二叉堆【小顶堆】数组模板+C++STL

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <cstring>
  4 #include <vector>
  5 using namespace std;
  6 const int SIZE = 1e6;
  7 int heap[SIZE], n;
  8 
  9 
 10 void up(int p) {
 11  while(p > 1) {
 12 
 13   if(heap[p] < heap[p/2]) {
 14    swap(heap[p], heap[p/2]);
 15    p /= 2;
 16   }
 17   else break;
 18  }
 19 }
 20 
 21 void Insert(int val) {
 22  heap[++n] = val;
 23  up(n);
 24 }
 25 
 26 int GetTop() {
 27  return heap[1];
 28 }
 29 
 30 void down(int p) {
 31  int s = p * 2;
 32  while(s <= n) {
 33   if(heap[s] > heap[s+1] && s < n) s++;
 34   if(heap[s] < heap[p]){
 35    swap(heap[s], heap[p]);
 36    p = s, s = p * 2;
 37   }
 38   else break;
 39  }
 40 }
 41 void ExTract() {
 42  heap[1] = heap[n--];
 43  down(1);
 44 }
 45 void remove(int k) {
 46  heap[k] = heap[n--];
 47  up(k), down(k);
 48 }
 49 int main() {
 50  int t;
 51  cin >> t;
 52  for(int i = 0; i < t; ++ i) {
 53      int a;
 54      cin >> a;
 55      Insert(a);
 56  }
 57  return 0;
 58 }

  1 priority_queue<int, vector<int>, greater<int>> heap;