?什么是二叉堆？

簡單來說，二叉堆就是一顆完全二叉樹，它具有特殊性質(zhì)：

創(chuàng)新互聯(lián)建站服務項目包括都昌網(wǎng)站建設、都昌網(wǎng)站制作、都昌網(wǎng)頁制作以及都昌網(wǎng)絡營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關系等，向廣大中小型企業(yè)、政府機構等提供互聯(lián)網(wǎng)行業(yè)的解決方案，都昌網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟效益。目前，我們服務的客戶以成都為中心已經(jīng)輻射到都昌省份的部分城市，未來相信會繼續(xù)擴大服務區(qū)域并繼續(xù)獲得客戶的支持與信任！

• 小頂堆：父節(jié)點的值小于兩個孩子節(jié)點的值，處于堆頂?shù)木褪亲钚≈?/p>

• 大頂堆：父節(jié)點的值大于兩個孩子節(jié)點的值，處于堆頂?shù)木褪谴笾?/p>

如下面兩圖就舉出了小頂堆和大頂堆的例子

插入元素

插入元素會插入到最后一個元素的后面，不斷地和父節(jié)點作比較，就拿小頂堆舉例，如果當前節(jié)點的值小于父節(jié)點的值，就意味著當前節(jié)點要上浮，也就是交換當前節(jié)點和父節(jié)點的位置，下面就展示了插入1的上浮操作

刪除堆頂元素

刪除堆頂元素后，將最后一個節(jié)點放在根節(jié)點，再進行下濾操作，即找到合適的位置而滿足二叉堆性質(zhì)：

• 對于小頂堆，首先比較兩個子節(jié)點的值，找出值較小的子節(jié)點，再進行判斷：

  • 如果該較小的子節(jié)點比當前節(jié)點的值還要大，則找到了合適的位置，或者當前節(jié)點的右節(jié)點大于堆的大小，下濾結束

  • 否則，將該較小的子節(jié)點與當前節(jié)點交換，重復之前操作

• 對于大頂堆，首先比較兩個子節(jié)點的值，找出值較大的子節(jié)點，再進行判斷：

  • 如果該較大的子節(jié)點比當前節(jié)點的值還要小，則找到了合適的位置，或者當前節(jié)點的右節(jié)點大于堆的大小，下濾結束

  • 否則，將該較大的子節(jié)點與當前節(jié)點交換，重復之前操作

下面展示了刪除堆頂元素2的過程

編寫代碼

使用的數(shù)組來表示二叉堆，第一個元素下標為1，左子樹坐標為當前節(jié)點下標乘2，父節(jié)點下標為當前節(jié)點除2

#define ll(x) ((x)<<1)      //獲得左子樹下標 
#define p(x)  ((x)>>1)      //獲得父節(jié)點下標

二叉堆用cnt表示下一個待插入元素的下標，等于當前元素個數(shù)加一，定義了compare函數(shù)，ab表示小頂堆

private:
    int cnt = 1, val[MAX];          
    //數(shù)組下標從1開始，cnt表示下一個元素將要插入的位置，當前元素個數(shù)為cnt-1 
    bool compare(int a, int b){return a:小頂堆

上浮代碼如下，首先向val數(shù)組插入一個元素，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,大頂堆：和孩子節(jié)點較大者交換，小頂堆：和孩子節(jié)點較小者交換 
 ? ? ? ?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)		//獲得父節(jié)點下標 
using namespace std;
class Heap{	
private:
	int cnt = 1, val[MAX];			//數(shù)組下標從1開始，cnt表示下一個元素將要插入的位置，當前元素個數(shù)為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,大頂堆：和孩子節(jié)點較大者交換，小頂堆：和孩子節(jié)點較小者交換 
			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

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧


當前題目：用C++寫二叉堆（優(yōu)先隊列）代碼，詳細注釋-創(chuàng)新互聯(lián)
本文網(wǎng)址：http://weahome.cn/article/ceeijc.html