數據結構——堆

• 2022 年 4 月 9 日
• 筆記
• C/C++, heap, 二叉樹, 堆, 完全二叉樹, 數據結構

堆

堆的概念

• 堆（heap）是電腦科學中一類特殊的數據結構的統稱。堆通常是一個可以被看做一棵樹的數組對象，即是一種順序儲存結構的完全二叉樹。^[1]

提示：完全二叉樹

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

堆的性質

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

最大堆最小堆

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

• 最小堆^[3:1]：根結點的鍵值是所有堆結點鍵值中最小者，且每個結點的值都比其孩子的值小。

程式碼

定義

有限數組形式

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

結果

95
93 92
87 1 82 3
86 2

完整程式碼

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

參考