目錄

前言

一.堆的介紹

1.堆的本質(zhì)

2.堆的分類

二.堆的實(shí)現(xiàn)(以小根堆為例)

1.關(guān)于二叉樹(shù)的兩組重要結(jié)論：

2.堆的物理存儲(chǔ)結(jié)構(gòu)框架(動(dòng)態(tài)數(shù)組的簡(jiǎn)單構(gòu)建)

3. 堆元素插入接口(以小根堆為例)

堆尾元素向上調(diào)整的算法接口:

4.堆元素插入接口測(cè)試

5.堆元素插入接口建堆的時(shí)間復(fù)雜度分析(建堆時(shí)間復(fù)雜度)

6.堆元素刪除接口(同樣以小根堆為例子)

堆元素向下調(diào)整算法接口實(shí)現(xiàn):

7.堆元素刪除接口測(cè)試

8.逐個(gè)刪除堆頂數(shù)據(jù)過(guò)程的時(shí)間復(fù)雜度分析(刪堆的時(shí)間復(fù)雜度分析)

9.堆的實(shí)現(xiàn)代碼總覽(以小根堆為例)

10.結(jié)語(yǔ)

?

?

---

前言

關(guān)于數(shù)據(jù)結(jié)構(gòu)的文章:寫博客的時(shí)候我感覺(jué)在表達(dá)層面上有點(diǎn)費(fèi)勁,如果文章整體在表述上讓人感覺(jué)不夠清楚,懇請(qǐng)讀者原諒,本菜狗已經(jīng)盡力了.

一.堆的介紹

1.堆的本質(zhì)

關(guān)于二叉樹(shù)的圖論基礎(chǔ)參見(jiàn):http://t.csdn.cn/Nv325http://t.csdn.cn/Nv325青菜友情提示:基礎(chǔ)概念對(duì)于理解堆的實(shí)現(xiàn)與運(yùn)用非常重要

堆的本質(zhì)是映射在內(nèi)存中順序存儲(chǔ)結(jié)構(gòu)(數(shù)組)上的完全二叉樹(shù)(完全二叉樹(shù)是堆的邏輯結(jié)構(gòu)).

堆的圖解:

• 結(jié)點(diǎn)中的數(shù)據(jù)存儲(chǔ)在相應(yīng)下標(biāo)的數(shù)組元素空間中

2.堆的分類

堆的兩個(gè)類型：

1. 大根堆:在大根堆中任何子結(jié)構(gòu)的父結(jié)點(diǎn)中存儲(chǔ)的值大于其左右孩子結(jié)點(diǎn)中存儲(chǔ)的值
2. 小根堆:在小根堆中任何子結(jié)構(gòu)的父結(jié)點(diǎn)中存儲(chǔ)的值小于其左右孩子結(jié)點(diǎn)中存儲(chǔ)的值

二.堆的實(shí)現(xiàn)(以小根堆為例)

1.關(guān)于二叉樹(shù)的兩組重要結(jié)論：

• 堆的任何一個(gè)父結(jié)點(diǎn)的編號(hào)parent與其左孩子結(jié)點(diǎn)的編號(hào)leftchild滿足如下關(guān)系式:
• 堆的任何一個(gè)父結(jié)點(diǎn)的編號(hào)parent與其右孩子結(jié)點(diǎn)的編號(hào)rightchild滿足如下關(guān)系式:

這兩組重要結(jié)論的推導(dǎo)和分析參見(jiàn)青菜的博客:http://t.csdn.cn/Nv325http://t.csdn.cn/Nv325

2.堆的物理存儲(chǔ)結(jié)構(gòu)框架(動(dòng)態(tài)數(shù)組的簡(jiǎn)單構(gòu)建)

堆是存儲(chǔ)在數(shù)組上的(大小根)完全二叉樹(shù),因此在實(shí)現(xiàn)堆之前我們先構(gòu)建一個(gè)簡(jiǎn)單的動(dòng)態(tài)數(shù)組作為物理存儲(chǔ)結(jié)構(gòu)框架:

• 維護(hù)動(dòng)態(tài)數(shù)組的結(jié)構(gòu)體:

  typedef int HPDataType;   //堆元素類型
  typedef struct Heap
  {HPDataType* arry;     //堆區(qū)內(nèi)存指針size_t size;          //堆元素個(gè)數(shù)size_t capacity;      //數(shù)組的空間容量
  }HP;
  

