#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;
}
}
堆
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 堆的数据结构能够使得堆顶总是维持最大（对于大根堆）或最小（对于小根堆），给定一个数组，对这个数组进行建堆，则平均复...
- 转自: Imcache :一个Java新的缓存框架堆Heap是内存中动态分配对象居住的地方。如果使用new一个对象...
- 一、建堆 1、如果使用nums构建最大堆： 输出nums的结果为 2、如果使用nums构建最小堆： 输出nums的...
- 堆(Heap)和非堆(Non-heap)内存 按照官方的说法：“Java 虚拟机具有一个堆，堆是运行时数据...
