二叉堆

#include<bits/stdc++.h>
using namespace std;

template<typename T>
class Heap{
private:
  T *heap;
  int Size;
  void up(int pos) {
    while (pos>1) {
      if (heap[pos/2]<heap[pos]) {
        swap(heap[pos],heap[pos/2]);
        pos/=2;
      } else {
        break;
      }
    }
  }
  void down(int pos) {
    int son=pos*2;
    while (son<=Size) {
      if (son<Size && heap[son]<heap[son+1]) {
        son++;
      }
      if (heap[pos]<heap[son]) {
        swap(heap[son],heap[pos]);
        pos=son,son=pos*2;
      } else {
        break;
      }
    }
  }

public:
  Heap(int n) {
    heap=new T[n+10];
    Size=0;
  }
  Heap(int s,const T a[],int n) {
    heap=new T[s+10];
    Size=n;
    for (int i=0;i<n;i++) {
      heap[i+1]=a[i];
    }
    for (int pos=Size/2;pos>=1;pos--) {
      down(pos);
    }
  }
  ~Heap() {
    delete[] heap;
    heap=NULL;
  }
  const T& top() const {
    return heap[1];
  }
  const bool empty() const {
    return Size==0;
  }
  int size() const {
    return Size;
  }
  void pop() {
    heap[1]=heap[Size--];
    down(1);
  }
  void push(const T& val) {
    heap[++Size]=val;
    up(Size);
  }
};

int main()
{
  srand(time(NULL));
  Heap<int> h(10);
  for (int i=0;i<10;i++) {
    h.push(rand()%100);
  }
  while (!h.empty()) {
    cout<<h.top()<<endl;
    h.pop();
  }
  return 0;
}