C++中二叉堆排序詳解

更新時(shí)間：2023年01月07日 09:56:20 作者：一枚大果殼

這篇文章主要介紹了C++中二叉堆排序詳解，主要介紹了二叉堆排序（遞歸和非遞歸實(shí)現(xiàn)上沉、下沉算法）,需要的朋友可以參考下

1. 前言

什么是二叉堆？

二叉堆是有序的 完全二叉樹(shù)，在完全二叉樹(shù)的基礎(chǔ)上，二叉堆 提供了有序性特征：

二叉堆 的根結(jié)點(diǎn)上的值是整個(gè)堆中的最小值或最大值。

當(dāng)根結(jié)點(diǎn)上的值是整個(gè)堆結(jié)構(gòu)中的最小值時(shí)，此堆稱(chēng)為最小堆。最小堆中，任意節(jié)點(diǎn)的值大于父結(jié)點(diǎn)的值。

當(dāng)根結(jié)點(diǎn)上的值是整個(gè)堆結(jié)構(gòu)中的最大值時(shí)，則稱(chēng)堆為最大堆。最大堆中，任意節(jié)點(diǎn)的值小于父結(jié)點(diǎn)的值。

根據(jù)完全二叉樹(shù)的特性，二叉堆的父結(jié)點(diǎn)與子結(jié)點(diǎn)之間滿(mǎ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)沒(méi)有父結(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 無(wú)非就是增、刪、改、查。

二叉堆的基本抽象數(shù)據(jù)結(jié)構(gòu)：

Heap() ：創(chuàng)建一個(gè)新堆。 insert(data)：向堆中添加新節(jié)點(diǎn)（數(shù)據(jù)）。 getRoot()：返回最?。ù螅┒训淖钚。ù螅┰?。 removeRoot() ：刪除根節(jié)點(diǎn)。 isEmpty()：判斷堆是否為空。 findAll()：查詢(xún)堆中所有數(shù)據(jù)。

根據(jù)二叉堆的特性，順序存儲(chǔ)應(yīng)該成為堆的首選方案。

如有數(shù)列=[8,5,12,15,19,13,1]，可以先創(chuàng)建一個(gè)一維數(shù)組。

數(shù)組第 0 位置初始為 0，從第 2 個(gè)位置也就是索引號(hào)為 1 的地方開(kāi)始存儲(chǔ)堆的數(shù)據(jù)。如下圖，二叉堆中的數(shù)據(jù)在數(shù)組中的對(duì)應(yīng)存儲(chǔ)位置。

2.2 基礎(chǔ) API 實(shí)現(xiàn)

設(shè)計(jì)一個(gè) Heap 類(lèi)封裝對(duì)二叉堆的操作方法，類(lèi)中方法用來(lái)實(shí)現(xiàn)最小堆。

#include <iostream>
using namespace std;
/* 
* 堆類(lèi) 
*/ 
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 類(lèi)中的屬性詳解：

heapList：使用數(shù)組存儲(chǔ)二叉堆的數(shù)據(jù)，初始時(shí)，列表的第 0 位置初始為默認(rèn)值 0。

Tips：為什么要設(shè)置列表的第 0 位置的默認(rèn)值為 0？

這個(gè) 0 也不是隨意指定的，有其特殊數(shù)據(jù)含義：用來(lái)描述根結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)或者說(shuō)根結(jié)點(diǎn)沒(méi)有父結(jié)點(diǎn)。

size：用來(lái)存儲(chǔ)二叉堆中數(shù)據(jù)的實(shí)際個(gè)數(shù)。

Heap 類(lèi)中的方法介紹：

isEmpty：檢查是不是空堆。邏輯較簡(jiǎn)單。