• 堆的基礎(chǔ)操作接口聲明：

  //維護(hù)堆的結(jié)構(gòu)體的初始化接口
  void HeapInit(HP* php);//銷毀堆的接口
  void HeapDestroy(HP* php);//堆元素的打印接口
  void HeapPrint(HP* php);//判斷堆是否為空(堆中有無(wú)元素)的接口
  bool HeapEmpty(HP* php);//返回堆中元素個(gè)數(shù)的接口
  size_t HeapSize(HP* php);//返回堆頂元素(即編號(hào)為0的元素)的接口
  HPDataType HeapTop(HP* php);

• 基礎(chǔ)接口的實(shí)現(xiàn):

  //堆結(jié)構(gòu)體的初始化接口
  void HeapInit(HP* ptrheap)
  {assert(ptrheap);ptrheap->arry = NULL;ptrheap->capacity = 0;ptrheap->size = 0;}//銷毀堆的接口
  void HeapDestroy(HP* ptrheap)
  {assert(ptrheap);free(ptrheap->arry);ptrheap->arry = NULL;ptrheap->capacity = 0;ptrheap->size = 0;
  }//堆的打印接口
  void HeapPrint(HP* ptrheap)
  {assert(ptrheap);size_t tem = 0;for (tem = 0; tem < ptrheap->size; ++tem){printf("%d->", ptrheap->arry[tem]);}printf("END\n");
  }//判斷堆是否為空的接口
  bool HeapEmpty(HP* ptrheap)
  {assert(ptrheap);return (0 == ptrheap->size);
  }//返回堆元素個(gè)數(shù)的接口
  size_t HeapSize(HP* ptrheap)
  {assert(ptrheap);return ptrheap->size;
  }//返回堆頂元素的接口
  HPDataType HeapTop(HP* ptrheap)
  {assert(!HeapEmpty(ptrheap));return ptrheap->arry[0];
  }

  主函數(shù)建堆時(shí)的內(nèi)存布局簡(jiǎn)單圖示:

  

  堆區(qū)上的數(shù)組是在堆元素插入接口中調(diào)用malloc申請(qǐng)出來(lái)的(我們暫時(shí)還沒(méi)有實(shí)現(xiàn)堆元素插入的接口)

• 以上是堆在內(nèi)存中的存儲(chǔ)框架的構(gòu)建,然而堆的核心接口是堆元素的插入和刪除接口

3. 堆元素插入接口(以小根堆為例)

• 堆的構(gòu)建過(guò)程概述:向堆尾逐個(gè)插入元素(將元素尾插進(jìn)數(shù)組中),每次插入一個(gè)元素后都通過(guò)堆的調(diào)整算法逐層向上(二叉樹(shù)意義上的層)(子結(jié)點(diǎn)和父結(jié)點(diǎn)進(jìn)行大小比較,若不滿足小根堆的性質(zhì)就進(jìn)行數(shù)值交換)調(diào)整該元素在堆中的位置以保持小根堆的數(shù)據(jù)結(jié)構(gòu).
• 算法過(guò)程簡(jiǎn)圖:
• 從0個(gè)結(jié)點(diǎn)的堆開(kāi)始,每尾插一個(gè)元素我們都按照小根堆的性質(zhì)(通過(guò)元素向上調(diào)整算法)調(diào)整該元素在堆中的位置來(lái)保持小根堆的數(shù)據(jù)結(jié)構(gòu),我們就是以這樣的基本思想來(lái)建堆的.
• 建堆的思路細(xì)解:

• 顯然在堆尾插入元素6后破壞了小根堆的結(jié)構(gòu)(6小于其父結(jié)點(diǎn)20不滿足小根堆的性質(zhì))(將任意一個(gè)子結(jié)構(gòu)中子結(jié)點(diǎn)與父結(jié)點(diǎn)進(jìn)行大小比較就可以知道堆的結(jié)構(gòu)有沒(méi)有被破壞),因此我們就需要將6這個(gè)元素逐層向二叉樹(shù)的上層調(diào)整(每個(gè)調(diào)整的子步驟都是從子結(jié)點(diǎn)向父結(jié)點(diǎn)調(diào)整)
• 通過(guò)樹(shù)的子結(jié)構(gòu)中子結(jié)點(diǎn)與父結(jié)點(diǎn)的編號(hào)關(guān)系可以找到堆尾8號(hào)結(jié)點(diǎn)(元素6)的父結(jié)點(diǎn)(元素20,結(jié)點(diǎn)編號(hào)為3)
• 接下來(lái)將元素逐層向上調(diào)整(子結(jié)點(diǎn)和父結(jié)點(diǎn)進(jìn)行數(shù)值交換)來(lái)恢復(fù)小根堆的數(shù)據(jù)結(jié)構(gòu):

