最小堆的满足以下三个条件a.堆是一颗完全二叉树 b.堆树中某个节点的值总是不大于或不小于其孩子节点的值c.堆树中每个节点的子树都是堆树
直接上代码
#include<iostream>
using namespace std;
class PQ{
private:
int sz;//优先队列的大小
int capacity;//优先队列的容量
int*pq;//数组保存优先队列里的元素
public:
PQ(int n){
pq=new int[n+1];
sz=0;
capacity=n;
}
~PQ(){
delete []pq;
}
void insert(int val){
if(sz>=capacity){
int*temp=new int[capacity<<1];
for(int i=1;i<=capacity;i++){
temp[i]=pq[i];
}
delete []pq;
pq=temp;
capacity<<=1;
}
sz++;
pq[sz]=val;
swim(sz);
}
int top(){
return pq[1];
}
int pop(){
int temp=pq[1];
swap(pq[1],pq[sz--]);
sink(1);
return temp;
}
int size(){
rturn sz;
}
//如果要插入的数比父节点小的话，上浮
void swim(int n){
while(n>1&&pq[n]<pq[n>>1]){
swap(pq[n],pq[n>>1]);
n>>1;
}
}
void sink(int n){
while(2*n<=sz){
int k=2*n;
if(k<sz&&pq[k]>pq[k+1]) k++;
if(pq[k]<pq[n]){
swap(pq[k],pq[n]);
n=k;
}else{
break;
}
}
}
}
