C語言詳解如何實現(xiàn)堆及堆的結構與接口
一、堆的結構及實現(xiàn)（重要）
1.1 二叉樹的順序結構
普通的二叉樹是不適合用數(shù)組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結構存儲。在現(xiàn)實中我們通常把堆 (一種完全二叉樹) 使用順序結構的數(shù)組來存儲，需要注意的是這里的堆和操作系統(tǒng)虛擬進程地址空間中的堆是兩回事，一個是數(shù)據(jù)結構，一個是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段。
1.2 堆的概念及結構
堆(Heap)是計算機科學中一類特殊的數(shù)據(jù)結構的統(tǒng)稱。堆通常是一個可以被看做一棵完全二叉樹的數(shù)組對象。堆總是滿足下列性質(zhì)：
- 堆中某個結點的值總是不大于或不小于其父結點的值；
- 堆總是一棵完全二叉樹。
堆是非線性數(shù)據(jù)結構，相當于一維數(shù)組，有兩個直接后繼。
【大根堆和小根堆】：
根結點最大的堆叫做大根堆，樹中所有父親都大于或等于孩子。
根結點最小的堆叫做小根堆，樹中所有父親都小于或等于孩子。
【思考】這個大根堆和小根堆有什么特點呢？
最值總在 0 號位，根據(jù)這個特點我們就可以做很多事情，比如TopK問題 (在一堆數(shù)據(jù)里面找到前 K 個最大 / 最小的數(shù))，生活中也有很多實例，比如點餐軟件中有上千家店鋪，我想選出該地區(qū)好評最多的十家川菜店，我們不用對所有數(shù)據(jù)排序，只需要取出前 K 個最大 / 最小數(shù)據(jù)。使用堆排序效率也更高。
1.3 堆的實現(xiàn)
1.3.1 堆的向下調(diào)整算法
下面給出一個數(shù)組，邏輯上看做一顆完全二叉樹。我們通過從根節(jié)點開始的向下調(diào)整算法可以把它調(diào)整成一個小堆。向下調(diào)整算法有一個前提：該節(jié)點的左右子樹必須是一個 (大 / 小) 堆，才能調(diào)整。
int array[] = { 27,15,19,18,28,34,65,49,25,37 }; // 根節(jié)點的左右子樹都是小堆
上面的數(shù)組，因為根節(jié)點的左右子樹都是小堆，所以我們從根節(jié)點開始調(diào)整，將其調(diào)成小堆。
向下調(diào)整算法思路（調(diào)成小堆）：
從根節(jié)點開始，不斷往下調(diào)。
選出根節(jié)點的左右孩子中「最小的孩子」，與「父親」進行比較。
- 如果父親小于孩子，就不需處理了，整個樹已經(jīng)是小堆了。
- 如果父親大于孩子，就跟父親交換位置，并將原來小的孩子的位置當成父親繼續(xù)向下進行調(diào)整，直到調(diào)整到葉子結點為止。
向下調(diào)整算法過程演示（調(diào)成小堆，把大的節(jié)點往下調(diào)整）：
向下調(diào)整算法代碼：
// 向下調(diào)整算法，建小堆，把大的節(jié)點往下調(diào)整
// 前提是：左右子樹都是小堆
void AdjustDown(int* a, int size, int parent)
{
// 指向左孩子，默認左孩子最小
int child = parent * 2 + 1;
while (child < size)
{
// 1. 選出左右孩子最小的那個，先判斷右孩子是否存在
if (child + 1 < size && a[child] > a[child + 1])
{
child++; // 指向右孩子
}
// 2. 最小的孩子與父親比較
if (a[parent] > a[child]) // 如果父親大于孩子
{
// 父親與孩子交換位置
Swap(&a[parent], &a[child]);
// 更新父子下標，原先最小的孩子作為父親，繼續(xù)往下調(diào)
parent = child;
child = parent * 2 + 1;
}
else // 如果父親小于孩子，說明已經(jīng)為小堆了，停止調(diào)整
{
break;
}
}
}1.3.2 向下調(diào)整算法的時間復雜度
我們以滿二叉樹計算，最壞情況下，向下調(diào)整算法最多進行滿二叉樹的高度減1次比較，則說明向下調(diào)整算法最多調(diào)整滿二叉樹的高度減1次，n 個節(jié)點的滿二叉樹高度為 log2(n+1)，估算后所以時間復雜度為 O(log2n)。
1.3.3 堆的創(chuàng)建（向下調(diào)整）
下面給出一個數(shù)組，這個數(shù)組邏輯上可以看做一顆完全二叉樹，但不是一個堆，我們需要通過算法把它構建成一個堆。如果根節(jié)點左右子樹不是一個 (大 / 小) 堆，我們應該怎么調(diào)整呢？
我們倒著調(diào)整，從下到上，從「倒數(shù)第一個非葉子節(jié)點的子樹」開始，依次遍歷完所有非葉子節(jié)點，分別對每個子樹進行「向下調(diào)整」成 (大 / 小) 堆，一直調(diào)整到「根節(jié)點」，就可以建成一個 (大 / 小) 堆。
為什么要倒著調(diào)整呢？因為這樣我們可以把「倒數(shù)第一個非葉子節(jié)點的子樹」的左右子樹看成是一個 (大 / 小) 堆，此時才能去使用向下調(diào)整算法。比如下圖中的黃色填充的子樹，3 的左子樹 6 就可以看成是一個大堆。
【實例】：將下面的數(shù)組建成一個大堆
int a[] = { 1,5,3,8,7,6 };
建堆過程演示（以建大堆為例）：從下到上，依次遍歷完所有非葉子節(jié)點，分別對每個子樹進行向下調(diào)整。
依次對 每一步 中，方框內(nèi)的樹 進行 向下調(diào)整 為一個 大堆。
建堆代碼：
// 交換函數(shù)
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
// 向下調(diào)整算法，建大堆，把小的節(jié)點往下調(diào)
// 前提是：左右子樹都是大堆
void AdjustDown(int* a, int size, int parent)
{
// 指向左孩子，默認左孩子最大
int child = parent * 2 + 1;
while (child < size)
{
// 1. 選出左右孩子最大的那個，先判斷右孩子是否存在
if (child + 1 < size && a[child] < a[child + 1])
{
child++; // 指向右孩子
}
// 2. 最大的孩子與父親比較
if (a[parent] < a[child]) // 如果父親小于孩子
{
// 父親與孩子交換位置
Swap(&a[parent], &a[child]);
// 更新父子下標，原先最大的孩子作為父親，繼續(xù)往下調(diào)
parent = child;
child = parent * 2 + 1;
}
else // 如果父親大于孩子，說明已經(jīng)為大堆了，停止調(diào)整
{
break;
}
}
}
void HeapSort(int* a, int size)
{
/* 建堆（大堆）
* 倒著調(diào)整，從倒數(shù)第一個非葉子節(jié)點的子樹進行向下調(diào)整，直到調(diào)整到根節(jié)點的樹
*/
int parent = ((size - 1) - 1) / 2; // 最后一個葉子節(jié)點的父親的下標
for (int i = parent; i >= 0; i--) // 從下到上，依次遍歷完所有子樹，分別對其進行調(diào)整
{
AdjustDown(a, size, i);
}
/* 堆排序
* 排升序 --> 建大堆，每次選出一個最大的數(shù)放到最后
* 排降序 --> 建小堆，每次選出一個最小的數(shù)放到最后
*/
// 下面是排升序：
int end = size - 1; // 記錄堆中最后一個元素的下標
while (end > 0)
{
Swap(&a[0], &a[end]); // 將堆頂元素和堆中最后一個元素交換，把最大的數(shù)(堆頂)放到最后
AdjustDown(a, end, 0); // 不看最后一個數(shù)，從根節(jié)點開始，對前面的數(shù)進行向下調(diào)整成大堆
end--;
}
}1.3.4 堆排序
排升序 --> 建大堆：
【思考】排升序，建小堆可以嗎？-- 可以是可以，但沒啥意思。
首先對 n 個數(shù)建小堆，選出最小的數(shù)，接著對剩下的 n-1 個數(shù)建小堆，選出第2小的數(shù)，不斷重復上述過程……。建 n 個數(shù)的堆時間復雜度是O(N)，所以上述操作時間復雜度為O(N2)，效率太低，尤其是當數(shù)據(jù)量大的時候，效率更低，同時堆的價值沒有被體現(xiàn)出來，還不如用直接排序。
【最佳方法】排升序，因為數(shù)字越來越大，需要找到最大的數(shù)字，得建大堆
- 首先對 n 個數(shù)建大堆。
- 將最大的數(shù)（堆頂）和最后一個數(shù)交換，把最大的數(shù)放到最后。
- 前面 n-1 個數(shù)的堆結構沒有被破壞（最后一個數(shù)不看做堆里面的），根節(jié)點的左右子樹依舊是大堆，所以我們進行一次向下調(diào)整成大堆即可選出第2大的數(shù)，放到倒數(shù)第二個位置，然后重復上述步驟……。
【時間復雜度】：建堆時間復雜度為O(N)，向下調(diào)整時間復雜度為O(log2N)，這里我們最多進行N-2次向下調(diào)整，所以堆排序時間復雜度為O(N*log2N)，效率是很高的。
排降序 --> 建小堆：
【最佳方法】排降序，因為數(shù)字越來越小，需要找到最小的數(shù)字，得建小堆
- 首先對 n 個數(shù)建小堆。
- 將最小的數(shù)（堆頂）和最后一個數(shù)交換，把最小的數(shù)放到最后。
- 前面 n-1 個數(shù)的堆結構沒有被破壞（最后一個數(shù)不看做堆里面的），根節(jié)點的左右子樹依舊是小堆，所以我們進行一次向下調(diào)整成小堆即可選出第2小的數(shù)，放到倒數(shù)第二個位置，然后重復上述步驟……。
- 【時間復雜度】：建堆時間復雜度為O(N)，向下調(diào)整時間復雜度為O(log2N)，這里我們最多進行N-2次向下調(diào)整，所以堆排序時間復雜度為O(N*log2N)，效率是很高的。
1.3.5 建堆的時間復雜度
因為堆是完全二叉樹，而滿二叉樹也是完全二叉樹，此處為了簡化使用滿二叉樹來證明，計算起來比較好算(時間復雜度本來看的就是近似值，多幾個節(jié)點不影響最終結果)：
建堆要從倒數(shù)第一個非葉子節(jié)點開始調(diào)整，也即是從倒數(shù)第二層開始調(diào)，可得出時間復雜度公式：
T ( n ) = ∑ ( 每 層 節(jié) 點 數(shù) ∗ ( 堆 的 高 度 − 當 前 層 數(shù) ) )
所以，建堆的時間復雜度為O(N)。
【上面學了那么多，這里小小總結一下】
- 堆的向下調(diào)整算法就是，在該節(jié)點左右子樹都是一個小/大堆的前提下，將以該節(jié)點為根的樹調(diào)整成一個小/大堆。
- 堆的創(chuàng)建就是倒著調(diào)整，從下到上，從倒數(shù)第一個非葉子節(jié)點的子樹開始，依次遍歷完所有子樹，分別對其進行向下調(diào)整。
- 時間復雜度：堆的向下調(diào)整算法為O(log2N)，堆的創(chuàng)建為O(N)。
二、堆的相關接口實現(xiàn)（以大堆為例）
首先新建一個工程（ 博主使用的是 VS2019 ）
- Heap.h（堆的類型定義、接口函數(shù)聲明、引用的頭文件）
- Heap.c（堆接口函數(shù)的實現(xiàn)）
- Test.c（主函數(shù)、測試堆各個接口功能）
Heap.h 頭文件代碼如下：
#pragma once
#include<stdio.h> // printf, perror
#include<stdbool.h> // bool
#include<assert.h> // assert
#include<stdlib.h> // malloc, free
#include<string.h> // memcpy
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a; // 指向動態(tài)開辟的數(shù)組
int size; // 數(shù)組中有效元素個數(shù)
int capacity; // d容量
}Heap;
// 交換函數(shù)
void Swap(HPDataType* a, HPDataType* b);
// 向下調(diào)整函數(shù)（調(diào)成大堆，把小的往下調(diào)）
void AdjustDown(HPDataType* a, int size, int parent);
// 向上調(diào)整函數(shù)（調(diào)成大堆，把大的往上調(diào)）
void AdjustUp(HPDataType* a, int child);
// 初始化堆
void HeapInit(Heap* php, HPDataType* arr, int n);
// 銷毀堆
void HeapDestroy(Heap* php);
// 插入元素（插入到堆的末尾），插入后并保持它依然是堆
void HeapPush(Heap* php, int x);
// 刪除堆頂元素，刪除后保持它依然是堆
void HeapPop(Heap* php);
// 獲取堆頂元素，也即是最值
HPDataType HeapTop(Heap* php);
// 判斷堆是否為空，為空返回true，不為空返回false
bool HeapEmpty(Heap* php);
// 獲取堆中有效元素個數(shù)
int HeapSize(Heap* php);
// 打印堆
void HeapPrint(Heap* php);2.1 堆的初始化
堆的初始化，首先需要實現(xiàn)一個向下調(diào)整算法：
// 交換函數(shù)
void Swap(HPDataType* a, HPDataType* b)
{
HPDataType tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
// 向下調(diào)整算法（調(diào)成大堆，把小的往下調(diào)）
void AdjustDown(HPDataType* a, int size, int parent)
{
// 左孩子下標，初始默認左孩子最大
int child = parent * 2 + 1;
while (child < size)
{
// 選出左右孩子最大的那個，先判斷右孩子是否存在
if (child + 1 < size && a[child] < a[child + 1])
{
child++; // 右孩子最大
}
// 最大的孩子與父親比較
if (a[parent] < a[child]) // 如果父親小于孩子
{
// 父親與孩子交換位置
Swap(&a[parent], &a[child]);
// 更新父子下標，原先最大的孩子作為父親，繼續(xù)往下調(diào)
parent = child;
child = parent * 2 + 1;
}
else // 如果父親大于孩子，說明已經(jīng)為大堆了，停止調(diào)整
{
break;
}
}
}堆的初始化代碼：
// 初始化堆，用一個給定的數(shù)組來初始化
void HeapInit(Heap* php, HPDataType* arr, int n)
{
assert(php); // 斷言
// 動態(tài)開辟n個空間
php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (php->a == NULL)
{
perror("malloc");
exit(-1);
}
// 把給定數(shù)組的各元素值拷貝過去
memcpy(php->a, arr, sizeof(HPDataType) * n);
php->size = php->capacity = n;
// 建堆(建大堆）
int parent = ((php->size - 1) - 1) / 2; // 倒數(shù)第一個非葉子節(jié)點下標
for (int i = parent; i >= 0; i--) // 從下到上，依次遍歷完所有子樹，分別對其進行調(diào)整
{
AdjustDown(php->a, php->size, i);
}
}2.2 堆的銷毀
// 銷毀堆
void HeapDestroy(Heap* php)
{
assert(php);
free(php->a); // 釋放動態(tài)開辟的空間
php->a = NULL;
php->size = php->capacity = 0;
}2.3 堆的插入
先插入一個新元素到數(shù)組的尾上，從插入的新元素開始，進行向上調(diào)整算法，直到滿足（大/小）堆。
堆的插入過程演示：
堆的插入，首先需要實現(xiàn)一個向上調(diào)整算法：
// 向上調(diào)整算法（調(diào)成大堆，把大的往上調(diào)）
void AdjustUp(HPDataType* a, int child)
{
// 父節(jié)點的下標
int parent = (child - 1) / 2;
//while (parent >= 0) parent不會小于0
while (child > 0)
{
// 孩子與父親進行比較
if (a[child] > a[parent]) // 如果孩子大于父親
{
// 孩子與父親交換
Swap(&a[child], &a[parent]);
// 更新父子下標，原先父親作為孩子，繼續(xù)往上調(diào)
child = parent;
parent = (child - 1) / 2;
}
else // 如果孩子小于父親，說明已經(jīng)為大堆了，停止調(diào)整
{
break;
}
}
}
堆的插入代碼：
// 插入元素（插入到堆的末尾），插入后并保持它依然是堆
void HeapPush(Heap* php, int x)
{
assert(php);
// 先檢查空間是否已滿
if (php->capacity == php->size)
{
// 增容兩倍
php->capacity *= 2;
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity);
if (tmp != NULL)
{
php->a = tmp;
tmp = NULL;
}
}
// 插入元素
php->a[php->size] = x;
php->size++;
// 從插入的元素開始，進行向上調(diào)整，保持它依然是堆
AdjustUp(php->a, php->size - 1);
}2.4 堆的刪除
- 將堆頂元素和最后一個元素交換（這樣就變成尾刪了，很方便）
- 刪除堆中最后一個元素
- 從根節(jié)點開始，對剩下元素進行向下調(diào)整，調(diào)成（大/小）堆
堆的刪除過程演示：
堆的插入，首先需要實現(xiàn)一個向下調(diào)整算法：前面已經(jīng)實現(xiàn)過了，這里就不展示了。
堆的刪除代碼：
// 刪除堆頂元素，刪除后保持它依然是堆
void HeapPop(Heap* php)
{
assert(php);
assert(!HeapEmpty(php)); // 堆不能為空
// 將堆頂元素和最后一個元素交換
Swap(&php->a[0], &php->a[php->size - 1]);
// 刪除堆中最后一個元素
php->size--;
// 從根節(jié)點開始，對剩下元素進行向下調(diào)整成大堆，保持它依然是堆
AdjustDown(php->a, php->size, 0);
}2.5 獲取堆頂元素
// 獲取堆頂元素，也即是最值
HPDataType HeapTop(Heap* php)
{
assert(php);
assert(!HeapEmpty(php)); // 堆不能為空
return php->a[0];
}2.6 堆的判空
// 判斷堆是否為空，為空返回true，不為空返回false
bool HeapEmpty(Heap* php)
{
assert(php);
return php->size == 0;
}2.7 找出堆中前k個最大元素
堆的相關接口實現(xiàn)好了，因為是大堆，所以我們可以很方便的來找出堆中前 k 個最大元素。
這里要和前面的堆排序區(qū)分開哦，這里我們并不是在堆中對所有元素排好序。
void TestHeap()
{
int a[] = { 1,5,3,8,7,6 };
Heap hp;
HeapInit(&hp, a, sizeof(a) / sizeof(a[0])); // 初始化堆
int k = 0;
scanf("%d", &k);
printf("找出堆中前%d個最大元素：\n", k);
while (!HeapEmpty(&hp) && k--)
{
printf("%d ", HeapTop(&hp)); // 獲取堆頂元素
HeapPop(&hp); // 刪除堆頂元素
}
printf("\n");
}運行結果：
2.8 堆的創(chuàng)建（向上調(diào)整）
下面給出一個數(shù)組，這個數(shù)組邏輯上可以看做一顆完全二叉樹，但不是一個堆，我們需要通過「向上調(diào)整算法」把它構建成一個堆。如果根節(jié)點左右子樹不是一個 (大 / 小) 堆，我們應該怎么調(diào)整呢？
我們從上到下，從「第一個節(jié)點（也就是根節(jié)點）的左孩子」開始，依次遍歷完所有節(jié)點，分別對每個節(jié)點進行「向上調(diào)整」，一直到「最后一個節(jié)點」，就可以建成一個 (大 / 小) 堆。
我們把數(shù)組中的「第一個元素」看作是一個「堆」，剩余的元素依次插入到這個「堆」中。前面我們也實現(xiàn)了堆的插入接口，原理就是向上調(diào)整。
// 向上調(diào)整算法建堆
void CreateHeap(int* a, int size)
{
// 把第一個元素看作是堆，剩余的元素依次插入堆中
for (int i = 1; i < size; i++)
{
AdjustUp(a, i);
}
}
到此這篇關于C語言詳解如何實現(xiàn)堆的結構與接口的文章就介紹到這了,更多相關C語言堆的結構與接口內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家介紹了從零學習cmake構建系統(tǒng)詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-02-02
這篇文章主要介紹了VSCode C++多文件編譯的簡單使用方法,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-03-03
這篇文章主要為大家詳細介紹了Linux下用C++實現(xiàn)俄羅斯方塊的相關資料，感興趣的小伙伴們可以參考一下2016-08-08
在C語言當中,字符串數(shù)組可以使用char a[] [10]; 或者char *a[]; 表示,下面這篇文章主要給大家介紹了關于c語言中字符串與字符串數(shù)組的相關資料,需要的朋友可以參考下2021-11-11
以下是對C語言中的函數(shù)聲明與調(diào)用進行了詳細的分析介紹，需要的朋友可以過來參考下2013-08-08
所謂的青蛙跳臺階問題，就是指一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。本文將用C語言解決這一問題，需要的可以參考一下2022-01-01
這篇文章主要介紹C語言中的If Else語句怎么使用，在日常操作中，相信很多人在If Else語句怎么使用問題上存在疑惑，小編查閱了各式資料，整理出使用方法，接下來，請跟著小編一起來學習吧2022-06-06
C++利用MySQL API連接和操作數(shù)據(jù)庫實例詳解
這篇文章主要介紹了C++利用MySQL API連接和操作數(shù)據(jù)庫實例詳解的相關資料,需要的朋友可以參考下2017-01-01
函數(shù)是一組一起執(zhí)行一個任務的語句。每個?C?程序都至少有一個函數(shù)，即主函數(shù)?main()?，所有簡單的程序都可以定義其他額外的函數(shù)2022-03-03
我們可以把棧理解成一個大倉庫，放在倉庫門口（棧頂）的貨物會優(yōu)先被取出，然后再取出里面的貨物。而從數(shù)據(jù)的邏輯結構來看，棧結構起始就是一種線性結構2013-10-10