C++數(shù)據(jù)結(jié)構(gòu)之堆詳解

更新時(shí)間：2022年04月09日 17:02:47 作者：CairBin

本文詳細(xì)講解了C++數(shù)據(jù)結(jié)構(gòu)之堆，文中通過示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下

堆的概念

堆（heap）是計(jì)算機(jī)科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱。堆通常是一個(gè)可以被看做一棵樹的數(shù)組對(duì)象，即是一種順序儲(chǔ)存結(jié)構(gòu)的完全二叉樹。

提示：完全二叉樹

完全二叉樹：對(duì)一棵深度為k、有n個(gè)結(jié)點(diǎn)二叉樹編號(hào)后，各節(jié)點(diǎn)的編號(hào)與深度為k的滿二叉樹相同位置的結(jié)點(diǎn)的編號(hào)相同，這顆二叉樹就被稱為完全二叉樹。[2]

堆的性質(zhì)

堆中某個(gè)結(jié)點(diǎn)的值總是不大于或不小于其父結(jié)點(diǎn)的值
堆總是一棵完全二叉樹
除了根結(jié)點(diǎn)和最后一個(gè)左子結(jié)點(diǎn)可以沒有兄弟結(jié)點(diǎn)，其他結(jié)點(diǎn)必須有兄弟結(jié)點(diǎn)

最大堆最小堆

最大堆：根結(jié)點(diǎn)的鍵值是所有堆結(jié)點(diǎn)鍵值中最大者，且每個(gè)結(jié)點(diǎn)的值都比其孩子的值大。
最小堆：根結(jié)點(diǎn)的鍵值是所有堆結(jié)點(diǎn)鍵值中最小者，且每個(gè)結(jié)點(diǎn)的值都比其孩子的值小。

代碼

定義

有限數(shù)組形式

int Heap[1024];    //順序結(jié)構(gòu)的二叉樹

若某結(jié)點(diǎn)編號(hào)為i，且存在左兒子和右兒子，則他們分別對(duì)應(yīng)

Heap[i*2+1];      //左兒子
Heap[i*2+2];      //右兒子

其父節(jié)點(diǎn)

Heap[i/2];		//i的父節(jié)點(diǎn)

動(dòng)態(tài)數(shù)組形式

在項(xiàng)目開發(fā)中，經(jīng)常以動(dòng)態(tài)數(shù)組形式出現(xiàn)，在本文主要對(duì)這種形式進(jìn)行介紹

//默認(rèn)容量
#define DEFAULT_CAPCITY 128

typedef struct _Heap
{
	int *arr;		//儲(chǔ)存元素的動(dòng)態(tài)數(shù)組
	int size;		//元素個(gè)數(shù)
	int capacity;	//當(dāng)前存儲(chǔ)的容量	
}Heap;

操作

只使用InitHeap()函數(shù)進(jìn)行初始化即可，AdjustDown()與BuildHeap()僅為堆建立時(shí)的內(nèi)部調(diào)用

向下調(diào)整結(jié)點(diǎn)

以創(chuàng)建最大堆為例
將“判斷最大子結(jié)點(diǎn)是否大于當(dāng)前父結(jié)點(diǎn)”處的>=改為<=即可創(chuàng)建最小堆