向上調(diào)整的第一步:將尾插進(jìn)堆尾的結(jié)點(diǎn)(8號(hào)結(jié)點(diǎn),值為6)與其父結(jié)點(diǎn)(3號(hào)結(jié)點(diǎn),值為20)進(jìn)行比較,父結(jié)點(diǎn)大于子結(jié)點(diǎn),交換父結(jié)點(diǎn)與子結(jié)點(diǎn)的值(下圖中的Swap是元素?cái)?shù)值交換接口):

向上調(diào)整的第二步:交換了8號(hào)結(jié)點(diǎn)和3號(hào)結(jié)點(diǎn)的值后,我們發(fā)現(xiàn)小堆結(jié)構(gòu)依然不成立,于是重復(fù)上述的調(diào)整過(guò)程,將元素6繼續(xù)向上層的父結(jié)點(diǎn)位置進(jìn)行調(diào)整,不斷重復(fù)迭代直到小堆結(jié)構(gòu)恢復(fù)或者元素6被調(diào)到堆頂為止:

• 可見(jiàn)經(jīng)過(guò)再一次調(diào)整后,元素6來(lái)到了1號(hào)結(jié)點(diǎn),此時(shí)1號(hào)結(jié)點(diǎn)大于0號(hào)結(jié)點(diǎn),小堆數(shù)據(jù)結(jié)構(gòu)得到恢復(fù),調(diào)整過(guò)程終止。

同時(shí)不難分析出,任何堆尾元素向上調(diào)整的過(guò)程都是在堆尾到堆頂元素的連通路徑上進(jìn)行的(該路徑長(zhǎng)度數(shù)量級(jí)為logk)(k為當(dāng)前樹(shù)結(jié)點(diǎn)總個(gè)數(shù))):

• 根據(jù)上面的分析我們可以設(shè)計(jì)出一個(gè)堆尾元素向上調(diào)整的算法接口:

接口首部: arry是指向數(shù)組首地址的指針,child是堆尾元素的編號(hào)(結(jié)點(diǎn)編號(hào)同時(shí)也是該元素的數(shù)組下標(biāo))

void AdjustUp(HPDataType* arry, size_t child);

堆尾元素向上調(diào)整的算法接口:

//元素交換接口
void Swap(HPDataType* e1, HPDataType* e2)
{assert(e1 && e2);HPDataType tem = *e1;*e1 = *e2;*e2 = tem;
}//小堆元素的向上調(diào)整接口
void AdjustUp(HPDataType* arry, size_t child)  //child表示孩子結(jié)點(diǎn)的編號(hào)
{assert(arry);size_t parent = (child - 1) / 2;    //算出父結(jié)點(diǎn)的數(shù)組下標(biāo)(堆編號(hào))while (child > 0)			        //child減小到0時(shí)則調(diào)整結(jié)束(堆尾元素已調(diào)到堆頂){if (arry[child] < arry[parent]) //父結(jié)點(diǎn)大于子結(jié)點(diǎn),則子結(jié)點(diǎn)需要上調(diào)以保持小堆的結(jié)構(gòu){Swap(arry + child, arry+parent);child = parent;				//將原父結(jié)點(diǎn)作為新的子結(jié)點(diǎn)繼續(xù)迭代過(guò)程parent = (child - 1) / 2;	//算出父結(jié)點(diǎn)的數(shù)組下標(biāo)(堆編號(hào))}else{break;						//父結(jié)點(diǎn)不大于子結(jié)點(diǎn),則堆結(jié)構(gòu)恢復(fù),無(wú)需再調(diào)整}}
}

堆尾元素向上調(diào)整的算法接口中需要注意的細(xì)節(jié):

• 調(diào)整循環(huán)的終止條件有兩個(gè):

