堆

#include<iostream>
#include<algorithm>
using namespace std;
template <class E>
class MaxPQ
{
private :
    E *arr;
    int n;
    void swim(int);
    void sink(int);
public :
    MaxPQ(int maxSize):n(0)
    {
        arr=new E[maxSize];
    }
    E deleteMax();
    void insert(E);
    bool isEmpty();
    E maxVal();

};
template <class E>
void MaxPQ<E>::swim(int k)
{
    while(k>=1&&arr[k]>arr[(k-1)/2])
    {
        swap(arr[k],arr[(k-1)/2]);
        k=(k-1)/2;
    }
}
template <class E>
void MaxPQ<E>::sink(int k)
{
    int j;
    while(2*k+1<n)
    {
        j=2*k+1;
        if(j<n-1&&arr[j]<arr[j+1]) j++;
        if(arr[k]>=arr[j]) break;
        swap(arr[j],arr[k]);
        k=j;
    }
}
template <class E>
void MaxPQ<E>::insert(E elem)
{
    arr[n]=elem;
    swim(n++);
}
template <class E>
E MaxPQ<E>::deleteMax()
{
    E val=arr[0];
    swap(arr[0],arr[--n]);
    sink(0);
    return val;
}
template <class E>
bool MaxPQ<E>::isEmpty()
{
    return n<1;
}
template <class E>
E MaxPQ<E>::maxVal()
{
    return arr[0];
}
int main()
{
    MaxPQ<int> pq(50);
    for(int i=0;i<50;i++)
    {
        pq.insert(i);
    }
    while(!pq.isEmpty())
    {
        cout<<pq.deleteMax()<<endl;
    }
}