網站首頁 編程語言 正文
1. 前言
什么是二叉堆？
二叉堆是有序的 完全二叉樹，在完全二叉樹的基礎上，二叉堆 提供了有序性特征：
二叉堆 的根結點上的值是整個堆中的最小值或最大值。
當根結點上的值是整個堆結構中的最小值時，此堆稱為最小堆。最小堆中，任意節點的值大于父結點的值。
當根結點上的值是整個堆結構中的最大值時，則稱堆為最大堆。最大堆中，任意節點的值小于父結點的值。
根據完全二叉樹的特性，二叉堆的父結點與子結點之間滿足下面的關系：
如果知道了一個結點的位置 i，則其左子結點在 2*i 位置，右子結點在 2*i+1 位置。
Tips： 前提是存在有子結點。
如果知道了一個結點的位置 i，則其父結點在 i除以 2 的位置。
Tips： 根結點沒有父結點。
如上圖所示：
值為 5 的結點在 2 處，則其左結點 12 的位置應該在 2*2=4 處，而實際情況也是在 4 位置。其右子結點 13 的位置應該在 2*2+1=5 的位置，實際位置也是在 5 位置。
值為 19 的結點現在 7 位置，其父結點的根據公式 7 除 2 等于 3(取整)，應該在 3 處，而實際情況也是在 3 處（位置在 3、 值為 8 的結點是其父結點）。
2 堆的數據結構
2.1 二叉堆的抽象數據結構
當談論某種數據結構的抽象數據結構時，最基本的 API 無非就是增、刪、改、查。
二叉堆的基本抽象數據結構：
Heap() ：創建一個新堆。 insert(data)： 向堆中添加新節點（數據）。 getRoot()： 返回最小（大）堆的最小（大）元素。 removeRoot() ：刪除根節點。 isEmpty()：判斷堆是否為空。 findAll()：查詢堆中所有數據。
根據二叉堆的特性，順序存儲應該成為堆的首選方案。
如有數列=[8,5,12,15,19,13,1]，可以先創建一個一維數組。
數組第 0 位置初始為 0，從第 2 個位置也就是索引號為 1 的地方開始存儲堆的數據。如下圖，二叉堆中的數據在數組中的對應存儲位置。
2.2 基礎 API 實現
設計一個 Heap 類封裝對二叉堆的操作方法，類中方法用來實現最小堆。
#include <iostream>
using namespace std;
/*
* 堆類
*/
template<typename T>
class Heap{
private:
//數組
T heapList[100];
//實際大小
int size=0;
public:
/*
*構造函數
*/
Heap(){
}
/*
*返回根結點的值
*/
T getRoot();
/*
*刪除根結點
*/
T removeRoot();
/*
*遞歸刪除
*/
T removeRoot_();
void removeRootByRecursion(int parentIdx );
/*
*初始化根結點
*/
void setRoot(T val);
/*
*添加新結點,返回存儲位置
*/
int insert(T val);
/*
*堆是否為空
*/
bool isEmpty();
/*
* 遞歸插入
*/
int insert_(T val);
int insertByRecursion(int pos);
/*
*輸出所有結點
*/
void findAll() {
for(int i=0; i<=size; i++)
cout<<this->heapList[i]<<"\t";
cout<<endl;
}
}; Heap 類中的屬性詳解：
heapList：使用數組存儲二叉堆的數據，初始時，列表的第 0 位置初始為默認值 0。
Tips： 為什么要設置列表的第 0 位置的默認值為 0？
這個 0 也不是隨意指定的，有其特殊數據含義：用來描述根結點的父結點編號或者說根結點沒有父結點。
size：用來存儲二叉堆中數據的實際個數。
Heap 類中的方法介紹：
isEmpty：檢查是不是空堆。邏輯較簡單。
/*
*當 size 為 0 時，堆為空
*/
template<typename T>
bool Heap<T>::isEmpty(){
return Heap::size==0;
}setRoot：創建根結點。保證根節點始終存儲在列表索引為 1 的位置。
/*
*初始化根結點
*/
template<typename T>
void Heap<T>::setRoot(T val) {
if( Heap<T>::heapList[1]==0 )
Heap<T>::heapList[1]=val;
Heap<T>::size++;
}getRoot：如果是最大堆，則返回二叉堆的最大值，如果是最小堆，則返回二叉堆的最小值。
/*
*返回根結點
*/
template<typename T>
T Heap<T>::getRoot() {
if( !Heap<T>::isEmpty )
return Heap<T>::heapList[1];
}Tips： 使用數組存儲二叉堆數據時，根結點始終保存在索引號為 1 的位置。
前面是幾個基本方法，現在實現添加新結點，編碼之前，先要知道如何在二叉堆中添加新結點：
2.3 上沉算法
添加新結點采用上沉算法。如下演示上沉算法的實現過程。
把新結點添加到已有的二叉堆的最后面。如下圖，添加值為 4 的新結點，存儲至索引號為 7 的位置。
查找新結點的父結點，并與父結點的值比較大小，如果比父結點的值小，則和父結點交換位置。如下圖，值為 4 的結點小于值為 8 的父結點，兩者交換位置。
交換后再查詢是否存在父結點，如果有，同樣比較大小、交換，直到到達根結點或比父結點大為止。值為 4 的結點小于值為 5 的父結點，繼續交換。交換后，新結點已經達到了根結點位置，整個添加過程可結束。觀察后會發現，遵循此流程添加后，沒有破壞二叉堆的有序性。
編碼實現 insert 方法
/*
*添加新結點
*/
template<typename T>
T Heap<T>::insert(T val) {
//存儲在最后一個位置
int pos= ++Heap<T>::size;
Heap<T>::heapList[pos]=val;
int temp=0;
//上沉算法
while(1) {
//找到父結點位置
int parentIdx= pos / 2;
if(parentIdx==0)
//出口一，沒有父結點
break;
if( Heap<T>::heapList[pos]>Heap<T>::heapList[parentIdx] )
//出口二：大于父結點
break;
else {
//和父親結點交換
temp=Heap<T>::heapList[pos];
Heap<T>::heapList[pos]=Heap<T>::heapList[parentIdx];
Heap<T>::heapList[parentIdx]=temp;
pos=parentIdx
}
}
}測試向二叉堆中添加數據。
int main(int argc, char** argv) {
//實例化堆
Heap<int> heap;
//初始化根結點
heap.setRoot(5);
//檢查根結點是否創建成功
int rootVal=heap.getRoot();
cout<<"根結點的值："<<rootVal<<endl;
//添加值為 12和值為 13 的 2個新結點，檢查添加新結點后整個二叉堆的有序性是否正確。
heap.insert(12);
heap.insert(13);
cout<<"測試一："<<endl;
heap.findAll();
return 0;
}輸出結果：
添加值為 1 的新結點，并檢查二叉堆的有序性。
int main(int argc, char** argv) {
//省略……
//添加值為 1 的結點
heap.insert(1);
cout<<"測試二："<<endl;
heap.findAll();
return 0;
}
繼續添加值為 15、19、8 的 3 個新結點，并檢查二叉堆的狀況。
int main(int argc, char** argv) {
//省略……
heap.insert(15);
heap.insert(19);
heap.insert(8);
cout<<"測試三："<<endl;
heap.findAll();
return 0;
}
上沉算法同樣可以使用遞歸實現。
/*
*遞歸實現插入
*/
template<typename T>
int Heap<T>::insert_(T val) {
//存儲在最后一個位置
int pos= ++Heap<T>::size;
Heap<T>::heapList[pos]=val;
//調用
Heap<T>::insertByRecursion(pos);
}
template<typename T>
int Heap<T>::insertByRecursion(int pos) {
//找到父結點位置
int parentIdx= pos / 2;
if(parentIdx==0)
//出口一，沒有父結點
return pos;
if( Heap<T>::heapList[pos]>Heap<T>::heapList[parentIdx] )
//出口二：大于父結點
return pos;
else {
//和父親結點交換
int temp=Heap<T>::heapList[pos];
Heap<T>::heapList[pos]=Heap<T>::heapList[parentIdx];
Heap<T>::heapList[parentIdx]=temp;
//遞歸
Heap<T>::insertByRecursion(parentIdx);
}
}2.4 下沉算法
介紹完添加方法后，再來了解一下，如何使用下沉算法刪除二叉堆中的結點。
二叉堆的刪除操作從根結點開始，如下圖刪除根結點后，空出來的根結點位置，需要在整個二叉堆中重新找一個結點充當新的根結點。
二叉堆中使用下沉算法選擇新的根結點：
找到二叉堆中的最后一個結點，移到到根結點位置。如下圖，把二叉堆中最后那個值為 19 的結點移到根結點位置。
最小堆中，如果新的根結點的值比左或右子結點的值大，則和子結點交換位置。如下圖，在二叉堆中把 19 和 5 的位置進行交換。
Tips： 總是和最小的子結點交換。
交換后，如果還是不滿足最小二叉堆父結點小于子結點的規則，則繼續比較、交換新根結點直到下沉到二叉堆有序為止。如下，繼續交換 12 和 19 的值。如此反復經過多次交換直到整個堆結構符合二叉堆的特性。
removeoot 方法的具體實現：
/*
* 下沉算法，刪除結點
*/
template<typename T>
T Heap<T>::removeRoot() {
if(Heap<T>::size==0)return NULL;
T root=Heap<T>::heapList[1];
if(Heap<T>::size==1) {
Heap<T>::size--;
return root;
}
//堆中最后一個結點移動根結點
Heap<T>::heapList[1]=Heap<T>::heapList[Heap<T>::size];
Heap<T>::size--;
//下沉算法
int parentIdx=1;
//子結點值
T minChild;
//子結點位置
int idx;
while(1) {
//左結點位置
int leftIdx=parentIdx*2;
//右結點位置
int rightIdx=parentIdx*2+1;
if( leftIdx<=Heap<T>::size && rightIdx<=Heap<T>::size ) {
//記錄較小的結點值和位置
minChild=Heap<T>::heapList[leftIdx]<Heap<T>::heapList[rightIdx]?Heap<T>::heapList[leftIdx]:Heap<T>::heapList[rightIdx];
idx=Heap<T>::heapList[leftIdx]<Heap<T>::heapList[rightIdx]?leftIdx:rightIdx;
} else if( leftIdx<=Heap<T>::size) {
minChild=Heap<T>::heapList[leftIdx];
idx=leftIdx;
} else if( rightIdx<=Heap<T>::size ) {
minChild=Heap<T>::heapList[rightIdx];
idx=rightIdx;
}else{
//沒有子結點
break;
}
//是否交換
if( Heap<T>::heapList[parentIdx]>minChild ) {
Heap<T>::heapList[idx]=Heap<T>::heapList[parentIdx];
Heap<T>::heapList[parentIdx]=minChild;
parentIdx=idx;
} else {
break;
}
}
return root;
} 測試在二叉堆中刪除結點：
int main(int argc, char** argv) {
//省略……
cout<<"測試刪除一:"<<endl;
heap.removeRoot();
heap.findAll();
return 0;
}
可以看到最后二叉堆的結構和有序性都得到了完整的保持。
"下沉算法" 同樣可以使用遞歸實現。
/*
*遞歸實現下沉算法
*/
template<typename T>
T Heap<T>::removeRoot_() {
if(Heap<T>::size==0)return NULL;
//根結點值
T root=Heap<T>::heapList[1];
//
if(Heap<T>::size==1) {
Heap<T>::size--;
return root;
}
//堆中最后一個結點移動根結點
Heap<T>::heapList[1]=Heap<T>::heapList[Heap<T>::size];
Heap<T>::size--;
//調用
Heap<T>::removeRootByRecursion(1);
return root;
}
template<typename T>
void Heap<T>::removeRootByRecursion(int parentIdx ) {
//子結點值
T minChild;
//子結點位置
int idx;
//左結點位置
int leftIdx=parentIdx*2;
//右結點位置
int rightIdx=parentIdx*2+1;
if( leftIdx<=Heap<T>::size && rightIdx<=Heap<T>::size ) {
//記錄較小的結點值和位置
minChild=Heap<T>::heapList[leftIdx]<Heap<T>::heapList[rightIdx]?Heap<T>::heapList[leftIdx]:Heap<T>::heapList[rightIdx];
idx=Heap<T>::heapList[leftIdx]<Heap<T>::heapList[rightIdx]?leftIdx:rightIdx;
} else if( leftIdx<=Heap<T>::size) {
minChild=Heap<T>::heapList[leftIdx];
idx=leftIdx;
} else if( rightIdx<=Heap<T>::size ) {
minChild=Heap<T>::heapList[rightIdx];
idx=rightIdx;
} else {
//沒有子結點
return;
}
//是否交換
if( Heap<T>::heapList[parentIdx]>minChild ) {
Heap<T>::heapList[idx]=Heap<T>::heapList[parentIdx];
Heap<T>::heapList[parentIdx]=minChild;
//遞歸
Heap<T>::removeRootByRecursion(idx);
} else {
return;
}
}3. 堆排序
堆排序指借助堆的有序性對數據進行排序。
需要排序的數據以堆的方式保存。 然后再從堆中以根結點方式取出來，無序數據就會變成有序數據 。
如有數列=[4,1,8,12,5,10,7,21,3]，現通過堆的數據結構進行排序。
int main(int argc, char** argv) {
//實例化堆
Heap<int> heap;
int nums[] = {4,1,8,12,5,10,7,21,3};
int size=sizeof(nums)/4;
// 創建根節點
heap.setRoot(nums[0]);
// 其它數據添加到二叉堆中
for (int i=1; i<size; i++) {
heap.insert(nums[i]);
}
cout<<"堆中數據："<<endl;
heap.findAll();
// 獲取堆中的數據
for(int i=0; i<size; i++ ) {
nums[i]= heap.removeRoot();
heap.findAll();
}
for(int i=0; i<size; i++)
cout<<nums[i]<<"\t";
return 0;
}輸出結果：
本例中的代碼還有優化空間，本文試圖講清楚堆的使用，優化的地方交給有興趣者。
4. 后記
在樹結構上加上一些新特性要求，樹會產生很多新的變種，如二叉樹，限制子結點的個數，如滿二叉樹，限制葉結點的個數，如完全二叉樹就是在滿二叉樹的“滿”字上做點文章，讓這個''滿"變成"不那么滿"。
在完全二叉樹上添加有序性，則會衍生出二叉堆數據結構。利用二叉堆的有序性，能輕松完成對數據的排序。
原文鏈接：https://blog.51cto.com/gkcode/5992314
相關推薦
- 2024-03-09 【Redis】Redis中的布隆過濾器
- 2022-05-20 springCloud_Nacos服務搭建
- 2022-03-18 C#?利用Autofac批量接口注入依賴的問題小結_C#教程
- 2022-02-17 不懂就問：map中使用await為什么會失效？
- 2022-12-06 C++如何將字符串顛倒輸出_C 語言
- 2022-04-09 SpringBoot 集成MyBatis-Plus提示反序列化異常：cannot deseriali
- 2023-01-03 go?doudou開發gRPC服務快速上手實現詳解_Golang
- 2022-06-29 Oracle遞歸查詢connect?by用法_oracle
- 最近更新
-
- 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加速