1. 一個(gè)是被調(diào)整元素被調(diào)到了堆頂(即child=0的時(shí)候)
2. 當(dāng)被調(diào)整元素大于其父結(jié)點(diǎn)時(shí)小堆的數(shù)據(jù)結(jié)構(gòu)得到恢復(fù),break終止循環(huán)

有了該接口,我們就可以設(shè)計(jì)堆元素插入接口:

• HP * ptrheap是指向堆結(jié)構(gòu)體的結(jié)構(gòu)體指針,x是要插入的元素的數(shù)值

void HeapPush(HP* ptrheap, HPDataType x)

// 插入一個(gè)小堆元素的接口
// 插入x以后，保持其數(shù)據(jù)結(jié)構(gòu)依舊是小堆
void HeapPush(HP* ptrheap, HPDataType x)        //ptrheap是指向堆結(jié)構(gòu)體的結(jié)構(gòu)體指針
{assert(ptrheap);if (ptrheap->capacity == ptrheap->size)	    //數(shù)組容量檢查,容量不夠則擴(kuò)容{size_t newcapacity = (0 == ptrheap->capacity) ? 4 : 2 * ptrheap->capacity;//注意容量為0則將堆區(qū)數(shù)組容量調(diào)整為4HPDataType* tem = (HPDataType*)realloc(ptrheap->arry, newcapacity*sizeof(HPDataType)); //空間不夠則擴(kuò)容assert(tem);             //檢查擴(kuò)容是否成功ptrheap->arry = tem;     //將堆區(qū)地址賦給結(jié)構(gòu)體中的指針成員ptrheap->capacity = newcapacity; //容量標(biāo)記更新}ptrheap->arry[ptrheap->size] = x;			//元素尾插入堆ptrheap->size++;//將尾插的元素進(jìn)行向上調(diào)整以保持堆的數(shù)據(jù)結(jié)構(gòu)(復(fù)用元素向上調(diào)整接口)AdjustUp(ptrheap->arry, ptrheap->size - 1); //根據(jù)完全二叉樹(shù)的結(jié)構(gòu)特點(diǎn)可知堆尾元素                //在二叉樹(shù)中編號(hào)為size-1
}

• 該接口可以完成一個(gè)堆元素的插入(而且每次完成插入后小根堆的數(shù)據(jù)結(jié)構(gòu)都可以得到保持)
• 如果我們想要?jiǎng)?chuàng)建一個(gè)n個(gè)元素小根堆,則n次調(diào)用HeapPush接口即可

4.堆元素插入接口測(cè)試

現(xiàn)在我們?cè)囍肏eapPush接口來(lái)構(gòu)建六個(gè)元素的小堆,并將堆打印出來(lái)觀察其邏輯結(jié)構(gòu):

• 主函數(shù)代碼:

  int main ()
  {HP hp;              //創(chuàng)建一個(gè)堆結(jié)構(gòu)體HeapInit(&hp);      //結(jié)構(gòu)體初始化HeapPush(&hp, 1);   //調(diào)用堆元素插入接口建堆HeapPush(&hp, 5);HeapPush(&hp, 0);HeapPush(&hp, 8);HeapPush(&hp, 3);HeapPush(&hp, 9);HeapPrint(&hp);     //打印堆元素
  }

  

  我們來(lái)觀察一下打印出來(lái)的小根堆的邏輯結(jié)構(gòu):

5.堆元素插入接口建堆的時(shí)間復(fù)雜度分析(建堆時(shí)間復(fù)雜度)

• 假設(shè)現(xiàn)在我們要調(diào)用HeapPush接口來(lái)創(chuàng)建一個(gè)N個(gè)元素的小堆(調(diào)用N次HeapPush接口)
• 注意:我們只關(guān)注時(shí)間復(fù)雜度最壞的情況(即假設(shè)每個(gè)插入堆尾的元素都沿著連通路徑向上調(diào)整到了堆頂)
• 分析建堆的時(shí)間復(fù)雜度時(shí)我們將堆看成滿二叉樹(shù)(滿二叉樹(shù)是特殊的完全二叉樹(shù)),也就是說(shuō)當(dāng)堆有N個(gè)元素時(shí),堆的層數(shù)h=log(N+1)(該對(duì)數(shù)以2為底,計(jì)算機(jī)科學(xué)中我們一般不關(guān)注對(duì)數(shù)的底數(shù))
• 接下來(lái)我們將所有元素的向上調(diào)整次數(shù)進(jìn)行求和,即可得出用HeapPush接口建堆的時(shí)間復(fù)雜度:
• 用錯(cuò)位相減法可對(duì)上面公式進(jìn)行求和計(jì)算:
• 因此可以得到用堆元素插入接口(堆元素向上調(diào)整算法)建堆(建立N個(gè)元素的小根堆)的時(shí)間復(fù)雜度為:O(N)=NlogN;

