用C++寫(xiě)二叉堆（優(yōu)先隊(duì)列）代碼，詳細(xì)注釋-創(chuàng)新互聯(lián)

?什么是二叉堆？

簡(jiǎn)單來(lái)說(shuō)，二叉堆就是一顆完全二叉樹(shù)，它具有特殊性質(zhì)：

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

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

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

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

插入元素

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

刪除堆頂元素

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

• 對(duì)于小頂堆，首先比較兩個(gè)子節(jié)點(diǎn)的值，找出值較小的子節(jié)點(diǎn)，再進(jìn)行判斷：

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

  • 否則，將該較小的子節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)交換，重復(fù)之前操作

• 對(duì)于大頂堆，首先比較兩個(gè)子節(jié)點(diǎn)的值，找出值較大的子節(jié)點(diǎn)，再進(jìn)行判斷：

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

  • 否則，將該較大的子節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)交換，重復(fù)之前操作

下面展示了刪除堆頂元素2的過(guò)程

編寫(xiě)代碼

使用的數(shù)組來(lái)表示二叉堆，第一個(gè)元素下標(biāo)為1，左子樹(shù)坐標(biāo)為當(dāng)前節(jié)點(diǎn)下標(biāo)乘2，父節(jié)點(diǎn)下標(biāo)為當(dāng)前節(jié)點(diǎn)除2

#define ll(x) ((x)<<1)      //獲得左子樹(shù)下標(biāo) 
#define p(x)  ((x)>>1)      //獲得父節(jié)點(diǎn)下標(biāo)

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

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

上浮代碼如下，首先向val數(shù)組插入一個(gè)元素，cnt加一，并將新加入的元素不斷上浮到合適位置

void push(int n){
 ? ?int idx = cnt;
 ? ?val[cnt++] = n;          
 ? ?while(idx >1){     //從最后一個(gè)元素cnt的位置插入，不斷上浮到合適位置 
 ? ? ? ?if(compare(val[p(idx)], val[idx]))  swap(val[idx], val[p(idx)]);     
 ? ? ? ?idx = p(idx); 
 ?  }
}

下濾代碼如下，如果當(dāng)前堆為空，則返回-1，先將堆頂元素和最后一個(gè)元素交換位置，然后將第一個(gè)元素不斷下濾

int pop(){      //彈出堆頂元素 
 ? ?if(cnt == 1)    return -1;   
 ? ?int idx = 1, top = val[1];  //記錄當(dāng)前堆頂為top
 ? ?swap(val[1], val[--cnt]);   //將堆頂元素和最后一個(gè)元素交換位置，相當(dāng)于刪除了堆頂，cnt-1 
 ? ?while(idx<= cnt){      
 ? ? ? ?int child = ll(idx);
 ? ? ? ?//注意是child+1,大頂堆：和孩子節(jié)點(diǎn)較大者交換，小頂堆：和孩子節(jié)點(diǎn)較小者交換 
 ? ? ? ?if((child+1< cnt) && (compare(val[child], val[child+1])))  child++; 
 ? ? ? ?//這個(gè)條件很重要，不能刪除 
 ? ? ? ?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)		//獲得左子樹(shù)下標(biāo) 
#define p(x)  ((x)>>1)		//獲得父節(jié)點(diǎn)下標(biāo) 
using namespace std;
class Heap{	
private:
	int cnt = 1, val[MAX];			//數(shù)組下標(biāo)從1開(kāi)始，cnt表示下一個(gè)元素將要插入的位置，當(dāng)前元素個(gè)數(shù)為cnt-1 
	bool compare(int a, int b){return a:小頂堆 
public:
	Heap(){}; 
	Heap(int array[], int n){for(int i=0; i1){		//從最后一個(gè)元素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];	//記錄當(dāng)前堆頂為top
		swap(val[1], val[--cnt]);	//將堆頂元素和最后一個(gè)元素交換位置，相當(dāng)于刪除了堆頂，cnt-1 
		while(idx<= cnt){		
			int child = ll(idx);
			if((child+1< cnt) && (compare(val[child], val[child+1])))	child++; //注意是child+1,大頂堆：和孩子節(jié)點(diǎn)較大者交換，小頂堆：和孩子節(jié)點(diǎn)較小者交換 
			if(child< cnt && compare(val[idx], val[child])) 	swap(val[child], val[idx]);	//這個(gè)條件很重要，不能刪除 
			idx = child;
		}		
		return top;
	}
	int top()	{return val[1];}	//返回堆頂元素，但不彈出 
	int size()	{return cnt-1;} 
	void show() {for(int i=1;i

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

文章名稱：用C++寫(xiě)二叉堆（優(yōu)先隊(duì)列）代碼，詳細(xì)注釋-創(chuàng)新互聯(lián)
文章起源：http://muchs.cn/article22/ceeijc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站制作、微信小程序、做網(wǎng)站、網(wǎng)站內(nèi)鏈、網(wǎng)站營(yíng)銷、自適應(yīng)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)