C++資料結構之堆詳解

2022-04-09 19:00:13

堆的概念

堆（heap）是電腦科學中一類特殊的資料結構的統稱。堆通常是一個可以被看做一棵樹的陣列物件，即是一種順序儲存結構的完全二元樹。

提示：完全二元樹

完全二元樹：對一棵深度為k、有n個結點二元樹編號後，各節點的編號與深度為k的滿二元樹相同位置的結點的編號相同，這顆二元樹就被稱為完全二元樹。[2]

堆的性質

堆中某個結點的值總是不大於或不小於其父結點的值
堆總是一棵完全二元樹
除了根結點和最後一個左子結點可以沒有兄弟結點，其他結點必須有兄弟結點

最大堆最小堆

最大堆：根結點的鍵值是所有堆結點鍵值中最大者，且每個結點的值都比其孩子的值大。
最小堆：根結點的鍵值是所有堆結點鍵值中最小者，且每個結點的值都比其孩子的值小。

程式碼

定義

有限陣列形式

int Heap[1024];    //順序結構的二元樹

若某結點編號為i，且存在左兒子和右兒子，則他們分別對應

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

其父節點

Heap[i/2];		//i的父節點

動態陣列形式

在專案開發中，經常以動態陣列形式出現，在本文主要對這種形式進行介紹

//預設容量
#define DEFAULT_CAPCITY 128

typedef struct _Heap
{
	int *arr;		//儲存元素的動態陣列
	int size;		//元素個數
	int capacity;	//當前儲存的容量	
}Heap;

操作

只使用InitHeap()函數進行初始化即可，AdjustDown()與BuildHeap()僅為堆建立時的內部呼叫

向下調整結點

以建立最大堆為例
將“判斷最大子結點是否大於當前父結點”處的>=改為<=即可建立最小堆

//向下調整，將當前結點與其子結點調整為最大堆
//用static修飾禁止外部呼叫
static void AdjustDown(Heap& heap, int index)
{
	int cur = heap.arr[index];	//當前待調整結點
	int parent, child;

	/*
		判斷是否存在子結點大於當前結點。
		若不存在，堆是平衡的，則不調整；
		若存在，則與最大子結點與之交換，交換後該子節點若還有子結點，則以此方法繼續調整。
	*/
	for (parent = index; (parent * 2 + 1) < heap.size; parent = child)
	{
		child = parent * 2 + 1;	//左子結點

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

		//判斷最大子結點是否大於當前父結點
		if (cur >= heap.arr[child])	//將此處的>=改成<=可構建最小堆
		{
			//不大於，不需要調整
			break;
		}
		else
		{
			//大於，則交換
			heap.arr[parent] = heap.arr[child];
			heap.arr[child] = cur;
		}

	}
}

建立堆

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

初始化

//初始化堆
//引數：被初始化的堆，存放初始資料的陣列， 陣列大小
bool InitHeap(Heap &heap, int *orginal, int size)
{
	//若容量大於size，則使用預設量，否則為size
	int capacity = DEFAULT_CAPCITY>size?DEFAULT_CAPCITY:size;
	
	heap.arr = new int[capacity];	//分配記憶體，型別根據實際需要可修改
	if(!heap.arr) return false;		//記憶體分配失敗則返回False
	
	heap.capacity = capacity;		//容量
	heap.size = 0;					//元素個數置為0
	
	//若存在原始陣列則構建堆
	if(size>0)
	{
		/*
		記憶體拷貝，將orginal的元素拷貝到堆陣列arr中
		size*sizeof(int)為元素所佔記憶體空間大小
		*/
		memcpy(heap.arr,orginal, size*sizeof(int));
		heap.size = size;	//調整大小
		BuildHeap(heap);	//建堆
	}
	
	return true;
}

列印堆

實際上是一個層序遍歷[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] << " ";

	}
}

測試

main函數

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;
}

結果

完整程式碼

#include <iostream>
#include <queue>

using namespace std;

//預設容量
#define DEFAULT_CAPCITY 128
typedef struct _Heap {
	int* arr;
	int size;
	int capacity;
}Heap;

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

	/*
		判斷是否存在子結點大於當前結點。
		若不存在，堆是平衡的，則不調整；
		若存在，則與最大子結點與之交換，交換後該子節點若還有子結點，則以此方法繼續調整。
	*/
	for (parent = index; (parent * 2 + 1) < heap.size; parent = child)
	{
		child = parent * 2 + 1;	//左子結點

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

		//判斷最大子結點是否大於當前父結點
		if (cur >= heap.arr[child])	//將此處的>=改成<=可構建最小堆
		{
			//不大於，不需要調整
			break;
		}
		else
		{
			//大於，則交換
			heap.arr[parent] = heap.arr[child];
			heap.arr[child] = cur;
		}

	}


}

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

//初始化堆
//引數：被初始化的堆，存放初始資料的陣列， 陣列大小
bool InitHeap(Heap& heap, int* orginal, int size)
{
	//若容量大於size，則使用預設量，否則為size
	int capacity = DEFAULT_CAPCITY > size ? DEFAULT_CAPCITY : size;

	heap.arr = new int[capacity];	//分配記憶體，型別根據實際需要可修改
	if (!heap.arr) return false;		//記憶體分配失敗則返回False

	heap.capacity = capacity;		//容量
	heap.size = 0;					//元素個數置為0

	//若存在原始陣列則構建堆
	if (size > 0)
	{
		/*
		記憶體拷貝，將orginal的元素拷貝到堆陣列arr中
		size*sizeof(int)為元素所佔記憶體空間大小
		*/
		memcpy(heap.arr, orginal, size * sizeof(int));
		heap.size = size;	//調整大小
		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;
}

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支援it145.com。