#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;
}
}
网友评论