1 什么是堆

• 簡單來說堆是二叉樹的一種表示方式,它在邏輯上就是一顆完全二叉樹,它在物理上卻是一個數組,這么說可能有點抽象,我們原來學習的棧,隊列,或者說順序表,鏈表等等,他們的邏輯結構和物理結構是相同或者相似的,就會比較好理解一些,而在堆這里物理結構和邏輯結構截然不同,理解相對就會比較抽象一些,我們接著看

1.1 堆的邏輯結構和物理結構

• 邏輯結構即我們想象的結構,就比方說我們早上在圖書館排隊的時候,放個包在圖書館門口,人可能都不見了,這個時候我們邏輯上認為我們在排隊,但物理上我們同學就可能在吃早飯上廁所啥的
• 邏輯上我們想象這個數組是一個二叉樹,并且像二叉樹一樣訪問子節點或者父節點

• 比方說我給出以下數組,它在邏輯上是這樣表示的(當然哈,指針其實是不存在的,只是邏輯上我們看作其是父子關系):
  

1.2 堆的訪問

• 既然堆是一顆貨真價實的二叉樹,可我們怎么像二叉樹一樣,通過父/子節點訪問子/父節點呢?

1. 通過父節點訪問子節點：
   • 我們假設父節點的下標為3,我們想訪問它的子節點,只需要把 父節點的下標 * 2 + 1 或 父節點的下標 * 2 + 2 即可 即 7 或 8
2. 通過子節點訪問父節點
   • 我們假設子節點的下標為7,我們想訪問它的父節點,只需要把 (子節點的下標 - 1) / 2 即可 即 3
   • 我們假設子節點的下表為8,我們想訪問它的父節點,依舊只需要把 (子節點的下標 - 1) / 2 即可 依舊是 3

1.3 堆為什么物理結構上要用數組?

• 事實上學習堆是為了學習堆排序打基礎,在堆排序中,有時候需要頻繁交換頭尾節點,如果用數組,找節點就會方便很多,交換函數也很好寫,效率會更高,用鏈表要不斷去遍歷,或者專門寫個尾指針妥協,很沒必要
• 其次,如果我們用鏈式存儲的話,訪問子/父節點需要定義3個指針,需要多開辟很多空間
• 堆一定是完全二叉樹,用數組存放會很方便,其中不會有空節點,所有數據存儲都是連續的

1.4 堆數據上的特點

• 堆必須要始終滿足滿足:父節點值比子節點小或者父節點始終比子節點大
• 我們稱父節點值始終比子節點小的堆為小堆/小根堆
• 我們稱父節點值始終比子節點大的堆為大堆/大根堆

例如:
1.大堆:

2.小堆:

2 堆的實現

2.1 堆類型定義

//堆在物理上是一個數組,我們直接按數組的定義方式就行
//類型定義
typedef int HPDataType;typedef struct Heap 
{HPDataType* data;int size;int capa;
}Heap;

2.2 需要實現的接口

//交換函數
void Swap(HPDataType* x, HPDataType* y);//向上調整(小堆)
void AdjustUp(HPDataType* data, int child);//向下調整(小堆)
void AdjustDown(HPDataType* data, int size, int father);//初始化堆
void HPInit(Heap* php);//銷毀堆
void HPDestroy(Heap* php);//堆插入
void HPPush(Heap* php, HPDataType x);//堆刪除
void HPPop(Heap* php);//堆頂
HPDataType HPTop(Heap* php);//堆判空
bool HPEmpty(Heap* php);

2.3 初始化堆

//像順序表一樣初始化就行
//初始化堆
void HPInit(HP* php)
{assert(php);php->a = (HPdatatype*)calloc(4, sizeof(HPdatatype));if (php->a == NULL){perror("HPInit::calloc fail");exit(1);}php->capa = 4;php->size = 0;
}

2.4 銷毀堆

//同樣,像順序表一樣銷毀就行
//銷毀堆
void HPdestory(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capa = 0;php->size = 0;
}

2.5 堆判空

//堆判空
bool HPEmpty(HP* php)
{assert(php);   //判空return php->size == 0;    //size是0就返回true
}

2.6 交換函數

//只是完成數據在空間上的交換
//交換函數
void Swap(HPdatatype* x, HPdatatype* y)
{HPdatatype tmp = *x;*x = *y;*y = tmp;
}

2.7 向上調整(小堆)

• 注意這里是重點
• 向上調整會在很多地方用到，基本思想就是讓本應該在上面的節點往上挪

//向上調整(小堆)
void AdjustUp(HPdatatype* a, int child)
{assert(a);//判空int father = (child - 1) / 2;//推算出父節點的位置while (father < child && a[father] > a[child])      //只要子節點比父節點還小，就讓子節點和父節點交換{								               		//重復此步驟直到子節點大于父節點或者子節點和自己比較Swap(&a[child], &a[father]); child = father;father = (child - 1) / 2;}
}

2.8 向下調整(小堆)

• 注意這里是重點
• 向下調整同樣會在很多地方用到

