189 8069 5689
简单来说，二叉堆就是一颗完全二叉树，它具有特殊性质：
创新互联建站服务项目包括都昌网站建设、都昌网站制作、都昌网页制作以及都昌网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，都昌网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到都昌省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！小顶堆：父节点的值小于两个孩子节点的值，处于堆顶的就是最小值
大顶堆：父节点的值大于两个孩子节点的值，处于堆顶的就是大值
如下面两图就举出了小顶堆和大顶堆的例子
插入元素会插入到最后一个元素的后面，不断地和父节点作比较，就拿小顶堆举例，如果当前节点的值小于父节点的值，就意味着当前节点要上浮，也就是交换当前节点和父节点的位置，下面就展示了插入1的上浮操作
删除堆顶元素后，将最后一个节点放在根节点，再进行下滤操作，即找到合适的位置而满足二叉堆性质：
对于小顶堆，首先比较两个子节点的值，找出值较小的子节点，再进行判断：
如果该较小的子节点比当前节点的值还要大，则找到了合适的位置，或者当前节点的右节点大于堆的大小，下滤结束
否则，将该较小的子节点与当前节点交换，重复之前操作
对于大顶堆，首先比较两个子节点的值，找出值较大的子节点，再进行判断：
如果该较大的子节点比当前节点的值还要小，则找到了合适的位置，或者当前节点的右节点大于堆的大小，下滤结束
否则，将该较大的子节点与当前节点交换，重复之前操作
下面展示了删除堆顶元素2的过程
使用的数组来表示二叉堆，第一个元素下标为1，左子树坐标为当前节点下标乘2，父节点下标为当前节点除2
#define ll(x) ((x)<<1) //获得左子树下标
#define p(x) ((x)>>1) //获得父节点下标二叉堆用cnt表示下一个待插入元素的下标，等于当前元素个数加一，定义了compare函数，a
private:
int cnt = 1, val[MAX];
//数组下标从1开始，cnt表示下一个元素将要插入的位置，当前元素个数为cnt-1
bool compare(int a, int b){return a:小顶堆 上浮代码如下，首先向val数组插入一个元素，cnt加一，并将新加入的元素不断上浮到合适位置
void push(int n){
int idx = cnt;
val[cnt++] = n;
while(idx >1){ //从最后一个元素cnt的位置插入，不断上浮到合适位置
if(compare(val[p(idx)], val[idx])) swap(val[idx], val[p(idx)]);
idx = p(idx);
}
}下滤代码如下，如果当前堆为空，则返回-1，先将堆顶元素和最后一个元素交换位置，然后将第一个元素不断下滤
int pop(){ //弹出堆顶元素
if(cnt == 1) return -1;
int idx = 1, top = val[1]; //记录当前堆顶为top
swap(val[1], val[--cnt]); //将堆顶元素和最后一个元素交换位置，相当于删除了堆顶，cnt-1
while(idx<= cnt){
int child = ll(idx);
//注意是child+1,大顶堆：和孩子节点较大者交换，小顶堆：和孩子节点较小者交换
if((child+1< cnt) && (compare(val[child], val[child+1]))) child++;
//这个条件很重要，不能删除
if(child< cnt && compare(val[idx], val[child])) swap(val[child], val[idx]);
idx = child;
}
return top;
}完整代码如下：
#include#include
#define MAX 10000
#define ll(x) ((x)<<1) //获得左子树下标
#define p(x) ((x)>>1) //获得父节点下标
using namespace std;
class Heap{
private:
int cnt = 1, val[MAX]; //数组下标从1开始，cnt表示下一个元素将要插入的位置，当前元素个数为cnt-1
bool compare(int a, int b){return a:小顶堆
public:
Heap(){};
Heap(int array[], int n){for(int i=0; i1){ //从最后一个元素cnt的位置插入，不断上浮到合适位置
if(compare(val[p(idx)], val[idx])) swap(val[idx], val[p(idx)]);
idx = p(idx);
}
}
int pop(){ //弹出堆顶元素
if(cnt == 1) return -1;
int idx = 1, top = val[1]; //记录当前堆顶为top
swap(val[1], val[--cnt]); //将堆顶元素和最后一个元素交换位置，相当于删除了堆顶，cnt-1
while(idx<= cnt){
int child = ll(idx);
if((child+1< cnt) && (compare(val[child], val[child+1]))) child++; //注意是child+1,大顶堆：和孩子节点较大者交换，小顶堆：和孩子节点较小者交换
if(child< cnt && compare(val[idx], val[child])) swap(val[child], val[idx]); //这个条件很重要，不能删除
idx = child;
}
return top;
}
int top() {return val[1];} //返回堆顶元素，但不弹出
int size() {return cnt-1;}
void show() {for(int i=1;i 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