C語言順序結(jié)構(gòu)的二叉樹之堆排序
一、堆
1. 概念與分類
上一期我們提到，二叉樹的實(shí)現(xiàn)既可以用順序結(jié)構(gòu)，也可以用鏈?zhǔn)浇Y(jié)構(gòu)。本篇我們來學(xué)習(xí)順序結(jié)構(gòu)的二叉樹，起個(gè)新名字——堆（heap）。
堆是完全二叉樹，它的底層是順序結(jié)構(gòu)的數(shù)組，具有二叉樹特性的同時(shí)，還有一些其他性質(zhì)：
堆分為大堆和小堆（或稱為大根堆、小根堆）：
- 大堆：大堆的每個(gè)結(jié)點(diǎn)的存儲(chǔ)值都 >= 它的子結(jié)點(diǎn)的存儲(chǔ)值。
- 小堆：小堆的每個(gè)結(jié)點(diǎn)的存儲(chǔ)值都 <= 它的子結(jié)點(diǎn)的存儲(chǔ)值。
譬如，在一個(gè)大堆中，某一個(gè)父結(jié)點(diǎn)的值為20，則它的子結(jié)點(diǎn)的值一定<=20；在一個(gè)小堆中，某一個(gè)父結(jié)點(diǎn)的值為20，則它的子結(jié)點(diǎn)的值一定>=20。
左孩子和右孩子的值的大小關(guān)系不確定。
換句話說，一個(gè)堆一定是大堆或小堆。以下的二叉樹，既不是大堆也不是小堆，它們就不是堆：
2. 結(jié)構(gòu)與性質(zhì)
定義數(shù)據(jù)結(jié)構(gòu)堆：
typedef struct Heap
{
HPDataType* arr;
int size;
int capacity;
}HP;
上面的畫圖是用邏輯結(jié)構(gòu)表示堆，用存儲(chǔ)結(jié)構(gòu)表示堆就要用到數(shù)組了，牢記二叉樹結(jié)點(diǎn)的編號(hào)方式：從上到下，從左到右：
不難推斷，堆的數(shù)組中有下列性質(zhì)：
- 大堆的首元素（根結(jié)點(diǎn)）是整個(gè)堆的最大值，小堆的首元素（根結(jié)點(diǎn)）是整個(gè)堆的最小值。
- 若子結(jié)點(diǎn)的下標(biāo)為i，則它的父結(jié)點(diǎn)是(i-1)/2。
- 若父結(jié)點(diǎn)的下標(biāo)為i，則它的左孩子是2i+1，右孩子是2i+2。結(jié)點(diǎn)個(gè)數(shù)是n，2i+1 >= n 說明無左孩子，2i+2 >= n 說明無右孩子。
順帶給出堆的初始化和銷毀方法，以及后面要用到的交換兩個(gè)變量值的方法：
void HPInit(HP* php)
{
assert(php);
php->arr = NULL;
php->size = php->capacity = 0;
}
void HPDestory(HP* php)
{
assert(php);
if (php->arr != NULL)
free(php->arr);
php->arr = NULL;
php->size = php->capacity = 0;
}
void Swap(HPDataType* px, HPDataType* py)
{
HPDataType tmp = *px;
*px = *py;
*py = tmp;
}
3. 入堆
想要把一個(gè)新的數(shù)據(jù)插入堆，分為兩步：
- 把它插入堆數(shù)組末尾
- 僅僅插入數(shù)據(jù)后，可能會(huì)破壞堆的性質(zhì)，所以還要進(jìn)行“向上調(diào)整”操作：將新插入結(jié)點(diǎn)順著其雙親往上調(diào)整位置至滿足大堆或小堆的位置。
我們以下面一個(gè)小堆為例，插入一個(gè)新數(shù)據(jù)10，如果它小于其父結(jié)點(diǎn)（不符合小堆），兩者交換。再和新父結(jié)點(diǎn)比較，如果小于交換……直到滿足小堆：
所以，我們要知道向上調(diào)整算法：它有兩個(gè)參數(shù)：要被調(diào)整的堆數(shù)組，要調(diào)整位置的結(jié)點(diǎn)的下標(biāo)：
void AdjustUp(HPDataType* arr, int child)
{
int parent = (child - 1) / 2; //找這個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)
while (child > 0)
{
//調(diào)整的是小堆: <
//調(diào)整的是大堆: >
if (arr[child] < arr[parent])
{
Swap(&arr[child], &arr[parent]);
child = parent;
parent = (child - 1) / 2;
}
else //新數(shù)據(jù)已經(jīng)到了對(duì)的位置
{
break;
}
}
}
這樣，我們就能實(shí)現(xiàn)入堆操作了：
void HPPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity) //空間不夠則需增容
{
int newcapacity = php->capacity == 0 ? 5 : 2 * php->capacity;
HPDataType* tmp = (HPDataType*)realloc(php->arr, newcapacity * sizeof(HPDataType));
if (tmp == NULL)
{
perror("relloc fail!");
exit(1);
}
php->arr = tmp;
php->capacity = newcapacity;
}
php->arr[php->size] = x; //新數(shù)據(jù)插到末尾，即下標(biāo)為size的位置
AdjustUp(php->arr, php->size);
php->size++;
}
測(cè)試：
我們來實(shí)現(xiàn)一個(gè)小堆，亂序給一些數(shù)：
將打印結(jié)果排列成堆的邏輯結(jié)構(gòu)看看，發(fā)現(xiàn)確實(shí)是正確的小堆：
4. 出堆
我們所謂的出堆，出的并不是數(shù)組末尾數(shù)據(jù)，出的是第一個(gè)數(shù)據(jù)——堆的根結(jié)點(diǎn)。但是，直接除去數(shù)組首元素，再將后面元素的下標(biāo)全體前挪，會(huì)使堆的所有結(jié)點(diǎn)位置關(guān)系“大亂套”，再想調(diào)整可就麻煩了。
因此，我們選擇這樣的出堆定元素方法：先將堆頂數(shù)據(jù)和堆的最后一個(gè)數(shù)據(jù)交換，size- -把數(shù)組末尾數(shù)據(jù)出掉，再對(duì)堆頂元素進(jìn)行“向下調(diào)整”操作。相比剛才所有結(jié)點(diǎn)位置大亂套，這樣只要調(diào)整一個(gè)結(jié)點(diǎn)的位置就好了。
向下調(diào)整算法和向上調(diào)整類似：它是比較結(jié)點(diǎn)和其較大或較小孩子的值，不斷往下交換調(diào)整位置直至滿足大堆或小堆：
向下調(diào)整算法有三個(gè)參數(shù)：要被調(diào)整的堆數(shù)組、要調(diào)整的結(jié)點(diǎn)的下標(biāo)、堆的數(shù)據(jù)個(gè)數(shù)
void AdjustDown(HPDataType* arr, int parent, int n)
{
int child = 2 * parent + 1;
while (child < n)
{
//調(diào)整的是小堆: >
//調(diào)整的是大堆: <
if (child + 1 < n && arr[child] < arr[child + 1]) //找兩個(gè)孩子中的較大/較小者
{
child++;
}
//調(diào)整的是小堆: <
//調(diào)整的是大堆: >
if (arr[child] > arr[parent])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = 2 * parent + 1;
}
else //調(diào)整完成
{
break;
}
}
}
這樣，我們就能實(shí)現(xiàn)出堆操作了：
void HPPop(HP* php)
{
assert(php);
assert(php->size != 0); //堆不能為空，否則無數(shù)據(jù)可出
Swap(&php->arr[0], &php->arr[php->size - 1]); //交換堆頂和堆尾數(shù)據(jù)
php->size--; //將堆尾數(shù)據(jù)出掉
AdjustDown(php->arr, 0, php->size);
}
測(cè)試：
我們來實(shí)現(xiàn)一個(gè)大堆，亂序給一些數(shù)，再進(jìn)行一次出堆：
分析邏輯結(jié)構(gòu)，可以看到大堆實(shí)現(xiàn)成功，出堆也沒有問題：
二、堆排序
堆排序是一種排序方法，不是借助堆的數(shù)據(jù)結(jié)構(gòu)，而是利用堆的思想進(jìn)行排序：
一個(gè)n個(gè)元素的數(shù)組，假如想排升序，就將數(shù)組建成一個(gè)大堆，堆頂是最大值，將堆頂和堆尾交換，下標(biāo)n-1處就是最大值了；我們?cè)侔亚皀-1個(gè)數(shù)據(jù)調(diào)整成大堆，此時(shí)堆頂就是第二大的數(shù)據(jù)，堆頂和堆尾交換，下標(biāo)n-2處就是第二大值了……直至排序完成。
相反地，想排成降序就建小堆，道理是一樣的，我們下面就以建成大堆為例。
堆排序的關(guān)鍵在于一開始建堆的方法，可以分為向下調(diào)整建堆和向上調(diào)整建堆：
void HPCreat_Down(int* arr, int n) //向下調(diào)整算法建堆
{
//從尾結(jié)點(diǎn)的父結(jié)點(diǎn)開始往上遍歷，每一個(gè)結(jié)點(diǎn)都進(jìn)行向下調(diào)整
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, i, n);
}
}
void HPCreat_Up(int* arr, int n) //向上調(diào)整算法建堆
{
//從第一個(gè)結(jié)點(diǎn)開始往下遍歷，每一個(gè)結(jié)點(diǎn)都進(jìn)行向上調(diào)整
for (int i = 0; i < n; i++)
{
AdjustUp(arr, i);
}
}
//注：建的是大堆還是小堆，取決于AdjustUp和AdjustDown函數(shù)中的大于還是小于號(hào)，上面提到過
知道了建堆方式后，就能實(shí)現(xiàn)堆排序了：
void HeapSort(int* arr, int n)
{
HPCreat_Down(arr, n);
//或HPCreat_Up(arr, n);
int end = n - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
AdjustDown(arr, 0, end); //對(duì)新堆頂進(jìn)行向下調(diào)整，以保證堆的性質(zhì)
end--;
}
}
測(cè)試：
很順利。
關(guān)于兩種建堆方式的時(shí)間復(fù)雜度：
推導(dǎo)需要用到數(shù)列相關(guān)定理公式，我就不再證明了，可以直接記住結(jié)果：
- 向下調(diào)整建堆：T(n) = n - log2(n+1)，O(n)
- 向上調(diào)整建堆：T(n) = (n+1) [log2(n+1) - 2] + 2，O(n*logn)
可見，向下調(diào)整建堆算法更好一些。
三、堆排序的應(yīng)用——TOP-K問題
TOP-K問題，即求n個(gè)數(shù)據(jù)中前K個(gè)最大值或最小值，一般情況下n都很大且n >> k。
我們能想到的最簡單的方法就是排序了，但是如果數(shù)據(jù)量太大，數(shù)據(jù)不能一下子全部加載到內(nèi)存中，排序就不可取了。最佳的方式就是用堆來解決，思路為：
- 取前k個(gè)數(shù)據(jù)建堆，遍歷剩下的n-k個(gè)數(shù)據(jù)跟堆頂比較。
- 如果找的是前k個(gè)最大值，就建小堆。若第k+1個(gè)數(shù)比堆頂大，就用它替換堆頂，再調(diào)整堆，再比較第k+2個(gè)數(shù)和堆頂……遍歷完，最后堆中的k個(gè)數(shù)就是n個(gè)數(shù)里面前的k個(gè)最大值了。
- 如果找的是前k個(gè)最小值，就建大堆。若第k+1個(gè)數(shù)比堆頂小，就用它替換堆頂，再調(diào)整堆，再比較第k+2個(gè)數(shù)和堆頂……遍歷完，最后堆中的k個(gè)數(shù)就是n個(gè)數(shù)里面前的k個(gè)最小值了。
應(yīng)該很好理解吧。
舉個(gè)栗子，我先來造十萬個(gè)數(shù)據(jù)，保存到一個(gè)文本文件data.txt中
void CreatData()
{
srand(time(0));
FILE* file = fopen("data.txt", "w");
if (file == NULL)
{
perror("fopen fail!");
exit(2);
}
for (int i = 0; i < 100000; i++)
{
int x = (rand() + i) % 100000 + 1;
fprintf(file, "%d\n", x);
}
fclose(file);
}
最后來實(shí)現(xiàn)TOP_K算法（以找前k個(gè)最小值為例）：
void Top_K()
{
int k;
printf("請(qǐng)輸入K:");
scanf("%d", &k);
FILE* file = fopen("data.txt", "r");
if (file == NULL)
{
perror("fopen fail!");
exit(2);
}
int* maxHeap = (int*)malloc(sizeof(int) * k);
if (maxHeap == NULL)
{
perror("malloc fail!");
exit(1);
}
for (int i = 0; i < k; i++)
{
//先將前k個(gè)數(shù)存到maxHeap中
fscanf(file, "%d", &maxHeap[i]);
}
HPCreat_Down(maxHeap, k); //找前k個(gè)最小值，建大堆
//遍歷剩下的數(shù)
int x;
while (fscanf(file, "%d", &x) != EOF) //fscanf文件讀取結(jié)束會(huì)返回EOF
{
//誰小誰當(dāng)堆頂
if (x < maxHeap[0])
{
maxHeap[0] = x;
AdjustDown(maxHeap, 0, k);
}
}
fclose(file);
//處理完成，打印結(jié)果
for (int i = 0; i < k; i++)
{
printf("%d ", maxHeap[i]);
}
}
測(cè)試：
可以看到，每次輸入一個(gè)k，都能找到前k個(gè)最小值，只不過不是按大小順序輸出的。順帶一提，這個(gè)算法的時(shí)間復(fù)雜度O(n) = k + (n - k)log2k
總結(jié)
到此這篇關(guān)于C語言順序結(jié)構(gòu)的二叉樹之堆排序的文章就介紹到這了,更多相關(guān)C語言順序結(jié)構(gòu)堆排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
在c++Template中很多地方都用到了typename與class這兩個(gè)關(guān)鍵字，而且好像可以替換，是不是這兩個(gè)關(guān)鍵字完全一樣呢?下面這篇文章主要給大家介紹了關(guān)于c++模板中class與typename的相關(guān)資料，需要的朋友可以參考下。2017-07-07
dev-c++創(chuàng)建lib(靜態(tài)鏈接庫)文件的實(shí)現(xiàn)步驟
本文主要介紹了dev-c++創(chuàng)建lib(靜態(tài)鏈接庫)文件的實(shí)現(xiàn)步驟，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06
這篇文章主要介紹了簡單舉例說明C++中break和continue語句的用法,是C++入門學(xué)習(xí)中的基礎(chǔ)只是,需要的朋友可以參考下2015-09-09
這篇文章主要為大家詳細(xì)介紹了如何通過C語言實(shí)現(xiàn)和電腦玩剪刀石頭布游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-11-11
C語言輸入一個(gè)數(shù)判斷是否為素?cái)?shù)的多種方法
素?cái)?shù)是只能被1和它自己本身整除,不能被其他自然數(shù)整除的大于1的正整數(shù),下面這篇文章主要給大家介紹了關(guān)于C語言輸入一個(gè)數(shù)判斷是否為素?cái)?shù)的多種方法,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-04-04
埃拉托斯特尼篩法，簡稱埃氏篩或愛氏篩，是一種由希臘數(shù)學(xué)家埃拉托斯特尼所提出的一種簡單檢定素?cái)?shù)的算法。本文將利用這一算法實(shí)現(xiàn)求解素?cái)?shù)，感興趣的可以了解一下2023-01-01
冒泡排序是最基礎(chǔ)的排序算法之一,它的核心思想是通過相鄰元素的比較和交換,將較大的元素逐步冒泡到數(shù)組的末尾,今天我們來分析三種不同的冒泡排序?qū)崿F(xiàn)方式,每種都有其獨(dú)特之處,需要的朋友可以參考下2025-10-10
之前看到本站給大家分享了一則C語言實(shí)現(xiàn)的簡單日歷，就手癢了，也想自己寫一個(gè)，既然有簡單了，那咱寫個(gè)稍微復(fù)雜點(diǎn)的，多功能的吧。呵呵，玩笑玩笑2015-03-03
這篇文章主要介紹了C++直接初始化與復(fù)制初始化的區(qū)別深入解析,是很多C++初學(xué)者需要深入了解的重要概念,需要的朋友可以參考下2014-09-09
深入解析C++11?lambda表達(dá)式/包裝器/線程庫
這篇文章主要介紹了C++11?lambda表達(dá)式/包裝器/線程庫的相關(guān)知識(shí)，本文通過示例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-05-05