//向下調整(小堆)
void AdjustDown(HPdatatype* a, int size, int father)
{assert(a);//判空int child = (father * 2) + 1;      //先假設比較小的是左子節點if (child + 1 < size && a[child] > a[child + 1])        //如果右子節點比左子節點大,注意要判斷一下子節點是否會超范圍{child++;        //把child改成右子節點}while (child < size && a[father] > a[child] )    //如果父節點一直比子節點大就不斷交換下移{                                                //直到子節點超出size范圍或者父節點比子節點小就停下Swap(&a[father], &a[child]);     //交換father = child;              //重新找到父節點(交換后的父節點應該是原來的子節點的位置)child = (father * 2) + 1;    //重新定位子節點if (child + 1 < size && a[child] > a[child + 1])    //如法炮制{child++;}}
}

2.9 堆插入

• 堆插入一般插入到末尾,因為末尾很空,啥也沒有,比較好插入,插在其他地方還得先挪動才可以插入

//堆插入
void HPPush(HP* php, HPdatatype x)
{assert(php);   //判空//堆擴容,這里像數組一樣擴容就行if (php->capa == php->size){HPdatatype* tmp = (HPdatatype*)realloc(php->a, 2 * php->size * sizeof(HPdatatype));if (tmp == NULL){perror("HPPush::realloc fail");exit(1);}php->a = tmp;php->capa *= 2;}php->a[php->size] = x;    //將要插入的數據放到堆低AdjustUp(php->a, php->size);      //通過向上調整找到這個數據本應該在的位置php->size++;      //別忘了讓size++
}

2.10 堆刪除

• 堆刪除一般刪除堆頂的數據,但不能簡單地把堆頂置為空,而是要和末尾數據交換,再一點點下調

//堆刪除
void HPPop(HP* php)
{assert(php);     //判空if (!HPEmpty(php))    //如果堆不是空堆{Swap(&php->a[0], &php->a[php->size - 1]);   //交換堆頂和末尾的數據AdjustDown(php->a, php->size - 1, 0);    //將堆頂的數據向下挪到合適的位置php->size--;   //別忘了size--}
}

2.11 //堆頂

//取堆頂
HPdatatype HPTop(HP* php)
{assert(php);    //判空return HPEmpty(php) ? -1 : php->a[0];   //返回堆頂數據
}

---

• 完整代碼在最下面哦

佬!都看到這了,如果覺得有幫助的話一定要點贊啊佬 >v< !!!
放個卡密在這,感謝各位能看到這兒啦!

---

3 完整代碼

3.1 heap.h

#pragma once//頭文件聲明
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>//類型定義
typedef int HPdatatype;typedef struct Heap
{HPdatatype* a;int size;int capa;
}HP;//函數申明//交換函數
void Swap(HPDataType* x, HPDataType* y);//向上調整(小堆)
void AdjustUp(HPDataType* data, int child);//向下調整(小堆)
void AdjustDown(HPDataType* data, int size, int father);//初始化堆
void HPInit(Heap* php);//銷毀堆
void HPDestroy(Heap* php);//堆插入
void HPPush(Heap* php, HPDataType x);//堆刪除
void HPPop(Heap* php);//堆頂
HPDataType HPTop(Heap* php);//堆判空
bool HPEmpty(Heap* php);

3.2 heap.c

#include "heap.h"//初始化堆
void HPInit(HP* php)
{assert(php);php->a = (HPdatatype*)calloc(4, sizeof(HPdatatype));if (php->a == NULL){perror("HPInit::calloc fail");exit(1);}php->capa = 4;php->size = 0;
}//銷毀堆
void HPdestory(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capa = 0;php->size = 0;
}//堆判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}//取堆頂
HPdatatype HPTop(HP* php)
{assert(php);return HPEmpty(php) ? -1 : php->a[0];
}//交換
void Swap(HPdatatype* x, HPdatatype* y)
{HPdatatype tmp = *x;*x = *y;*y = tmp;
}//向上調整(小堆)
void AdjustUp(HPdatatype* a, int child)
{assert(a);int father = (child - 1) / 2;while (father < child && a[father] > a[child]){Swap(&a[child], &a[father]);child = father;father = (child - 1) / 2;}
}//堆插入
void HPPush(HP* php, HPdatatype x)
{assert(php);//堆擴容if (php->capa == php->size){HPdatatype* tmp = (HPdatatype*)realloc(php->a, 2 * php->size * sizeof(HPdatatype));if (tmp == NULL){perror("HPPush::realloc fail");exit(1);}php->a = tmp;php->capa *= 2;}php->a[php->size] = x;AdjustUp(php->a, php->size);php->size++;
}//向下調整(小堆)
void AdjustDown(HPdatatype* a, int size, int father)
{assert(a);int child = (father * 2) + 1;if (child + 1 < size && a[child] > a[child + 1]){child++;}while (child < size && a[father] > a[child] ){Swap(&a[father], &a[child]);father = child;child = (father * 2) + 1;if (child + 1 < size && a[child] > a[child + 1]){child++;}}
}//堆刪除
void HPPop(HP* php)
{assert(php);if (!HPEmpty(php)){Swap(&php->a[0], &php->a[php->size - 1]);AdjustDown(php->a, php->size - 1, 0);php->size--;}
}