/*
*當(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)始終保存在索引號(hào)為 1 的位置。

前面是幾個(gè)基本方法，現(xiàn)在實(shí)現(xiàn)添加新結(jié)點(diǎn)，編碼之前，先要知道如何在二叉堆中添加新結(jié)點(diǎn)：

2.3 上沉算法

添加新結(jié)點(diǎn)采用上沉算法。如下演示上沉算法的實(shí)現(xiàn)過(guò)程。

把新結(jié)點(diǎn)添加到已有的二叉堆的最后面。如下圖，添加值為 4 的新結(jié)點(diǎn)，存儲(chǔ)至索引號(hào)為 7 的位置。

查找新結(jié)點(diǎn)的父結(jié)點(diǎn)，并與父結(jié)點(diǎn)的值比較大小，如果比父結(jié)點(diǎn)的值小，則和父結(jié)點(diǎn)交換位置。如下圖，值為 4 的結(jié)點(diǎn)小于值為 8 的父結(jié)點(diǎn)，兩者交換位置。

交換后再查詢(xú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è)添加過(guò)程可結(jié)束。觀察后會(huì)發(fā)現(xiàn)，遵循此流程添加后，沒(méi)有破壞二叉堆的有序性。

編碼實(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)
			//出口一，沒(méi)有父結(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
		}
	}
}

測(cè)試向二叉堆中添加數(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<<"測(cè)試一："<<endl;
	heap.findAll();
	return 0;
}

輸出結(jié)果：

添加值為 1 的新結(jié)點(diǎn)，并檢查二叉堆的有序性。

int main(int argc, char** argv) {
	//省略……
    //添加值為 1 的結(jié)點(diǎn)
	heap.insert(1);
	cout<<"測(cè)試二："<<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<<"測(cè)試三："<<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)
		//出口一，沒(méi)有父結(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 下沉算法

介紹完添加方法后，再來(lái)了解一下，如何使用下沉算法刪除二叉堆中的結(jié)點(diǎn)。

二叉堆的刪除操作從根結(jié)點(diǎn)開(kāi)始，如下圖刪除根結(jié)點(diǎn)后，空出來(lái)的根結(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)交換。

交換后，如果還是不滿(mǎn)足最小二叉堆父結(jié)點(diǎn)小于子結(jié)點(diǎn)的規(guī)則，則繼續(xù)比較、交換新根結(jié)點(diǎn)直到下沉到二叉堆有序?yàn)橹?。如下，繼續(xù)交換 12 和 19 的值。如此反復(fù)經(jīng)過(guò)多次交換直到整個(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{
			//沒(méi)有子結(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;
}

測(cè)試在二叉堆中刪除結(jié)點(diǎn)：

int main(int argc, char** argv) {
    //省略……
	cout<<"測(cè)試刪除一:"<<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 {
		//沒(méi)有子結(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. 堆排序

堆排序指借助堆的有序性對(duì)數(shù)據(jù)進(jìn)行排序。

需要排序的數(shù)據(jù)以堆的方式保存。然后再?gòu)亩阎幸愿Y(jié)點(diǎn)方式取出來(lái)，無(wú)序數(shù)據(jù)就會(huì)變成有序數(shù)據(jù) 。

如有數(shù)列=[4,1,8,12,5,10,7,21,3]，現(xiàn)通過(guò)堆的數(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. 后記

在樹(shù)結(jié)構(gòu)上加上一些新特性要求，樹(shù)會(huì)產(chǎn)生很多新的變種，如二叉樹(shù)，限制子結(jié)點(diǎn)的個(gè)數(shù)，如滿(mǎn)二叉樹(shù)，限制葉結(jié)點(diǎn)的個(gè)數(shù)，如完全二叉樹(shù)就是在滿(mǎn)二叉樹(shù)的“滿(mǎn)”字上做點(diǎn)文章，讓這個(gè)''滿(mǎn)"變成"不那么滿(mǎn)"。

在完全二叉樹(shù)上添加有序性，則會(huì)衍生出二叉堆數(shù)據(jù)結(jié)構(gòu)。利用二叉堆的有序性，能輕松完成對(duì)數(shù)據(jù)的排序。

到此這篇關(guān)于C++中二叉堆排序詳解的文章就介紹到這了,更多相關(guān)C++ 二叉堆排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: