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