網站首頁 編程語言 正文
一、堆的結構及實現（重要）
1.1 二叉樹的順序結構
普通的二叉樹是不適合用數組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結構存儲。在現實中我們通常把堆 (一種完全二叉樹) 使用順序結構的數組來存儲，需要注意的是這里的堆和操作系統虛擬進程地址空間中的堆是兩回事，一個是數據結構，一個是操作系統中管理內存的一塊區域分段。
1.2 堆的概念及結構
堆(Heap)是計算機科學中一類特殊的數據結構的統稱。堆通常是一個可以被看做一棵完全二叉樹的數組對象。堆總是滿足下列性質：
- 堆中某個結點的值總是不大于或不小于其父結點的值；
- 堆總是一棵完全二叉樹。
堆是非線性數據結構，相當于一維數組，有兩個直接后繼。
【大根堆和小根堆】：
根結點最大的堆叫做大根堆，樹中所有父親都大于或等于孩子。
根結點最小的堆叫做小根堆，樹中所有父親都小于或等于孩子。
【思考】這個大根堆和小根堆有什么特點呢？
最值總在 0 號位，根據這個特點我們就可以做很多事情，比如TopK問題 (在一堆數據里面找到前 K 個最大 / 最小的數)，生活中也有很多實例，比如點餐軟件中有上千家店鋪，我想選出該地區好評最多的十家川菜店，我們不用對所有數據排序，只需要取出前 K 個最大 / 最小數據。使用堆排序效率也更高。
1.3 堆的實現
1.3.1 堆的向下調整算法
下面給出一個數組，邏輯上看做一顆完全二叉樹。我們通過從根節點開始的向下調整算法可以把它調整成一個小堆。向下調整算法有一個前提：該節點的左右子樹必須是一個 (大 / 小) 堆，才能調整。
int array[] = { 27,15,19,18,28,34,65,49,25,37 }; // 根節點的左右子樹都是小堆
上面的數組，因為根節點的左右子樹都是小堆，所以我們從根節點開始調整，將其調成小堆。
向下調整算法思路（調成小堆）：
從根節點開始，不斷往下調。
選出根節點的左右孩子中「最小的孩子」，與「父親」進行比較。
- 如果父親小于孩子，就不需處理了，整個樹已經是小堆了。
- 如果父親大于孩子，就跟父親交換位置，并將原來小的孩子的位置當成父親繼續向下進行調整，直到調整到葉子結點為止。
向下調整算法過程演示（調成小堆，把大的節點往下調整）：
向下調整算法代碼：
// 向下調整算法，建小堆，把大的節點往下調整
// 前提是：左右子樹都是小堆
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]);
// 更新父子下標，原先最小的孩子作為父親，繼續往下調
parent = child;
child = parent * 2 + 1;
}
else // 如果父親小于孩子，說明已經為小堆了，停止調整
{
break;
}
}
}1.3.2 向下調整算法的時間復雜度
我們以滿二叉樹計算，最壞情況下，向下調整算法最多進行滿二叉樹的高度減1次比較，則說明向下調整算法最多調整滿二叉樹的高度減1次，n 個節點的滿二叉樹高度為 log2(n+1)，估算后所以時間復雜度為 O(log2n)。
1.3.3 堆的創建（向下調整）
下面給出一個數組，這個數組邏輯上可以看做一顆完全二叉樹，但不是一個堆，我們需要通過算法把它構建成一個堆。如果根節點左右子樹不是一個 (大 / 小) 堆，我們應該怎么調整呢？
我們倒著調整，從下到上，從「倒數第一個非葉子節點的子樹」開始，依次遍歷完所有非葉子節點，分別對每個子樹進行「向下調整」成 (大 / 小) 堆，一直調整到「根節點」，就可以建成一個 (大 / 小) 堆。
為什么要倒著調整呢？因為這樣我們可以把「倒數第一個非葉子節點的子樹」的左右子樹看成是一個 (大 / 小) 堆，此時才能去使用向下調整算法。比如下圖中的黃色填充的子樹，3 的左子樹 6 就可以看成是一個大堆。
【實例】：將下面的數組建成一個大堆
int a[] = { 1,5,3,8,7,6 };
建堆過程演示（以建大堆為例）：從下到上，依次遍歷完所有非葉子節點，分別對每個子樹進行向下調整。
依次對 每一步 中，方框內的樹 進行 向下調整 為一個 大堆。
建堆代碼：
// 交換函數
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
// 向下調整算法，建大堆，把小的節點往下調
// 前提是：左右子樹都是大堆
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]);
// 更新父子下標，原先最大的孩子作為父親，繼續往下調
parent = child;
child = parent * 2 + 1;
}
else // 如果父親大于孩子，說明已經為大堆了，停止調整
{
break;
}
}
}
void HeapSort(int* a, int size)
{
/* 建堆（大堆）
* 倒著調整，從倒數第一個非葉子節點的子樹進行向下調整，直到調整到根節點的樹
*/
int parent = ((size - 1) - 1) / 2; // 最后一個葉子節點的父親的下標
for (int i = parent; i >= 0; i--) // 從下到上，依次遍歷完所有子樹，分別對其進行調整
{
AdjustDown(a, size, i);
}
/* 堆排序
* 排升序 --> 建大堆，每次選出一個最大的數放到最后
* 排降序 --> 建小堆，每次選出一個最小的數放到最后
*/
// 下面是排升序：
int end = size - 1; // 記錄堆中最后一個元素的下標
while (end > 0)
{
Swap(&a[0], &a[end]); // 將堆頂元素和堆中最后一個元素交換，把最大的數(堆頂)放到最后
AdjustDown(a, end, 0); // 不看最后一個數，從根節點開始，對前面的數進行向下調整成大堆
end--;
}
}1.3.4 堆排序
排升序 --> 建大堆：
【思考】排升序，建小堆可以嗎？-- 可以是可以，但沒啥意思。
首先對 n 個數建小堆，選出最小的數，接著對剩下的 n-1 個數建小堆，選出第2小的數，不斷重復上述過程……。建 n 個數的堆時間復雜度是O(N)，所以上述操作時間復雜度為O(N2)，效率太低，尤其是當數據量大的時候，效率更低，同時堆的價值沒有被體現出來，還不如用直接排序。
【最佳方法】排升序，因為數字越來越大，需要找到最大的數字，得建大堆
- 首先對 n 個數建大堆。
- 將最大的數（堆頂）和最后一個數交換，把最大的數放到最后。
- 前面 n-1 個數的堆結構沒有被破壞（最后一個數不看做堆里面的），根節點的左右子樹依舊是大堆，所以我們進行一次向下調整成大堆即可選出第2大的數，放到倒數第二個位置，然后重復上述步驟……。
【時間復雜度】：建堆時間復雜度為O(N)，向下調整時間復雜度為O(log2N)，這里我們最多進行N-2次向下調整，所以堆排序時間復雜度為O(N*log2N)，效率是很高的。
排降序 --> 建小堆：
【最佳方法】排降序，因為數字越來越小，需要找到最小的數字，得建小堆
- 首先對 n 個數建小堆。
- 將最小的數（堆頂）和最后一個數交換，把最小的數放到最后。
- 前面 n-1 個數的堆結構沒有被破壞（最后一個數不看做堆里面的），根節點的左右子樹依舊是小堆，所以我們進行一次向下調整成小堆即可選出第2小的數，放到倒數第二個位置，然后重復上述步驟……。
- 【時間復雜度】：建堆時間復雜度為O(N)，向下調整時間復雜度為O(log2N)，這里我們最多進行N-2次向下調整，所以堆排序時間復雜度為O(N*log2N)，效率是很高的。
1.3.5 建堆的時間復雜度
因為堆是完全二叉樹，而滿二叉樹也是完全二叉樹，此處為了簡化使用滿二叉樹來證明，計算起來比較好算(時間復雜度本來看的就是近似值，多幾個節點不影響最終結果)：
建堆要從倒數第一個非葉子節點開始調整，也即是從倒數第二層開始調，可得出時間復雜度公式：
T ( n ) = ∑ ( 每 層 節 點 數 ? ( 堆 的 高 度 ? 當 前 層 數 ) )
所以，建堆的時間復雜度為O(N)。
【上面學了那么多，這里小小總結一下】
- 堆的向下調整算法就是，在該節點左右子樹都是一個小/大堆的前提下，將以該節點為根的樹調整成一個小/大堆。
- 堆的創建就是倒著調整，從下到上，從倒數第一個非葉子節點的子樹開始，依次遍歷完所有子樹，分別對其進行向下調整。
- 時間復雜度：堆的向下調整算法為O(log2N)，堆的創建為O(N)。
二、堆的相關接口實現（以大堆為例）
首先新建一個工程（ 博主使用的是 VS2019 ）
- Heap.h（堆的類型定義、接口函數聲明、引用的頭文件）
- Heap.c（堆接口函數的實現）
- Test.c（主函數、測試堆各個接口功能）
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; // 指向動態開辟的數組
int size; // 數組中有效元素個數
int capacity; // d容量
}Heap;
// 交換函數
void Swap(HPDataType* a, HPDataType* b);
// 向下調整函數（調成大堆，把小的往下調）
void AdjustDown(HPDataType* a, int size, int parent);
// 向上調整函數（調成大堆，把大的往上調）
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);
// 獲取堆中有效元素個數
int HeapSize(Heap* php);
// 打印堆
void HeapPrint(Heap* php);2.1 堆的初始化
堆的初始化，首先需要實現一個向下調整算法：
// 交換函數
void Swap(HPDataType* a, HPDataType* b)
{
HPDataType tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
// 向下調整算法（調成大堆，把小的往下調）
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]);
// 更新父子下標，原先最大的孩子作為父親，繼續往下調
parent = child;
child = parent * 2 + 1;
}
else // 如果父親大于孩子，說明已經為大堆了，停止調整
{
break;
}
}
}堆的初始化代碼：
// 初始化堆，用一個給定的數組來初始化
void HeapInit(Heap* php, HPDataType* arr, int n)
{
assert(php); // 斷言
// 動態開辟n個空間
php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (php->a == NULL)
{
perror("malloc");
exit(-1);
}
// 把給定數組的各元素值拷貝過去
memcpy(php->a, arr, sizeof(HPDataType) * n);
php->size = php->capacity = n;
// 建堆(建大堆）
int parent = ((php->size - 1) - 1) / 2; // 倒數第一個非葉子節點下標
for (int i = parent; i >= 0; i--) // 從下到上，依次遍歷完所有子樹，分別對其進行調整
{
AdjustDown(php->a, php->size, i);
}
}2.2 堆的銷毀
// 銷毀堆
void HeapDestroy(Heap* php)
{
assert(php);
free(php->a); // 釋放動態開辟的空間
php->a = NULL;
php->size = php->capacity = 0;
}2.3 堆的插入
先插入一個新元素到數組的尾上，從插入的新元素開始，進行向上調整算法，直到滿足（大/小）堆。
堆的插入過程演示：
堆的插入，首先需要實現一個向上調整算法：
// 向上調整算法（調成大堆，把大的往上調）
void AdjustUp(HPDataType* a, int child)
{
// 父節點的下標
int parent = (child - 1) / 2;
//while (parent >= 0) parent不會小于0
while (child > 0)
{
// 孩子與父親進行比較
if (a[child] > a[parent]) // 如果孩子大于父親
{
// 孩子與父親交換
Swap(&a[child], &a[parent]);
// 更新父子下標，原先父親作為孩子，繼續往上調
child = parent;
parent = (child - 1) / 2;
}
else // 如果孩子小于父親，說明已經為大堆了，停止調整
{
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++;
// 從插入的元素開始，進行向上調整，保持它依然是堆
AdjustUp(php->a, php->size - 1);
}2.4 堆的刪除
- 將堆頂元素和最后一個元素交換（這樣就變成尾刪了，很方便）
- 刪除堆中最后一個元素
- 從根節點開始，對剩下元素進行向下調整，調成（大/小）堆
堆的刪除過程演示：
堆的插入，首先需要實現一個向下調整算法：前面已經實現過了，這里就不展示了。
堆的刪除代碼：
// 刪除堆頂元素，刪除后保持它依然是堆
void HeapPop(Heap* php)
{
assert(php);
assert(!HeapEmpty(php)); // 堆不能為空
// 將堆頂元素和最后一個元素交換
Swap(&php->a[0], &php->a[php->size - 1]);
// 刪除堆中最后一個元素
php->size--;
// 從根節點開始，對剩下元素進行向下調整成大堆，保持它依然是堆
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個最大元素
堆的相關接口實現好了，因為是大堆，所以我們可以很方便的來找出堆中前 k 個最大元素。
這里要和前面的堆排序區分開哦，這里我們并不是在堆中對所有元素排好序。
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 堆的創建（向上調整）
下面給出一個數組，這個數組邏輯上可以看做一顆完全二叉樹，但不是一個堆，我們需要通過「向上調整算法」把它構建成一個堆。如果根節點左右子樹不是一個 (大 / 小) 堆，我們應該怎么調整呢？
我們從上到下，從「第一個節點（也就是根節點）的左孩子」開始，依次遍歷完所有節點，分別對每個節點進行「向上調整」，一直到「最后一個節點」，就可以建成一個 (大 / 小) 堆。
我們把數組中的「第一個元素」看作是一個「堆」，剩余的元素依次插入到這個「堆」中。前面我們也實現了堆的插入接口，原理就是向上調整。
// 向上調整算法建堆
void CreateHeap(int* a, int size)
{
// 把第一個元素看作是堆，剩余的元素依次插入堆中
for (int i = 1; i < size; i++)
{
AdjustUp(a, i);
}
}
原文鏈接：https://blog.csdn.net/weixin_48025315/article/details/123165836
相關推薦
- 2022-05-10 V-for中通過變量+索引實現單獨控制
- 2024-07-15 Redis 底層數據結構-簡單動態字符串（SDS）
- 2022-10-14 ‘configurationClass‘ must be assignable to [org.hi
- 2022-05-10 Install fail Error: Unsupported URL Type “workspac
- 2023-03-29 詳解C++中菱形繼承的原理與解決方法_C 語言
- 2022-11-20 Pandas數據處理庫畫圖與文件讀取使用示例_python
- 2023-01-13 Python實現復制文檔數據_python
- 2022-02-16 瀏覽器斷點如何使用(測試工具)
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速