6.堆元素刪除接口(同樣以小根堆為例子)

我們討論的堆元素刪除指的是:刪除堆頂數(shù)據(jù)

刪除堆頂?shù)脑?/span>的基本思路:

• 先將堆頂元素與堆尾元素進(jìn)行交換,然后令維護(hù)堆的結(jié)構(gòu)體中的size(記錄堆元素個(gè)數(shù)的成員變量)減一(相當(dāng)于移除堆尾元素)
• 然而原來(lái)的堆尾元素被交換到堆頂位置后,小根堆的數(shù)據(jù)結(jié)構(gòu)會(huì)被破壞,因此我們需要將堆頂元素進(jìn)行向下調(diào)整操作:
• 堆頂元素向下調(diào)整圖解演示:
• 通過(guò)算法圖解分析我們可以設(shè)計(jì)一個(gè)堆元素向下調(diào)整算法接口:?

arry是指向內(nèi)存堆區(qū)數(shù)組首地址的指針,size是堆的結(jié)點(diǎn)總個(gè)數(shù),parent是待調(diào)整結(jié)點(diǎn)在堆中的編號(hào);

void AdjustDown(HPDataType* arry,size_t size,size_t parent)

堆元素向下調(diào)整算法接口實(shí)現(xiàn):

//元素交換接口
void Swap(HPDataType* e1, HPDataType* e2)
{assert(e1 && e2);HPDataType tem = *e1;*e1 = *e2;*e2 = tem;
}//小堆元素的向下調(diào)整接口
void AdjustDown(HPDataType* arry,size_t size,size_t parent)
{assert(arry);size_t child = 2 * parent + 1;   //確定父結(jié)點(diǎn)的左孩子的編號(hào)while (child < size)			 //child增加到大于或等于size時(shí)說(shuō)明被調(diào)整元素被調(diào)整到了葉結(jié)點(diǎn)上,調(diào)整過(guò)程結(jié)束{if (child + 1 < size && arry[child + 1] < arry[child])//確定左右孩子中較小的孩子結(jié)點(diǎn){++child;   //條件成立說(shuō)明右孩子較小,child更新為右孩子編號(hào)}if ( arry[child] < arry[parent])//父結(jié)點(diǎn)大于子結(jié)點(diǎn),則父結(jié)點(diǎn)需要下調(diào)以保持小堆的結(jié)構(gòu){Swap(arry + parent, arry + child);//父子結(jié)點(diǎn)進(jìn)行值交換parent = child;				      //將原來(lái)的子結(jié)點(diǎn)作為新的父結(jié)點(diǎn)繼續(xù)迭代過(guò)程child = 2 * parent + 1;		      //繼續(xù)向下找另外一個(gè)子結(jié)點(diǎn)}else{break;						//父結(jié)點(diǎn)不大于子結(jié)點(diǎn),則小堆結(jié)構(gòu)成立,無(wú)需繼續(xù)調(diào)整}}
}

• ?注意一下算法接口的一些細(xì)節(jié)和邊界條件:

1. child<size說(shuō)明被調(diào)整元素已經(jīng)被調(diào)整到葉結(jié)點(diǎn)位置,結(jié)束調(diào)整過(guò)程
2. 算法接口中我們只設(shè)計(jì)了一個(gè)child變量來(lái)記錄當(dāng)前父結(jié)點(diǎn)的孩子結(jié)點(diǎn)的編號(hào),接著通過(guò)arry[child + 1] < arry[child]來(lái)比較左右孩子大小來(lái)確定child到底是取左孩子的編號(hào)還是取右孩子的編號(hào)(注意child+1<size判斷語(yǔ)句是為了確定右孩子是否存在)

