什么是二叉堆？

简单来说，二叉堆就是一颗完全二叉树，它具有特殊性质：

创新互联建站服务项目包括都昌网站建设、都昌网站制作、都昌网页制作以及都昌网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，都昌网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到都昌省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！

• 小顶堆：父节点的值小于两个孩子节点的值，处于堆顶的就是最小值

• 大顶堆：父节点的值大于两个孩子节点的值，处于堆顶的就是大值

如下面两图就举出了小顶堆和大顶堆的例子

插入元素

插入元素会插入到最后一个元素的后面，不断地和父节点作比较，就拿小顶堆举例，如果当前节点的值小于父节点的值，就意味着当前节点要上浮，也就是交换当前节点和父节点的位置，下面就展示了插入1的上浮操作

删除堆顶元素

删除堆顶元素后，将最后一个节点放在根节点，再进行下滤操作，即找到合适的位置而满足二叉堆性质：

• 对于小顶堆，首先比较两个子节点的值，找出值较小的子节点，再进行判断：

  • 如果该较小的子节点比当前节点的值还要大，则找到了合适的位置，或者当前节点的右节点大于堆的大小，下滤结束

  • 否则，将该较小的子节点与当前节点交换，重复之前操作

• 对于大顶堆，首先比较两个子节点的值，找出值较大的子节点，再进行判断：

  • 如果该较大的子节点比当前节点的值还要小，则找到了合适的位置，或者当前节点的右节点大于堆的大小，下滤结束

  • 否则，将该较大的子节点与当前节点交换，重复之前操作

下面展示了删除堆顶元素2的过程

编写代码

使用的数组来表示二叉堆，第一个元素下标为1，左子树坐标为当前节点下标乘2，父节点下标为当前节点除2

#define ll(x) ((x)<<1)      //获得左子树下标 
#define p(x)  ((x)>>1)      //获得父节点下标

二叉堆用cnt表示下一个待插入元素的下标，等于当前元素个数加一，定义了compare函数，ab表示小顶堆

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元起，快前往官网查看详情吧


本文名称：用C++写二叉堆（优先队列）代码，详细注释-创新互联
标题URL：http://kswjz.com/article/ceeijc.html