目錄

前言

一.堆的介紹

1.堆的本質(zhì)

2.堆的分類

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

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

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

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

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

4.堆元素插入接口測試

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

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

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

7.堆元素刪除接口測試

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

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

10.結(jié)語

?

?

前言

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

一.堆的介紹

1.堆的本質(zhì)

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

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

堆的圖解:

• 結(jié)點中的數(shù)據(jù)存儲在相應(yīng)下標的數(shù)組元素空間中

2.堆的分類

堆的兩個類型：

1. 大根堆:在大根堆中任何子結(jié)構(gòu)的父結(jié)點中存儲的值大于其左右孩子結(jié)點中存儲的值(即任何一條連通路徑上從上往下滿足降序排列)
2. 小根堆:在小根堆中任何子結(jié)構(gòu)的父結(jié)點中存儲的值小于其左右孩子結(jié)點中存儲的值(即任何一條連通路徑上從上往下滿足升序排列)

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

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

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

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

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

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

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

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

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

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

• 基礎(chǔ)接口的實現(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);
  }
  
  
  //返回堆元素個數(shù)的接口
  size_t HeapSize(HP* ptrheap)
  {
  	assert(ptrheap);
  	return ptrheap->size;
  }
  
  
  //返回堆頂元素的接口
  HPDataType HeapTop(HP* ptrheap)
  {
  	assert(!HeapEmpty(ptrheap));
  	return ptrheap->arry[0];
  }

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

  

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

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

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

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

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

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

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

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

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

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

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

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é)點的編號
{
	assert(arry);
	size_t parent = (child - 1) / 2;    //算出父結(jié)點的數(shù)組下標(堆編號)
	while (child > 0)			        //child減小到0時則調(diào)整結(jié)束(堆尾元素已調(diào)到堆頂)
	{
		if (arry[child] < arry[parent]) //父結(jié)點大于子結(jié)點,則子結(jié)點需要上調(diào)以保持小堆的結(jié)構(gòu)
		{
			Swap(arry + child, arry+parent);
			child = parent;				//將原父結(jié)點作為新的子結(jié)點繼續(xù)迭代過程
			parent = (child - 1) / 2;	//算出父結(jié)點的數(shù)組下標(堆編號)
		}
		else
		{
			break;						//父結(jié)點不大于子結(jié)點,則堆結(jié)構(gòu)恢復(fù),無需再調(diào)整
		}
	}
}

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

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

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

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

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

void HeapPush(HP* ptrheap, HPDataType x)

// 插入一個小堆元素的接口
// 插入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ù)組容量檢查,容量不夠則擴容
	{
		size_t newcapacity = (0 == ptrheap->capacity) ? 4 : 2 * ptrheap->capacity;
        //注意容量為0則將堆區(qū)數(shù)組容量調(diào)整為4
		HPDataType* tem = (HPDataType*)realloc(ptrheap->arry, newcapacity*sizeof(HPDataType)); //空間不夠則擴容
		assert(tem);             //檢查擴容是否成功
		ptrheap->arry = tem;     //將堆區(qū)地址賦給結(jié)構(gòu)體中的指針成員
		ptrheap->capacity = newcapacity; //容量標記更新
	}
	ptrheap->arry[ptrheap->size] = x;			//元素尾插入堆
	ptrheap->size++;


	//將尾插的元素進行向上調(diào)整以保持堆的數(shù)據(jù)結(jié)構(gòu)(復(fù)用元素向上調(diào)整接口)
	AdjustUp(ptrheap->arry, ptrheap->size - 1); //根據(jù)完全二叉樹的結(jié)構(gòu)特點可知堆尾元素                
                                                //在二叉樹中編號為size-1
}

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

4.堆元素插入接口測試

現(xiàn)在我們試著用HeapPush接口來構(gòu)建六個元素的小堆,并將堆打印出來觀察其邏輯結(jié)構(gòu):

• 主函數(shù)代碼:

  int main ()
  {
      HP hp;              //創(chuàng)建一個堆結(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);     //打印堆元素
  }

  

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

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

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

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

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

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

• 先將堆頂元素與堆尾元素進行交換,然后令維護堆的結(jié)構(gòu)體中的size(記錄堆元素個數(shù)的成員變量)減一(相當于移除堆尾元素)
• 然而原來的堆尾元素被交換到堆頂位置后,小根堆的數(shù)據(jù)結(jié)構(gòu)會被破壞,因此我們需要將堆頂元素進行向下調(diào)整操作:
• 堆頂元素向下調(diào)整圖解演示:
• 同樣不難分析出,任何堆頂元素向下調(diào)整的過程都是在堆頂?shù)蕉盐苍氐?/strong>連通路徑上進行的(該路徑長度數(shù)量級為logk)(k為當前樹結(jié)點總個數(shù))):
• 通過算法分析我們可以設(shè)計一個堆元素向下調(diào)整算法接口:??

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

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

堆元素向下調(diào)整算法接口實現(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é)點的左孩子的編號
	while (child < size)			 //child增加到大于或等于size時說明被調(diào)整元素被調(diào)整到了葉結(jié)點上,調(diào)整過程結(jié)束
	{
		if (child + 1 < size && arry[child + 1] < arry[child])//確定左右孩子中較小的孩子結(jié)點
		{
			++child;   //條件成立說明右孩子較小,child更新為右孩子編號
		}
		if ( arry[child] < arry[parent])//父結(jié)點大于子結(jié)點,則父結(jié)點需要下調(diào)以保持小堆的結(jié)構(gòu)
		{
			Swap(arry + parent, arry + child);//父子結(jié)點進行值交換
			parent = child;				      //將原來的子結(jié)點作為新的父結(jié)點繼續(xù)迭代過程
			child = 2 * parent + 1;		      //繼續(xù)向下找另外一個子結(jié)點
		}
		else
		{
			break;						//父結(jié)點不大于子結(jié)點,則小堆結(jié)構(gòu)成立,無需繼續(xù)調(diào)整
		}
	}
}

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

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

• 有了堆元素向下調(diào)整算法接口我們就可以實現(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);    //將堆頂元素進行向下調(diào)整以保持堆的數(shù)據(jù)結(jié)構(gòu)
  }

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

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