• 有了堆元素向下調(diào)整算法接口我們就可以實(shí)現(xiàn)堆頂數(shù)據(jù)刪除接口:

  //刪除堆頂元素
  void HeapPop(HP* ptrheap)
  {assert(ptrheap);Swap(ptrheap->arry, ptrheap->arry + ptrheap->size - 1); //交換堆頂與堆尾元素ptrheap->size--;										//刪除堆尾元素AdjustDown(ptrheap->arry, ptrheap->size, 0);    //將堆頂元素進(jìn)行向下調(diào)整以保持堆的數(shù)據(jù)結(jié)構(gòu)
  }

  注意:AdjustDown接口的傳參中,ptrheadp->size指的是堆元素的總個(gè)數(shù),由于我們要將堆頂元素向下調(diào)整,因此傳入的被調(diào)整結(jié)點(diǎn)編號(hào)為0

• 該接口每調(diào)用一次就可以刪除一個(gè)堆頂數(shù)據(jù)(并保持小根堆的數(shù)據(jù)結(jié)構(gòu)):

7.堆元素刪除接口測(cè)試

我們先6次調(diào)用HeapPush接口創(chuàng)建一個(gè)六個(gè)元素的小堆,然后再6次調(diào)用HeapPop接口逐個(gè)刪除堆頂元素(每刪除一個(gè)堆頂數(shù)據(jù)打印一次堆,借此觀察每次刪除堆頂數(shù)據(jù)后堆的數(shù)據(jù)結(jié)構(gòu)).

int main ()
{HP hp;HeapInit(&hp);HeapPush(&hp, 1);HeapPush(&hp, 5);HeapPush(&hp, 0);HeapPush(&hp, 8);HeapPush(&hp, 3);HeapPush(&hp, 9);HeapPrint(&hp);HeapPop(&hp);HeapPrint(&hp);HeapPop(&hp);HeapPrint(&hp);HeapPop(&hp);HeapPrint(&hp);HeapPop(&hp);HeapPrint(&hp);HeapPop(&hp);HeapPrint(&hp);HeapDestroy(&hp);}

觀察小根堆的數(shù)據(jù)結(jié)構(gòu)(邏輯結(jié)構(gòu)):?

• 可見(jiàn)逐個(gè)刪除堆頂數(shù)據(jù)的過(guò)程中小根堆的數(shù)據(jù)結(jié)構(gòu)得到了保持

8.逐個(gè)刪除堆頂數(shù)據(jù)過(guò)程的時(shí)間復(fù)雜度分析(刪堆的時(shí)間復(fù)雜度分析)

假設(shè)現(xiàn)在有一個(gè)N個(gè)元素的小根堆,我們逐個(gè)刪除堆頂數(shù)據(jù)直到將堆刪空。

現(xiàn)在我們來(lái)分析這個(gè)過(guò)程的時(shí)間復(fù)雜度(我們同樣將二叉樹(shù)看成滿二叉樹(shù)來(lái)分析):

• 同樣我們考慮的是時(shí)間復(fù)雜度最壞的情況:即每次調(diào)用堆元素刪除接口后,被交換到堆頂?shù)脑囟?/span>沿著連通路徑向下被調(diào)整到葉結(jié)點(diǎn)
• 分析：假設(shè)堆的高度為h,則滿樹(shù)的總結(jié)點(diǎn)個(gè)數(shù)N為? : 2^h?- 1?
  需要注意的是滿樹(shù)的第h層(最后一層)的結(jié)點(diǎn)個(gè)數(shù)為: 2^(h-1)

所以滿樹(shù)的最后一層的結(jié)點(diǎn)個(gè)數(shù)占樹(shù)的總結(jié)點(diǎn)個(gè)數(shù)的一半

因此如果我們刪去滿樹(shù)的前h-1層的所有結(jié)點(diǎn),則由最后一層結(jié)點(diǎn)所構(gòu)成的新樹(shù)的高度大致為h-1:

這也就意味著,在刪除前h-1層結(jié)點(diǎn)的過(guò)程中樹(shù)的總高度幾乎不會(huì)發(fā)生變化:

