C語言順序結(jié)構(gòu)的二叉樹之堆排序
一、堆
1. 概念與分類
上一期我們提到，二叉樹的實現(xiàn)既可以用順序結(jié)構(gòu)，也可以用鏈式結(jié)構(gòu)。本篇我們來學習順序結(jié)構(gòu)的二叉樹，起個新名字——堆（heap）。
堆是完全二叉樹，它的底層是順序結(jié)構(gòu)的數(shù)組，具有二叉樹特性的同時，還有一些其他性質(zhì)：
堆分為大堆和小堆（或稱為大根堆、小根堆）：
- 大堆：大堆的每個結(jié)點的存儲值都 >= 它的子結(jié)點的存儲值。
- 小堆：小堆的每個結(jié)點的存儲值都 <= 它的子結(jié)點的存儲值。
譬如，在一個大堆中，某一個父結(jié)點的值為20，則它的子結(jié)點的值一定<=20；在一個小堆中，某一個父結(jié)點的值為20，則它的子結(jié)點的值一定>=20。
左孩子和右孩子的值的大小關(guān)系不確定。
換句話說，一個堆一定是大堆或小堆。以下的二叉樹，既不是大堆也不是小堆，它們就不是堆：
2. 結(jié)構(gòu)與性質(zhì)
定義數(shù)據(jù)結(jié)構(gòu)堆：
typedef struct Heap
{
HPDataType* arr;
int size;
int capacity;
}HP;
上面的畫圖是用邏輯結(jié)構(gòu)表示堆，用存儲結(jié)構(gòu)表示堆就要用到數(shù)組了，牢記二叉樹結(jié)點的編號方式：從上到下，從左到右：
不難推斷，堆的數(shù)組中有下列性質(zhì)：
- 大堆的首元素（根結(jié)點）是整個堆的最大值，小堆的首元素（根結(jié)點）是整個堆的最小值。
- 若子結(jié)點的下標為i，則它的父結(jié)點是(i-1)/2。
- 若父結(jié)點的下標為i，則它的左孩子是2i+1，右孩子是2i+2。結(jié)點個數(shù)是n，2i+1 >= n 說明無左孩子，2i+2 >= n 說明無右孩子。
順帶給出堆的初始化和銷毀方法，以及后面要用到的交換兩個變量值的方法：
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. 入堆
想要把一個新的數(shù)據(jù)插入堆，分為兩步：
- 把它插入堆數(shù)組末尾
- 僅僅插入數(shù)據(jù)后，可能會破壞堆的性質(zhì)，所以還要進行“向上調(diào)整”操作：將新插入結(jié)點順著其雙親往上調(diào)整位置至滿足大堆或小堆的位置。
我們以下面一個小堆為例，插入一個新數(shù)據(jù)10，如果它小于其父結(jié)點（不符合小堆），兩者交換。再和新父結(jié)點比較，如果小于交換……直到滿足小堆：
所以，我們要知道向上調(diào)整算法：它有兩個參數(shù)：要被調(diào)整的堆數(shù)組，要調(diào)整位置的結(jié)點的下標：
void AdjustUp(HPDataType* arr, int child)
{
int parent = (child - 1) / 2; //找這個結(jié)點的父結(jié)點
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)到了對的位置
{
break;
}
}
}
這樣，我們就能實現(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ù)插到末尾，即下標為size的位置
AdjustUp(php->arr, php->size);
php->size++;
}
測試：
我們來實現(xiàn)一個小堆，亂序給一些數(shù)：
將打印結(jié)果排列成堆的邏輯結(jié)構(gòu)看看，發(fā)現(xiàn)確實是正確的小堆：
4. 出堆
我們所謂的出堆，出的并不是數(shù)組末尾數(shù)據(jù)，出的是第一個數(shù)據(jù)——堆的根結(jié)點。但是，直接除去數(shù)組首元素，再將后面元素的下標全體前挪，會使堆的所有結(jié)點位置關(guān)系“大亂套”，再想調(diào)整可就麻煩了。
因此，我們選擇這樣的出堆定元素方法：先將堆頂數(shù)據(jù)和堆的最后一個數(shù)據(jù)交換，size- -把數(shù)組末尾數(shù)據(jù)出掉，再對堆頂元素進行“向下調(diào)整”操作。相比剛才所有結(jié)點位置大亂套，這樣只要調(diào)整一個結(jié)點的位置就好了。
向下調(diào)整算法和向上調(diào)整類似：它是比較結(jié)點和其較大或較小孩子的值，不斷往下交換調(diào)整位置直至滿足大堆或小堆：
向下調(diào)整算法有三個參數(shù)：要被調(diào)整的堆數(shù)組、要調(diào)整的結(jié)點的下標、堆的數(shù)據(jù)個數(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]) //找兩個孩子中的較大/較小者
{
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;
}
}
}
這樣，我們就能實現(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);
}
測試：
我們來實現(xiàn)一個大堆，亂序給一些數(shù)，再進行一次出堆：
分析邏輯結(jié)構(gòu)，可以看到大堆實現(xiàn)成功，出堆也沒有問題：
二、堆排序
堆排序是一種排序方法，不是借助堆的數(shù)據(jù)結(jié)構(gòu)，而是利用堆的思想進行排序：
一個n個元素的數(shù)組，假如想排升序，就將數(shù)組建成一個大堆，堆頂是最大值，將堆頂和堆尾交換，下標n-1處就是最大值了；我們再把前n-1個數(shù)據(jù)調(diào)整成大堆，此時堆頂就是第二大的數(shù)據(jù)，堆頂和堆尾交換，下標n-2處就是第二大值了……直至排序完成。
相反地，想排成降序就建小堆，道理是一樣的，我們下面就以建成大堆為例。
堆排序的關(guān)鍵在于一開始建堆的方法，可以分為向下調(diào)整建堆和向上調(diào)整建堆：
void HPCreat_Down(int* arr, int n) //向下調(diào)整算法建堆
{
//從尾結(jié)點的父結(jié)點開始往上遍歷，每一個結(jié)點都進行向下調(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)整算法建堆
{
//從第一個結(jié)點開始往下遍歷，每一個結(jié)點都進行向上調(diào)整
for (int i = 0; i < n; i++)
{
AdjustUp(arr, i);
}
}
//注：建的是大堆還是小堆，取決于AdjustUp和AdjustDown函數(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); //對新堆頂進行向下調(diào)整，以保證堆的性質(zhì)
end--;
}
}
測試：
很順利。
關(guān)于兩種建堆方式的時間復(fù)雜度：
推導需要用到數(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個數(shù)據(jù)中前K個最大值或最小值，一般情況下n都很大且n >> k。
我們能想到的最簡單的方法就是排序了，但是如果數(shù)據(jù)量太大，數(shù)據(jù)不能一下子全部加載到內(nèi)存中，排序就不可取了。最佳的方式就是用堆來解決，思路為：
- 取前k個數(shù)據(jù)建堆，遍歷剩下的n-k個數(shù)據(jù)跟堆頂比較。
- 如果找的是前k個最大值，就建小堆。若第k+1個數(shù)比堆頂大，就用它替換堆頂，再調(diào)整堆，再比較第k+2個數(shù)和堆頂……遍歷完，最后堆中的k個數(shù)就是n個數(shù)里面前的k個最大值了。
- 如果找的是前k個最小值，就建大堆。若第k+1個數(shù)比堆頂小，就用它替換堆頂，再調(diào)整堆，再比較第k+2個數(shù)和堆頂……遍歷完，最后堆中的k個數(shù)就是n個數(shù)里面前的k個最小值了。
應(yīng)該很好理解吧。
舉個栗子，我先來造十萬個數(shù)據(jù)，保存到一個文本文件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);
}
最后來實現(xiàn)TOP_K算法（以找前k個最小值為例）：
void Top_K()
{
int k;
printf("請輸入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個數(shù)存到maxHeap中
fscanf(file, "%d", &maxHeap[i]);
}
HPCreat_Down(maxHeap, k); //找前k個最小值，建大堆
//遍歷剩下的數(shù)
int x;
while (fscanf(file, "%d", &x) != EOF) //fscanf文件讀取結(jié)束會返回EOF
{
//誰小誰當堆頂
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]);
}
}
測試：
可以看到，每次輸入一個k，都能找到前k個最小值，只不過不是按大小順序輸出的。順帶一提，這個算法的時間復(fù)雜度O(n) = k + (n - k)log2k
總結(jié)
到此這篇關(guān)于C語言順序結(jié)構(gòu)的二叉樹之堆排序的文章就介紹到這了,更多相關(guān)C語言順序結(jié)構(gòu)堆排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
本文主要介紹了跨平臺C++包管理利器vcpkg的實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2025-06-06
最近在看到的一個需求，本以為比較簡單，但花了不少時間，所以下面這篇文章主要給大家介紹了關(guān)于C/C++經(jīng)典實例之模擬計算器的相關(guān)資料，文中通過示例代碼介紹的非常詳細，需要的朋友可以參考借鑒，下面來一起看看吧。2017-10-10
string類是標準庫的類，并不是內(nèi)置類型，標準庫就像是我們自己定義的類差不多的，string類型對象沒有標配'\0'結(jié)尾的2013-09-09
基于C++實現(xiàn)BMI身體質(zhì)量指數(shù)計算工具
BMI（Body?Mass?Index,身體質(zhì)量指數(shù)）,也稱為體重指數(shù),是一種常用的衡量成人人體肥胖程度的指標,本文就來用C++編寫一個簡單的BMI計算工具吧2023-10-10
本篇文章對John Carmark密碼進行了分析介紹。需要的朋友參考下2013-05-05
這篇文章主要介紹了C++編程中Address-of運算符&的作用及用法,是C++入門學習中的基礎(chǔ)知識,需要的朋友可以參考下2016-01-01
在C++中，并不提倡使用#define定義一個常量。#define本質(zhì)上是一個預(yù)處理器指令，它僅僅表示使用一個串代替別一個串而已。也就是說，#define定義的常量從未被編譯器看到——它們在編譯器開始處理源碼之前就被移走了2015-08-08
FFmpeg中的libavfilter模塊(或庫)用于filter(過濾器),?filter可以有多個輸入和多個輸出,下面就跟隨小編一起簡單學習一下它的巨日使用吧2023-08-08
約瑟夫環(huán)問題(數(shù)組法)c語言實現(xiàn)
這篇文章主要介紹了約瑟夫環(huán)問題(數(shù)組法)c語言實現(xiàn)，有需要的朋友可以參考一下2013-12-12![json error: Use of overloaded operator [] is ambiguous錯誤的解決方法](http://img.jbzj.com/images/xgimg/bcimg9.png)
json error: Use of overloaded operator [] is ambiguous錯誤的解決方
今天小編就為大家分享一篇關(guān)于json error: Use of overloaded operator [] is ambiguous錯誤的解決方法，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-04-04