C++中二叉堆排序詳解
1. 前言
什么是二叉堆？
二叉堆是有序的 完全二叉樹，在完全二叉樹的基礎(chǔ)上，二叉堆 提供了有序性特征：
二叉堆 的根結(jié)點上的值是整個堆中的最小值或最大值。
當(dāng)根結(jié)點上的值是整個堆結(jié)構(gòu)中的最小值時，此堆稱為最小堆。最小堆中，任意節(jié)點的值大于父結(jié)點的值。
當(dāng)根結(jié)點上的值是整個堆結(jié)構(gòu)中的最大值時，則稱堆為最大堆。最大堆中，任意節(jié)點的值小于父結(jié)點的值。
根據(jù)完全二叉樹的特性，二叉堆的父結(jié)點與子結(jié)點之間滿足下面的關(guān)系：
如果知道了一個結(jié)點的位置 i，則其左子結(jié)點在 2*i 位置，右子結(jié)點在 2*i+1 位置。
Tips： 前提是存在有子結(jié)點。
如果知道了一個結(jié)點的位置 i，則其父結(jié)點在 i除以 2 的位置。
Tips： 根結(jié)點沒有父結(jié)點。
如上圖所示：
值為 5 的結(jié)點在 2 處，則其左結(jié)點 12 的位置應(yīng)該在 2*2=4 處，而實際情況也是在 4 位置。其右子結(jié)點 13 的位置應(yīng)該在 2*2+1=5 的位置，實際位置也是在 5 位置。
值為 19 的結(jié)點現(xiàn)在 7 位置，其父結(jié)點的根據(jù)公式 7 除 2 等于 3(取整)，應(yīng)該在 3 處，而實際情況也是在 3 處（位置在 3、 值為 8 的結(jié)點是其父結(jié)點）。
2 堆的數(shù)據(jù)結(jié)構(gòu)
2.1 二叉堆的抽象數(shù)據(jù)結(jié)構(gòu)
當(dāng)談?wù)撃撤N數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)結(jié)構(gòu)時，最基本的 API 無非就是增、刪、改、查。
二叉堆的基本抽象數(shù)據(jù)結(jié)構(gòu)：
Heap() ：創(chuàng)建一個新堆。 insert(data)： 向堆中添加新節(jié)點（數(shù)據(jù)）。 getRoot()： 返回最小（大）堆的最?。ù螅┰?。 removeRoot() ：刪除根節(jié)點。 isEmpty()：判斷堆是否為空。 findAll()：查詢堆中所有數(shù)據(jù)。
根據(jù)二叉堆的特性，順序存儲應(yīng)該成為堆的首選方案。
如有數(shù)列=[8,5,12,15,19,13,1]，可以先創(chuàng)建一個一維數(shù)組。
數(shù)組第 0 位置初始為 0，從第 2 個位置也就是索引號為 1 的地方開始存儲堆的數(shù)據(jù)。如下圖，二叉堆中的數(shù)據(jù)在數(shù)組中的對應(yīng)存儲位置。
2.2 基礎(chǔ) API 實現(xiàn)
設(shè)計一個 Heap 類封裝對二叉堆的操作方法，類中方法用來實現(xiàn)最小堆。
#include <iostream>
using namespace std;
/*
* 堆類
*/
template<typename T>
class Heap{
private:
//數(shù)組
T heapList[100];
//實際大小
int size=0;
public:
/*
*構(gòu)造函數(shù)
*/
Heap(){
}
/*
*返回根結(jié)點的值
*/
T getRoot();
/*
*刪除根結(jié)點
*/
T removeRoot();
/*
*遞歸刪除
*/
T removeRoot_();
void removeRootByRecursion(int parentIdx );
/*
*初始化根結(jié)點
*/
void setRoot(T val);
/*
*添加新結(jié)點,返回存儲位置
*/
int insert(T val);
/*
*堆是否為空
*/
bool isEmpty();
/*
* 遞歸插入
*/
int insert_(T val);
int insertByRecursion(int pos);
/*
*輸出所有結(jié)點
*/
void findAll() {
for(int i=0; i<=size; i++)
cout<<this->heapList[i]<<"\t";
cout<<endl;
}
}; Heap 類中的屬性詳解：
heapList：使用數(shù)組存儲二叉堆的數(shù)據(jù)，初始時，列表的第 0 位置初始為默認(rèn)值 0。
Tips： 為什么要設(shè)置列表的第 0 位置的默認(rèn)值為 0？
這個 0 也不是隨意指定的，有其特殊數(shù)據(jù)含義：用來描述根結(jié)點的父結(jié)點編號或者說根結(jié)點沒有父結(jié)點。
size：用來存儲二叉堆中數(shù)據(jù)的實際個數(shù)。
Heap 類中的方法介紹：
isEmpty：檢查是不是空堆。邏輯較簡單。
/*
*當(dāng) size 為 0 時，堆為空
*/
template<typename T>
bool Heap<T>::isEmpty(){
return Heap::size==0;
}setRoot：創(chuàng)建根結(jié)點。保證根節(jié)點始終存儲在列表索引為 1 的位置。
/*
*初始化根結(jié)點
*/
template<typename T>
void Heap<T>::setRoot(T val) {
if( Heap<T>::heapList[1]==0 )
Heap<T>::heapList[1]=val;
Heap<T>::size++;
}getRoot：如果是最大堆，則返回二叉堆的最大值，如果是最小堆，則返回二叉堆的最小值。
/*
*返回根結(jié)點
*/
template<typename T>
T Heap<T>::getRoot() {
if( !Heap<T>::isEmpty )
return Heap<T>::heapList[1];
}Tips： 使用數(shù)組存儲二叉堆數(shù)據(jù)時，根結(jié)點始終保存在索引號為 1 的位置。
前面是幾個基本方法，現(xiàn)在實現(xiàn)添加新結(jié)點，編碼之前，先要知道如何在二叉堆中添加新結(jié)點：
2.3 上沉算法
添加新結(jié)點采用上沉算法。如下演示上沉算法的實現(xiàn)過程。
把新結(jié)點添加到已有的二叉堆的最后面。如下圖，添加值為 4 的新結(jié)點，存儲至索引號為 7 的位置。
查找新結(jié)點的父結(jié)點，并與父結(jié)點的值比較大小，如果比父結(jié)點的值小，則和父結(jié)點交換位置。如下圖，值為 4 的結(jié)點小于值為 8 的父結(jié)點，兩者交換位置。
交換后再查詢是否存在父結(jié)點，如果有，同樣比較大小、交換，直到到達(dá)根結(jié)點或比父結(jié)點大為止。值為 4 的結(jié)點小于值為 5 的父結(jié)點，繼續(xù)交換。交換后，新結(jié)點已經(jīng)達(dá)到了根結(jié)點位置，整個添加過程可結(jié)束。觀察后會發(fā)現(xiàn)，遵循此流程添加后，沒有破壞二叉堆的有序性。
編碼實現(xiàn) insert 方法
/*
*添加新結(jié)點
*/
template<typename T>
T Heap<T>::insert(T val) {
//存儲在最后一個位置
int pos= ++Heap<T>::size;
Heap<T>::heapList[pos]=val;
int temp=0;
//上沉算法
while(1) {
//找到父結(jié)點位置
int parentIdx= pos / 2;
if(parentIdx==0)
//出口一，沒有父結(jié)點
break;
if( Heap<T>::heapList[pos]>Heap<T>::heapList[parentIdx] )
//出口二：大于父結(jié)點
break;
else {
//和父親結(jié)點交換
temp=Heap<T>::heapList[pos];
Heap<T>::heapList[pos]=Heap<T>::heapList[parentIdx];
Heap<T>::heapList[parentIdx]=temp;
pos=parentIdx
}
}
}測試向二叉堆中添加數(shù)據(jù)。
int main(int argc, char** argv) {
//實例化堆
Heap<int> heap;
//初始化根結(jié)點
heap.setRoot(5);
//檢查根結(jié)點是否創(chuàng)建成功
int rootVal=heap.getRoot();
cout<<"根結(jié)點的值："<<rootVal<<endl;
//添加值為 12和值為 13 的 2個新結(jié)點，檢查添加新結(jié)點后整個二叉堆的有序性是否正確。
heap.insert(12);
heap.insert(13);
cout<<"測試一："<<endl;
heap.findAll();
return 0;
}輸出結(jié)果：
添加值為 1 的新結(jié)點，并檢查二叉堆的有序性。
int main(int argc, char** argv) {
//省略……
//添加值為 1 的結(jié)點
heap.insert(1);
cout<<"測試二："<<endl;
heap.findAll();
return 0;
}
繼續(xù)添加值為 15、19、8 的 3 個新結(jié)點，并檢查二叉堆的狀況。
int main(int argc, char** argv) {
//省略……
heap.insert(15);
heap.insert(19);
heap.insert(8);
cout<<"測試三："<<endl;
heap.findAll();
return 0;
}
上沉算法同樣可以使用遞歸實現(xiàn)。
/*
*遞歸實現(xiàn)插入
*/
template<typename T>
int Heap<T>::insert_(T val) {
//存儲在最后一個位置
int pos= ++Heap<T>::size;
Heap<T>::heapList[pos]=val;
//調(diào)用
Heap<T>::insertByRecursion(pos);
}
template<typename T>
int Heap<T>::insertByRecursion(int pos) {
//找到父結(jié)點位置
int parentIdx= pos / 2;
if(parentIdx==0)
//出口一，沒有父結(jié)點
return pos;
if( Heap<T>::heapList[pos]>Heap<T>::heapList[parentIdx] )
//出口二：大于父結(jié)點
return pos;
else {
//和父親結(jié)點交換
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 下沉算法
介紹完添加方法后，再來了解一下，如何使用下沉算法刪除二叉堆中的結(jié)點。
二叉堆的刪除操作從根結(jié)點開始，如下圖刪除根結(jié)點后，空出來的根結(jié)點位置，需要在整個二叉堆中重新找一個結(jié)點充當(dāng)新的根結(jié)點。
二叉堆中使用下沉算法選擇新的根結(jié)點：
找到二叉堆中的最后一個結(jié)點，移到到根結(jié)點位置。如下圖，把二叉堆中最后那個值為 19 的結(jié)點移到根結(jié)點位置。
最小堆中，如果新的根結(jié)點的值比左或右子結(jié)點的值大，則和子結(jié)點交換位置。如下圖，在二叉堆中把 19 和 5 的位置進(jìn)行交換。
Tips： 總是和最小的子結(jié)點交換。
交換后，如果還是不滿足最小二叉堆父結(jié)點小于子結(jié)點的規(guī)則，則繼續(xù)比較、交換新根結(jié)點直到下沉到二叉堆有序為止。如下，繼續(xù)交換 12 和 19 的值。如此反復(fù)經(jīng)過多次交換直到整個堆結(jié)構(gòu)符合二叉堆的特性。
removeoot 方法的具體實現(xiàn)：
/*
* 下沉算法，刪除結(jié)點
*/
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;
}
//堆中最后一個結(jié)點移動根結(jié)點
Heap<T>::heapList[1]=Heap<T>::heapList[Heap<T>::size];
Heap<T>::size--;
//下沉算法
int parentIdx=1;
//子結(jié)點值
T minChild;
//子結(jié)點位置
int idx;
while(1) {
//左結(jié)點位置
int leftIdx=parentIdx*2;
//右結(jié)點位置
int rightIdx=parentIdx*2+1;
if( leftIdx<=Heap<T>::size && rightIdx<=Heap<T>::size ) {
//記錄較小的結(jié)點值和位置
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{
//沒有子結(jié)點
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;
} 測試在二叉堆中刪除結(jié)點：
int main(int argc, char** argv) {
//省略……
cout<<"測試刪除一:"<<endl;
heap.removeRoot();
heap.findAll();
return 0;
}
可以看到最后二叉堆的結(jié)構(gòu)和有序性都得到了完整的保持。
"下沉算法" 同樣可以使用遞歸實現(xiàn)。
/*
*遞歸實現(xiàn)下沉算法
*/
template<typename T>
T Heap<T>::removeRoot_() {
if(Heap<T>::size==0)return NULL;
//根結(jié)點值
T root=Heap<T>::heapList[1];
//
if(Heap<T>::size==1) {
Heap<T>::size--;
return root;
}
//堆中最后一個結(jié)點移動根結(jié)點
Heap<T>::heapList[1]=Heap<T>::heapList[Heap<T>::size];
Heap<T>::size--;
//調(diào)用
Heap<T>::removeRootByRecursion(1);
return root;
}
template<typename T>
void Heap<T>::removeRootByRecursion(int parentIdx ) {
//子結(jié)點值
T minChild;
//子結(jié)點位置
int idx;
//左結(jié)點位置
int leftIdx=parentIdx*2;
//右結(jié)點位置
int rightIdx=parentIdx*2+1;
if( leftIdx<=Heap<T>::size && rightIdx<=Heap<T>::size ) {
//記錄較小的結(jié)點值和位置
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 {
//沒有子結(jié)點
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. 堆排序
堆排序指借助堆的有序性對數(shù)據(jù)進(jìn)行排序。
需要排序的數(shù)據(jù)以堆的方式保存。 然后再從堆中以根結(jié)點方式取出來，無序數(shù)據(jù)就會變成有序數(shù)據(jù) 。
如有數(shù)列=[4,1,8,12,5,10,7,21,3]，現(xiàn)通過堆的數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序。
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;
// 創(chuàng)建根節(jié)點
heap.setRoot(nums[0]);
// 其它數(shù)據(jù)添加到二叉堆中
for (int i=1; i<size; i++) {
heap.insert(nums[i]);
}
cout<<"堆中數(shù)據(jù)："<<endl;
heap.findAll();
// 獲取堆中的數(shù)據(jù)
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;
}輸出結(jié)果：
本例中的代碼還有優(yōu)化空間，本文試圖講清楚堆的使用，優(yōu)化的地方交給有興趣者。
4. 后記
在樹結(jié)構(gòu)上加上一些新特性要求，樹會產(chǎn)生很多新的變種，如二叉樹，限制子結(jié)點的個數(shù)，如滿二叉樹，限制葉結(jié)點的個數(shù)，如完全二叉樹就是在滿二叉樹的“滿”字上做點文章，讓這個''滿"變成"不那么滿"。
在完全二叉樹上添加有序性，則會衍生出二叉堆數(shù)據(jù)結(jié)構(gòu)。利用二叉堆的有序性，能輕松完成對數(shù)據(jù)的排序。
到此這篇關(guān)于C++中二叉堆排序詳解的文章就介紹到這了,更多相關(guān)C++ 二叉堆排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Java?C++題解?leetcode第k個數(shù)實例
這篇文章主要為大家介紹了Java?C++題解?leetcode第k個數(shù)實例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-09-09
淺析Boost智能指針:scoped_ptr shared_ptr weak_ptr
雖然通過弱引用指針可以有效的解除循環(huán)引用，但這種方式必須在程序員能預(yù)見會出現(xiàn)循環(huán)引用的情況下才能使用，也可以是說這個僅僅是一種編譯期的解決方案，如果程序在運行過程中出現(xiàn)了循環(huán)引用，還是會造成內(nèi)存泄漏的2013-09-09
這篇文章主要介紹了C語言二叉樹的非遞歸遍歷,包括了先序遍歷、中序遍歷與后序遍歷,需要的朋友可以參考下2014-09-09
中序遍歷(LDR)是二叉樹遍歷的一種，也叫做中根遍歷、中序周游。在二叉樹中，中序遍歷首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹2021-07-07
這篇文章主要介紹了二叉樹前序遍歷的非遞歸算法,需要的朋友可以參考下2014-02-02
C++使用easyX庫實現(xiàn)三星環(huán)繞效果流程詳解
EasyX是針對C/C++的圖形庫，可以幫助使用C/C++語言的程序員快速上手圖形和游戲編程。這篇文章主要介紹了C++使用easyX庫實現(xiàn)三星環(huán)繞效果，需要的可以參考一下2022-10-10
這篇文章主要介紹了C語言構(gòu)建動態(tài)數(shù)組完整實例,幫助讀者加深對C語言數(shù)組及指針的理解,需要的朋友可以參考下2014-07-07
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)掃雷算法簡易版，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-07-07
在不少實際問題中有許多具有規(guī)律性的重復(fù)操作，因此在程序中就需要重復(fù)執(zhí)行某些語句。一組被重復(fù)執(zhí)行的語句稱之為循環(huán)體，C語言while語句可以是單個語句,也可以是一個語句塊,其條件可以是任意表達(dá)式,true是任意非零值,當(dāng)條件為真時,循環(huán)進(jìn)行迭代2022-06-06
C語言實現(xiàn)學(xué)生選課系統(tǒng)完整版
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)學(xué)生選課系統(tǒng)的完整版，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-02-02