因此可以得到刪除滿樹(shù)的前h-1層所有結(jié)點(diǎn)過(guò)程中,每個(gè)被交換到堆頂?shù)脑囟家幌蛳抡{(diào)整log(N+1)次,則刪除滿樹(shù)的前h-1層所有結(jié)點(diǎn)過(guò)程中,向下調(diào)整算法中循環(huán)語(yǔ)句執(zhí)行總次數(shù)約為:

接著,對(duì)于由原樹(shù)的最后一層(第h層)結(jié)點(diǎn)構(gòu)成的新樹(shù)(層數(shù)為h-1層)我們可以作類似的分析(即先刪除其前h-2層結(jié)點(diǎn),得到由其第h-1層結(jié)點(diǎn)構(gòu)成的新樹(shù)),以這種方式遞推下去直到樹(shù)被刪空為止:

• 由此可得,?逐個(gè)刪除堆頂數(shù)據(jù)直到將堆刪空過(guò)程中,堆元素的向下調(diào)整算法中循環(huán)語(yǔ)句總的執(zhí)行次數(shù)估算為:

該多項(xiàng)式的和化為大O階漸進(jìn)表示法結(jié)果為O(NlogN).?

• 逐個(gè)刪除堆頂數(shù)據(jù)直到將堆刪空的過(guò)程的時(shí)間復(fù)雜度分析為:O(NlogN)

9.堆的實(shí)現(xiàn)代碼總覽(以小根堆為例)

接口和結(jié)構(gòu)類型聲明的頭文件:

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>//實(shí)現(xiàn)小堆typedef int HPDataType;
typedef struct Heap
{HPDataType* arry;size_t size;size_t capacity;
}HP;//堆的初始化接口
void HeapInit(HP* php);
//銷毀堆的接口
void HeapDestroy(HP* php);
//堆的打印接口
void HeapPrint(HP* php);
//判斷堆是否為空的接口
bool HeapEmpty(HP* php);
//返回堆元素個(gè)數(shù)的接口
size_t HeapSize(HP* php);
//返回堆頂元素的接口
HPDataType HeapTop(HP* php);void Swap(HPDataType* pa, HPDataType* pb);
//堆元素向上調(diào)整算法接口
void AdjustUp(HPDataType* a, size_t child);
//堆元素向下調(diào)整算法接口
void AdjustDown(HPDataType* a, size_t size,size_t parent);
// 插入元素x以后，保持?jǐn)?shù)據(jù)結(jié)構(gòu)是(大/小)堆
void HeapPush(HP* php, HPDataType x);
// 刪除堆頂?shù)臄?shù)據(jù)后,保持?jǐn)?shù)據(jù)結(jié)構(gòu)是(大/小)堆
void HeapPop(HP* php);

各個(gè)堆操作接口的實(shí)現(xiàn):

#include "heap.h"//堆的初始化接口
void HeapInit(HP* ptrheap)
{assert(ptrheap);ptrheap->arry = NULL;ptrheap->capacity = 0;ptrheap->size = 0;}
//銷毀堆的接口
void HeapDestroy(HP* ptrheap)
{assert(ptrheap);free(ptrheap->arry);ptrheap->arry = NULL;ptrheap->capacity = 0;ptrheap->size = 0;
}//堆的打印接口
void HeapPrint(HP* ptrheap)
{assert(ptrheap);size_t tem = 0;for (tem = 0; tem < ptrheap->size; ++tem){printf("%d->", ptrheap->arry[tem]);}printf("END\n");
}//判斷堆是否為空的接口
bool HeapEmpty(HP* ptrheap)
{assert(ptrheap);return (0 == ptrheap->size);
}//返回堆元素個(gè)數(shù)的接口
size_t HeapSize(HP* ptrheap)
{assert(ptrheap);return ptrheap->size;
}//返回堆頂元素的接口
HPDataType HeapTop(HP* ptrheap)
{assert(!HeapEmpty(ptrheap));return ptrheap->arry[0];
}//元素交換接口
void Swap(HPDataType* e1, HPDataType* e2)
{assert(e1 && e2);HPDataType tem = *e1;*e1 = *e2;*e2 = tem;
}//小堆元素的向上調(diào)整接口
void AdjustUp(HPDataType* arry, size_t child)  //child表示孩子結(jié)點(diǎn)的編號(hào)
{assert(arry);size_t parent = (child - 1) / 2;while (child > 0)						   //child減小到0時(shí)則調(diào)整結(jié)束{if (arry[child] < arry[parent])        //父結(jié)點(diǎn)大于子結(jié)點(diǎn),則子結(jié)點(diǎn)需要上調(diào)以保持小堆的結(jié)構(gòu){Swap(arry + child, arry+parent);child = parent;				//將原父結(jié)點(diǎn)作為新的子結(jié)點(diǎn)繼續(xù)迭代過(guò)程parent = (child - 1) / 2;	//繼續(xù)向上找另外一個(gè)父結(jié)點(diǎn)}else{break;						//父結(jié)點(diǎn)不大于子結(jié)點(diǎn),則堆結(jié)構(gòu)任然成立,無(wú)需調(diào)整}}
}// 插入一個(gè)小堆元素的接口
// 插入x以后，保持其數(shù)據(jù)結(jié)構(gòu)依舊是小堆
void HeapPush(HP* ptrheap, HPDataType x)
{assert(ptrheap);if (ptrheap->capacity == ptrheap->size)	//容量檢查,容量不夠則擴(kuò)容{size_t newcapacity = (0 == ptrheap->capacity) ? 4 : 2 * ptrheap->capacity;HPDataType* tem = (HPDataType*)realloc(ptrheap->arry, newcapacity * sizeof(HPDataType));assert(tem);ptrheap->arry = tem;ptrheap->capacity = newcapacity;}ptrheap->arry[ptrheap->size] = x;			//先尾插一個(gè)元素ptrheap->size++;//將尾插的元素進(jìn)行向上調(diào)整以保持堆的數(shù)據(jù)結(jié)構(gòu)AdjustUp(ptrheap->arry, ptrheap->size - 1); //根據(jù)完全二叉樹(shù)的結(jié)構(gòu)特點(diǎn)可知尾插進(jìn)數(shù)組的元素在二叉樹(shù)中編號(hào)為size-1
}//小堆元素的向下調(diào)整接口
void AdjustDown(HPDataType* arry,size_t size,size_t parent)
{assert(arry);size_t child = 2 * parent + 1;   //確定父結(jié)點(diǎn)的左孩子的編號(hào)while (child < size)			 //child增加到大于或等于size時(shí)則調(diào)整結(jié)束{if (child + 1 < size && arry[child + 1] < arry[child]) //確定左右孩子中較小的孩子結(jié)點(diǎn){++child;}if ( arry[child] < arry[parent])//父結(jié)點(diǎn)大于子結(jié)點(diǎn),則子結(jié)點(diǎn)需要上調(diào)以保持小堆的結(jié)構(gòu){Swap(arry + parent, arry + child);parent = child;				//將原子結(jié)點(diǎn)作為新的父結(jié)點(diǎn)繼續(xù)迭代過(guò)程child = 2 * parent + 1;		//繼續(xù)向下找另外一個(gè)子結(jié)點(diǎn)}else{break;						//父結(jié)點(diǎn)不大于子結(jié)點(diǎn),則堆結(jié)構(gòu)任然成立,無(wú)需調(diào)整}}
}//刪除堆頂元素
void HeapPop(HP* ptrheap)
{assert(ptrheap);Swap(ptrheap->arry, ptrheap->arry + ptrheap->size - 1); //交換堆頂與堆尾元素ptrheap->size--;										//刪除堆尾元素AdjustDown(ptrheap->arry, ptrheap->size, 0);			//將堆頂元素進(jìn)行向下調(diào)整以保持堆的數(shù)據(jù)結(jié)構(gòu)
}

我們只需將小根堆的堆元素上下調(diào)整算法接口中的子父結(jié)點(diǎn)值大小比較符號(hào)改為大于號(hào)即可實(shí)現(xiàn)大根堆

10.結(jié)語(yǔ)

• 本文的核心:通過(guò)堆元素的上下調(diào)整算法接口完成堆的構(gòu)建和刪空(并分析過(guò)程的時(shí)間復(fù)雜度)
• 堆元素上下調(diào)整算法接口在后續(xù)的堆排序和TopK問(wèn)題中還會(huì)直接用到
• 堆的高效性來(lái)源于如下數(shù)學(xué)思想:利用指數(shù)級(jí)展開(kāi)的數(shù)據(jù)結(jié)構(gòu)模型實(shí)現(xiàn)對(duì)數(shù)級(jí)回溯,從而降低了排序和查找的時(shí)間復(fù)雜度(不得不說(shuō)前人的創(chuàng)造真的是無(wú)可比擬)

?

?

?

?

?

?

?