//向下調(diào)整，將當(dāng)前結(jié)點(diǎn)與其子結(jié)點(diǎn)調(diào)整為最大堆
//用static修飾禁止外部調(diào)用
static void AdjustDown(Heap& heap, int index)
{
	int cur = heap.arr[index];	//當(dāng)前待調(diào)整結(jié)點(diǎn)
	int parent, child;

	/*
		判斷是否存在子結(jié)點(diǎn)大于當(dāng)前結(jié)點(diǎn)。
		若不存在，堆是平衡的，則不調(diào)整；
		若存在，則與最大子結(jié)點(diǎn)與之交換，交換后該子節(jié)點(diǎn)若還有子結(jié)點(diǎn)，則以此方法繼續(xù)調(diào)整。
	*/
	for (parent = index; (parent * 2 + 1) < heap.size; parent = child)
	{
		child = parent * 2 + 1;	//左子結(jié)點(diǎn)

		//取兩個(gè)子結(jié)點(diǎn)中最大節(jié)點(diǎn),(child+1)<heap.size防止越界
		if (((child + 1) < heap.size && (heap.arr[child] < heap.arr[child + 1])))
			child++;

		//判斷最大子結(jié)點(diǎn)是否大于當(dāng)前父結(jié)點(diǎn)
		if (cur >= heap.arr[child])	//將此處的>=改成<=可構(gòu)建最小堆
		{
			//不大于，不需要調(diào)整
			break;
		}
		else
		{
			//大于，則交換
			heap.arr[parent] = heap.arr[child];
			heap.arr[child] = cur;
		}

	}
}

建立堆

//建立堆，用static修飾禁止外部調(diào)用
static void BuildHeap(Heap& heap)
{
	int i;
	//從倒數(shù)第二層開始調(diào)整（若只有一層則從該層開始）
	for (i = heap.size / 2 - 1; i >= 0; i--)
	{
		AdjustDown(heap, i);
	}
}

初始化

//初始化堆
//參數(shù)：被初始化的堆，存放初始數(shù)據(jù)的數(shù)組， 數(shù)組大小
bool InitHeap(Heap &heap, int *orginal, int size)
{
	//若容量大于size，則使用默認(rèn)量，否則為size
	int capacity = DEFAULT_CAPCITY>size?DEFAULT_CAPCITY:size;
	
	heap.arr = new int[capacity];	//分配內(nèi)存，類型根據(jù)實(shí)際需要可修改
	if(!heap.arr) return false;		//內(nèi)存分配失敗則返回False
	
	heap.capacity = capacity;		//容量
	heap.size = 0;					//元素個(gè)數(shù)置為0
	
	//若存在原始數(shù)組則構(gòu)建堆
	if(size>0)
	{
		/*
		內(nèi)存拷貝，將orginal的元素拷貝到堆數(shù)組arr中
		size*sizeof(int)為元素所占內(nèi)存空間大小
		*/
		memcpy(heap.arr,orginal, size*sizeof(int));
		heap.size = size;	//調(diào)整大小
		BuildHeap(heap);	//建堆
	}
	
	return true;
}

打印堆

實(shí)際上是一個(gè)層序遍歷[4]

//以樹狀的形式打印堆
void PrintHeapAsTreeStyle(Heap hp)
{
	queue<int> que;
	int r = 0;
	que.push(r);
	queue<int> temp;

	while (!que.empty())
	{
		r = que.front();
		que.pop();

		if (r * 2 + 1 < hp.size) temp.push(r * 2 + 1);
		if (r * 2 + 2 < hp.size) temp.push(r * 2 + 2);

		if (que.empty())
		{
			cout << hp.arr[r] << endl;
			que = temp;
			temp = queue<int>();
		}
		else
			cout << hp.arr[r] << " ";

	}
}

測(cè)試

main函數(shù)

int main()
{
	Heap hp;
	int vals[] = { 1,2,3,87,93,82,92,86,95 };

	if (!InitHeap(hp, vals, sizeof(vals) / sizeof(vals[0])))
	{
		fprintf(stderr, "初始化堆失敗！\n");
		exit(-1);
	}

	PrintHeapAsTreeStyle(hp);

	return 0;
}

結(jié)果

完整代碼

#include <iostream>
#include <queue>

using namespace std;

//默認(rèn)容量
#define DEFAULT_CAPCITY 128
typedef struct _Heap {
	int* arr;
	int size;
	int capacity;
}Heap;

