一、堆樹的定義

堆樹的定義如下：

（1）堆樹是一顆完全二叉樹；

（2）堆樹中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其孩子節(jié)點(diǎn)的值；

（3）堆樹中每個(gè)節(jié)點(diǎn)的子樹都是堆樹。

當(dāng)父節(jié)點(diǎn)的鍵值總是大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為最大堆。 當(dāng)父節(jié)點(diǎn)的鍵值總是小于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為最小堆。如下圖所示，左邊為最大堆，右邊為最小堆。

二、堆樹的操作

以最大堆為例進(jìn)行講解，最小堆同理。

原始數(shù)據(jù)為a[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}，采用順序存儲方式，對應(yīng)的完全二叉樹如下圖所示：

（1）構(gòu)造最大堆

在構(gòu)造堆的基本思想就是：首先將每個(gè)葉子節(jié)點(diǎn)視為一個(gè)堆，再將每個(gè)葉子節(jié)點(diǎn)與其父節(jié)點(diǎn)一起構(gòu)造成一個(gè)包含更多節(jié)點(diǎn)的對。

所以，在構(gòu)造堆的時(shí)候，首先需要找到最后一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，從這個(gè)節(jié)點(diǎn)開始構(gòu)造最大堆；直到該節(jié)點(diǎn)前面所有分支節(jié)點(diǎn)都處理完畢，這樣最大堆就構(gòu)造完畢了。

假設(shè)樹的節(jié)點(diǎn)個(gè)數(shù)為n，以1為下標(biāo)開始編號，直到n結(jié)束。對于節(jié)點(diǎn)i，其父節(jié)點(diǎn)為i/2；左孩子節(jié)點(diǎn)為i*2，右孩子節(jié)點(diǎn)為i*2+1。最后一個(gè)節(jié)點(diǎn)的下標(biāo)為n，其父節(jié)點(diǎn)的下標(biāo)為n/2。

如下圖所示，最后一個(gè)節(jié)點(diǎn)為7，其父節(jié)點(diǎn)為16，從16這個(gè)節(jié)點(diǎn)開始構(gòu)造最大堆；構(gòu)造完畢之后，轉(zhuǎn)移到下一個(gè)父節(jié)點(diǎn)2，直到所有父節(jié)點(diǎn)都構(gòu)造完畢。

C++代碼實(shí)現(xiàn)：

定義存放堆的結(jié)構(gòu)如下：

strcut MaxHeap{ Etype *heap; int HeapSize; int MaxSize;};MaxHeap H;

其中，heap是數(shù)據(jù)元素存放的空間，下標(biāo)從1開始存數(shù)數(shù)據(jù)，下標(biāo)為0的作為工作空間，存儲臨時(shí)數(shù)據(jù)。HeapSize是數(shù)據(jù)元素的個(gè)數(shù)，MaxSize是存放數(shù)據(jù)元素空間的大小。

初始化堆方法如下：

void MaxHeapInit (MaxHeap &H){ for(int i = H.HeapSize/2; i>=1; i--) { H.heap[0] = H.heap[i]; int son = i*2; while(son <= H.HeapSize) { if(son < H.HeapSize && H.heap[son] < H.heap[son+1]) son++; if(H.heap[0] >= H.heap[son]) break; else { H.heap[son/2] = H.heap[son]; son *= 2; } } H.heap[son/2] = H.heap[0]; }}

（2）最大堆中插入節(jié)點(diǎn)

最大堆的插入節(jié)點(diǎn)的思想就是先在堆的最后添加一個(gè)節(jié)點(diǎn)，然后沿著堆樹上升。跟最大堆的初始化過程大致相同。

C++代碼實(shí)現(xiàn)：

void MaxHeapInsert (MaxHeap &H, EType &x){ if(H.HeapSize == H.MaxSize) return false; int i = ++H.HeapSize; while(i!=1 && x>H.heap[i/2]) { H.heap[i] = H.heap[i/2]; i = i/2; } H.heap[i] = x; return true;}

（3）最大堆中堆頂節(jié)點(diǎn)的刪除

最大堆堆頂節(jié)點(diǎn)刪除思想如下：將堆樹的最后的節(jié)點(diǎn)提到根結(jié)點(diǎn)，然后刪除最大值，然后再把新的根節(jié)點(diǎn)放到合適的位置。

C++代碼實(shí)現(xiàn)：

void MaxHeapDelete (MaxHeap &H, EType &x){ if(H.HeapSize == 0) return false; x = H.heap[1]; H.heap[0] = H.heap[H.HeapSize--]; int i = 1, son = i*2; while(son <= H.HeapSize) { if(son <= H.HeapSize && H.heap[0] < H.heap[son+1]) son++; if(H.heap[0] >= H.heap[son]) break; H.heap[i] = H.heap[son]; i = son; son = son*2; } H.heap[i] = H.heap[0]; return true;}

三、堆樹的應(yīng)用

利用最大堆、最小堆進(jìn)行排序。

堆排序算法詳解：http://blog.csdn.net/guoweimelon/article/details/50904231

參考文獻(xiàn)：

1、徹底弄懂最大堆的四種操作(圖解+程序)（JAVA）?http://128kj.iteye.com/blog/1728555

2、最大堆、最小堆?http://blog.csdn.net/genios/article/details/8157031

轉(zhuǎn)載于:https://www.cnblogs.com/leebxo/p/11058555.html

總結(jié)

以上是生活随笔為你收集整理的堆树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。