文章目錄

• • 1 堆的原理
  • 2 堆的實(shí)現(xiàn)
  • • 2.1 堆的創(chuàng)建
    • 2.2 向堆中插入新元素
    • 2.3 堆頂元素出堆

1 堆的原理

先看一下堆長什么樣：

最大堆的特點(diǎn)：

每個結(jié)點(diǎn)最多可以有2個子結(jié)點(diǎn)。

根結(jié)點(diǎn)的鍵值是所有堆結(jié)點(diǎn)值中的最大者，且每個結(jié)點(diǎn)的值都比其孩子的值大。

除了根結(jié)點(diǎn)沒有兄弟結(jié)點(diǎn)，最后一個左子結(jié)點(diǎn)可以沒有兄弟結(jié)點(diǎn)，其他結(jié)點(diǎn)必須有兄弟結(jié)點(diǎn)。

看一下如下幾個符不符合最大堆的定義：

（A、B不是，C是最大堆。）

看一下堆的特點(diǎn)：

• 堆是你見過的最有個性的樹！它是用數(shù)組表示的樹！
  

對于i子結(jié)點(diǎn)：

• i的左子結(jié)點(diǎn)為：2 * i + 1
• i的右子結(jié)點(diǎn)為：2 * i + 2
• i的父結(jié)點(diǎn)：(i - 1) / 2

---

2 堆的實(shí)現(xiàn)

2.1 堆的創(chuàng)建

在數(shù)組中快速創(chuàng)建堆：

算法實(shí)現(xiàn)如下：

堆數(shù)據(jù)結(jié)構(gòu)的定義：

#define DEFAULT_CAPCITY 128typedef struct _Heap{int *arr; //存儲堆元素的數(shù)組int size; //當(dāng)前已存儲的元素個數(shù)int capacity; //當(dāng)前存儲的容量 }Heap;

建最大堆：

bool initHeap(Heap &heap, int *orginal, int size); static void buildHeap(Heap &heap); static void adjustDown(Heap &heap, int index);/*初始化堆*/ bool initHeap(Heap &heap, int *orginal, int size){int capacity = DEFAULT_CAPCITY>size? DEFAULT_CAPCITY:size;heap.arr = new int[capacity];if(!heap.arr) return false;heap.capacity = capacity;heap.size = 0;//如果存在原始數(shù)據(jù)則構(gòu)建堆if(size>0){memcpy(heap.arr, orginal, size*sizeof(int));heap.size = size;buildHeap(heap);}else {heap.size = 0;}return true; }/*將當(dāng)前的節(jié)點(diǎn)和子節(jié)點(diǎn)調(diào)整成最大堆*/ void adjustDown(Heap &heap, int index) { int cur=heap.arr[index];//當(dāng)前待調(diào)整的節(jié)點(diǎn)int parent,child;/*判斷否存在大于當(dāng)前節(jié)點(diǎn)子節(jié)點(diǎn)，如果不存在 ，則堆本身是平衡的，不需要調(diào)整；如果存在，則將最大的子節(jié)點(diǎn)與之交換，交換后，如果這個子節(jié)點(diǎn)還有子節(jié)點(diǎn)，則要繼續(xù)按照同樣的步驟對這個子節(jié)點(diǎn)進(jìn)行調(diào)整*/for(parent=index; (parent*2+1)<heap.size; parent=child){child=parent*2+1;//取兩個子節(jié)點(diǎn)中的最大的節(jié)點(diǎn)if(((child+1)<heap.size)&&(heap.arr[child]<heap.arr[child+1])){child++;}//判斷最大的節(jié)點(diǎn)是否大于當(dāng)前的父節(jié)點(diǎn)if(cur>=heap.arr[child]){//不大于，則不需要調(diào)整，跳出循環(huán)break;}else {//大于當(dāng)前的父節(jié)點(diǎn)，進(jìn)行交換，然后從子節(jié)點(diǎn)位置繼續(xù)向下調(diào)整heap.arr[parent]=heap.arr[child];heap.arr[child]=cur;}} }/* 從最后一個父節(jié)點(diǎn)(size/2-1 的位置)逐個往前調(diào)整所有父節(jié)點(diǎn) （直到根節(jié)點(diǎn)）,確保每一個父節(jié)點(diǎn)都是一個最大堆，最后整體上形成一個最大堆 */ void buildHeap(Heap &heap){int i;for(i=heap.size/2-1; i>=0; i--){adjustDown(heap, i);} }

2.2 向堆中插入新元素

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

/*將當(dāng)前的節(jié)點(diǎn)和父節(jié)點(diǎn)調(diào)整成最大堆*/ void adjustUp(Heap &heap, int index) {if(index<0 || index >= heap.size){//大于堆的最大值直接 returnreturn;}while(index>0){int temp = heap.arr[index];int parent = (index - 1) / 2;if(parent >= 0){//如果索引沒有出界就執(zhí)行想要的操作if(temp > heap.arr[parent]){heap.arr[index] = heap.arr[parent];heap.arr[parent] = temp;index = parent;}else {//如果已經(jīng)比父親小 直接結(jié)束循環(huán)break;}}else {//越界結(jié)束循環(huán)break;}} }/*最大堆尾部插入節(jié)點(diǎn)，同時保證最大堆的特性*/ bool insert(Heap &heap, int value) {if (heap.size == heap.capacity) {fprintf(stderr, "棧空間耗盡！\n");return false;}int index = heap.size;heap.arr[heap.size++] = value;adjustUp(heap, index);return true; }

這樣的話我們就可以有另一種創(chuàng)建堆的方式：

/*初始化堆*/ bool initHeap(Heap &heap, int *orginal, int size) {int capacity = DEFAULT_CAPCITY>size ? DEFAULT_CAPCITY : size;heap.arr = new int[capacity];if (!heap.arr) return false;heap.capacity = capacity;heap.size = 0;//如果存在原始數(shù)據(jù)則構(gòu)建堆if(size > 0){/*方式一: 直接調(diào)整所有元素memcpy(heap.arr, orginal, size*sizeof(int));heap.size = size;//建堆buildHeap(heap);*///方式二: 一次插入一個for(int i=0; i<size; i++){insert(heap, orginal[i]);}}return true; }

2.3 堆頂元素出堆

如果我們將堆頂?shù)脑貏h除，那么頂部有一個空的節(jié)點(diǎn)，怎么處理？

當(dāng)插入節(jié)點(diǎn)的時候，我們將新的值插入數(shù)組的尾部。現(xiàn)在我們來做相反的事情：我們?nèi)〕鰯?shù)組中的最后一個元素，將它放到堆的頂部，然后再修復(fù)堆屬性。

/* 刪除優(yōu)先隊(duì)列中最大的節(jié)點(diǎn)，并獲得節(jié)點(diǎn)的值*/ bool pop(Heap& heap, int &value) {if (!heap || (heap->size==0)) return false;value = heap.arr[0];pq.arr[0] = heap.arr[--heap.size];//heap.arr[0] = heap.arr[heap.size-1];//heap.size--;adjustDown(heap, 0);// 向下執(zhí)行堆調(diào)整return true; }

---

參考資料：

C/C++從入門到精通-高級程序員之路【奇牛學(xué)院】

總結(jié)

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

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