//向下調(diào)整，將當(dāng)前結(jié)點(diǎn)與其子結(jié)點(diǎn)調(diào)整為最大堆
static void AdjustDown(Heap& heap, int index)
{
	int cur = heap.arr[index];	//當(dāng)前待調(diào)整結(jié)點(diǎn)
	int parent, child;

	/*
		判斷是否存在子結(jié)點(diǎn)大于當(dāng)前結(jié)點(diǎn)。
		若不存在，堆是平衡的，則不調(diào)整；
		若存在，則與最大子結(jié)點(diǎn)與之交換，交換后該子節(jié)點(diǎn)若還有子結(jié)點(diǎn)，則以此方法繼續(xù)調(diào)整。
	*/
	for (parent = index; (parent * 2 + 1) < heap.size; parent = child)
	{
		child = parent * 2 + 1;	//左子結(jié)點(diǎn)

		//取兩個(gè)子結(jié)點(diǎn)中最大節(jié)點(diǎn),(child+1)<heap.size防止越界
		if (((child + 1) < heap.size && (heap.arr[child] < heap.arr[child + 1])))
			child++;

		//判斷最大子結(jié)點(diǎn)是否大于當(dāng)前父結(jié)點(diǎn)
		if (cur >= heap.arr[child])	//將此處的>=改成<=可構(gòu)建最小堆
		{
			//不大于，不需要調(diào)整
			break;
		}
		else
		{
			//大于，則交換
			heap.arr[parent] = heap.arr[child];
			heap.arr[child] = cur;
		}

	}


}

//建立堆，用static修飾禁止外部調(diào)用
static void BuildHeap(Heap& heap)
{
	int i;
	//從倒數(shù)第二層開始調(diào)整（若只有一層則從該層開始）
	for (i = heap.size / 2 - 1; i >= 0; i--)
	{
		AdjustDown(heap, i);
	}
}

//初始化堆
//參數(shù)：被初始化的堆，存放初始數(shù)據(jù)的數(shù)組， 數(shù)組大小
bool InitHeap(Heap& heap, int* orginal, int size)
{
	//若容量大于size，則使用默認(rèn)量，否則為size
	int capacity = DEFAULT_CAPCITY > size ? DEFAULT_CAPCITY : size;

	heap.arr = new int[capacity];	//分配內(nèi)存，類型根據(jù)實(shí)際需要可修改
	if (!heap.arr) return false;		//內(nèi)存分配失敗則返回False

	heap.capacity = capacity;		//容量
	heap.size = 0;					//元素個(gè)數(shù)置為0

	//若存在原始數(shù)組則構(gòu)建堆
	if (size > 0)
	{
		/*
		內(nèi)存拷貝，將orginal的元素拷貝到堆數(shù)組arr中
		size*sizeof(int)為元素所占內(nèi)存空間大小
		*/
		memcpy(heap.arr, orginal, size * sizeof(int));
		heap.size = size;	//調(diào)整大小
		BuildHeap(heap);	//建堆
	}

	return true;
}

//以樹狀的形式打印堆
void PrintHeapAsTreeStyle(Heap hp)
{
	queue<int> que;
	int r = 0;
	que.push(r);
	queue<int> temp;

	while (!que.empty())
	{
		r = que.front();
		que.pop();

		if (r * 2 + 1 < hp.size) temp.push(r * 2 + 1);
		if (r * 2 + 2 < hp.size) temp.push(r * 2 + 2);

		if (que.empty())
		{
			cout << hp.arr[r] << endl;
			que = temp;
			temp = queue<int>();
		}
		else
			cout << hp.arr[r] << " ";

	}

}

int main()
{
	Heap hp;
	int vals[] = { 1,2,3,87,93,82,92,86,95 };

	if (!InitHeap(hp, vals, sizeof(vals) / sizeof(vals[0])))
	{
		fprintf(stderr, "初始化堆失?。n");
		exit(-1);
	}

	PrintHeapAsTreeStyle(hp);

	return 0;
}

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: