C語言怎么實現(xiàn)堆及堆的結(jié)構(gòu)與接口

本文小編為大家詳細(xì)介紹“C語言怎么實現(xiàn)堆及堆的結(jié)構(gòu)與接口”，內(nèi)容詳細(xì)，步驟清晰，細(xì)節(jié)處理妥當(dāng)，希望這篇“C語言怎么實現(xiàn)堆及堆的結(jié)構(gòu)與接口”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學(xué)習(xí)新知識吧。

一、堆的結(jié)構(gòu)及實現(xiàn)（重要）

1.1 二叉樹的順序結(jié)構(gòu)

普通的二叉樹是不適合用數(shù)組來存儲的，因為可能會存在大量的空間浪費(fèi)。而完全二叉樹更適合使用順序結(jié)構(gòu)存儲。在現(xiàn)實中我們通常把堆 (一種完全二叉樹) 使用順序結(jié)構(gòu)的數(shù)組來存儲，需要注意的是這里的堆和操作系統(tǒng)虛擬進(jìn)程地址空間中的堆是兩回事，一個是數(shù)據(jù)結(jié)構(gòu)，一個是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段。

1.2 堆的概念及結(jié)構(gòu)

堆(Heap)是計算機(jī)科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱。堆通常是一個可以被看做一棵完全二叉樹的數(shù)組對象。堆總是滿足下列性質(zhì)：

• 堆中某個結(jié)點的值總是不大于或不小于其父結(jié)點的值；

• 堆總是一棵完全二叉樹。

堆是非線性數(shù)據(jù)結(jié)構(gòu)，相當(dāng)于一維數(shù)組，有兩個直接后繼。

【大根堆和小根堆】：

根結(jié)點最大的堆叫做大根堆，樹中所有父親都大于或等于孩子。

根結(jié)點最小的堆叫做小根堆，樹中所有父親都小于或等于孩子。

【思考】這個大根堆和小根堆有什么特點呢？

最值總在 0 號位，根據(jù)這個特點我們就可以做很多事情，比如TopK問題 (在一堆數(shù)據(jù)里面找到前 K 個最大 / 最小的數(shù))，生活中也有很多實例，比如點餐軟件中有上千家店鋪，我想選出該地區(qū)好評最多的十家川菜店，我們不用對所有數(shù)據(jù)排序，只需要取出前 K 個最大 / 最小數(shù)據(jù)。使用堆排序效率也更高。

1.3 堆的實現(xiàn)

1.3.1 堆的向下調(diào)整算法

下面給出一個數(shù)組，邏輯上看做一顆完全二叉樹。我們通過從根節(jié)點開始的向下調(diào)整算法可以把它調(diào)整成一個小堆。向下調(diào)整算法有一個前提：該節(jié)點的左右子樹必須是一個 (大 / 小) 堆，才能調(diào)整。

int array[] = { 27,15,19,18,28,34,65,49,25,37 }; // 根節(jié)點的左右子樹都是小堆

上面的數(shù)組，因為根節(jié)點的左右子樹都是小堆，所以我們從根節(jié)點開始調(diào)整，將其調(diào)成小堆。

向下調(diào)整算法思路（調(diào)成小堆）：

從根節(jié)點開始，不斷往下調(diào)。

選出根節(jié)點的左右孩子中「最小的孩子」，與「父親」進(jìn)行比較。

• 如果父親小于孩子，就不需處理了，整個樹已經(jīng)是小堆了。

• 如果父親大于孩子，就跟父親交換位置，并將原來小的孩子的位置當(dāng)成父親繼續(xù)向下進(jìn)行調(diào)整，直到調(diào)整到葉子結(jié)點為止。

向下調(diào)整算法過程演示（調(diào)成小堆，把大的節(jié)點往下調(diào)整）：

向下調(diào)整算法代碼：

// 向下調(diào)整算法，建小堆，把大的節(jié)點往下調(diào)整
// 前提是：左右子樹都是小堆
void AdjustDown(int* a, int size, int parent)
{
	// 指向左孩子，默認(rèn)左孩子最小
	int child = parent * 2 + 1;
	while (child < size)
	{
		// 1. 選出左右孩子最小的那個，先判斷右孩子是否存在
		if (child + 1 < size && a[child] > a[child + 1])
		{
			child++; // 指向右孩子
		}
		// 2. 最小的孩子與父親比較
		if (a[parent] > a[child]) // 如果父親大于孩子
		{
			// 父親與孩子交換位置
			Swap(&a[parent], &a[child]);
			// 更新父子下標(biāo)，原先最小的孩子作為父親，繼續(xù)往下調(diào)
			parent = child;
			child = parent * 2 + 1;
		}
		else // 如果父親小于孩子，說明已經(jīng)為小堆了，停止調(diào)整
		{
			break;
		}
	}
}

1.3.2 向下調(diào)整算法的時間復(fù)雜度

我們以滿二叉樹計算，最壞情況下，向下調(diào)整算法最多進(jìn)行滿二叉樹的高度減1次比較，則說明向下調(diào)整算法最多調(diào)整滿二叉樹的高度減1次，n 個節(jié)點的滿二叉樹高度為 log2(n+1)，估算后所以時間復(fù)雜度為 O(log2n)。

1.3.3 堆的創(chuàng)建（向下調(diào)整）

下面給出一個數(shù)組，這個數(shù)組邏輯上可以看做一顆完全二叉樹，但不是一個堆，我們需要通過算法把它構(gòu)建成一個堆。如果根節(jié)點左右子樹不是一個 (大 / 小) 堆，我們應(yīng)該怎么調(diào)整呢？

我們倒著調(diào)整，從下到上，從「倒數(shù)第一個非葉子節(jié)點的子樹」開始，依次遍歷完所有非葉子節(jié)點，分別對每個子樹進(jìn)行「向下調(diào)整」成 (大 / 小) 堆，一直調(diào)整到「根節(jié)點」，就可以建成一個 (大 / 小) 堆。

為什么要倒著調(diào)整呢？因為這樣我們可以把「倒數(shù)第一個非葉子節(jié)點的子樹」的左右子樹看成是一個 (大 / 小) 堆，此時才能去使用向下調(diào)整算法。比如下圖中的黃色填充的子樹，3 的左子樹 6 就可以看成是一個大堆。

【實例】：將下面的數(shù)組建成一個大堆

int a[] = { 1,5,3,8,7,6 };

建堆過程演示（以建大堆為例）：從下到上，依次遍歷完所有非葉子節(jié)點，分別對每個子樹進(jìn)行向下調(diào)整。

依次對 每一步 中，方框內(nèi)的樹 進(jìn)行 向下調(diào)整 為一個 大堆。

建堆代碼：

// 交換函數(shù)
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
// 向下調(diào)整算法，建大堆，把小的節(jié)點往下調(diào)
// 前提是：左右子樹都是大堆
void AdjustDown(int* a, int size, int parent)
{
	// 指向左孩子，默認(rèn)左孩子最大
	int child = parent * 2 + 1;
	while (child < size)
	{
		// 1. 選出左右孩子最大的那個，先判斷右孩子是否存在
		if (child + 1 < size && a[child] < a[child + 1])
		{
			child++; // 指向右孩子
		}
		// 2. 最大的孩子與父親比較
		if (a[parent] < a[child]) // 如果父親小于孩子
		{
			// 父親與孩子交換位置
			Swap(&a[parent], &a[child]);
			// 更新父子下標(biāo)，原先最大的孩子作為父親，繼續(xù)往下調(diào)
			parent = child;
			child = parent * 2 + 1;
		}
		else // 如果父親大于孩子，說明已經(jīng)為大堆了，停止調(diào)整
		{
			break;
		}
	}
}
void HeapSort(int* a, int size)
{
    /* 建堆（大堆）
    * 倒著調(diào)整，從倒數(shù)第一個非葉子節(jié)點的子樹進(jìn)行向下調(diào)整，直到調(diào)整到根節(jié)點的樹
    */
	int parent = ((size - 1) - 1) / 2; // 最后一個葉子節(jié)點的父親的下標(biāo)
	for (int i = parent; i >= 0; i--)  // 從下到上，依次遍歷完所有子樹，分別對其進(jìn)行調(diào)整
	{
		AdjustDown(a, size, i);
	}
    /* 堆排序
    * 排升序 --> 建大堆，每次選出一個最大的數(shù)放到最后
    * 排降序 --> 建小堆，每次選出一個最小的數(shù)放到最后
    */
    // 下面是排升序：
	int end = size - 1; // 記錄堆中最后一個元素的下標(biāo)
	while (end > 0)
	{
		Swap(&a[0], &a[end]);  // 將堆頂元素和堆中最后一個元素交換，把最大的數(shù)(堆頂)放到最后
		AdjustDown(a, end, 0); // 不看最后一個數(shù)，從根節(jié)點開始，對前面的數(shù)進(jìn)行向下調(diào)整成大堆
		end--;
	}
}

1.3.4 堆排序

排升序 --> 建大堆：

【思考】排升序，建小堆可以嗎？-- 可以是可以，但沒啥意思。

首先對 n 個數(shù)建小堆，選出最小的數(shù)，接著對剩下的 n-1 個數(shù)建小堆，選出第2小的數(shù)，不斷重復(fù)上述過程……。建 n 個數(shù)的堆時間復(fù)雜度是O(N)，所以上述操作時間復(fù)雜度為O(N2)，效率太低，尤其是當(dāng)數(shù)據(jù)量大的時候，效率更低，同時堆的價值沒有被體現(xiàn)出來，還不如用直接排序。

【最佳方法】排升序，因為數(shù)字越來越大，需要找到最大的數(shù)字，得建大堆

• 首先對 n 個數(shù)建大堆。

• 將最大的數(shù)（堆頂）和最后一個數(shù)交換，把最大的數(shù)放到最后。

• 前面 n-1 個數(shù)的堆結(jié)構(gòu)沒有被破壞（最后一個數(shù)不看做堆里面的），根節(jié)點的左右子樹依舊是大堆，所以我們進(jìn)行一次向下調(diào)整成大堆即可選出第2大的數(shù)，放到倒數(shù)第二個位置，然后重復(fù)上述步驟……。

【時間復(fù)雜度】：建堆時間復(fù)雜度為O(N)，向下調(diào)整時間復(fù)雜度為O(log2N)，這里我們最多進(jìn)行N-2次向下調(diào)整，所以堆排序時間復(fù)雜度為O(N*log2N)，效率是很高的。

排降序 --> 建小堆：

【最佳方法】排降序，因為數(shù)字越來越小，需要找到最小的數(shù)字，得建小堆

• 首先對 n 個數(shù)建小堆。

• 將最小的數(shù)（堆頂）和最后一個數(shù)交換，把最小的數(shù)放到最后。

• 前面 n-1 個數(shù)的堆結(jié)構(gòu)沒有被破壞（最后一個數(shù)不看做堆里面的），根節(jié)點的左右子樹依舊是小堆，所以我們進(jìn)行一次向下調(diào)整成小堆即可選出第2小的數(shù)，放到倒數(shù)第二個位置，然后重復(fù)上述步驟……。

• 【時間復(fù)雜度】：建堆時間復(fù)雜度為O(N)，向下調(diào)整時間復(fù)雜度為O(log2N)，這里我們最多進(jìn)行N-2次向下調(diào)整，所以堆排序時間復(fù)雜度為O(N*log2N)，效率是很高的。

1.3.5 建堆的時間復(fù)雜度

因為堆是完全二叉樹，而滿二叉樹也是完全二叉樹，此處為了簡化使用滿二叉樹來證明，計算起來比較好算(時間復(fù)雜度本來看的就是近似值，多幾個節(jié)點不影響最終結(jié)果)：

建堆要從倒數(shù)第一個非葉子節(jié)點開始調(diào)整，也即是從倒數(shù)第二層開始調(diào)，可得出時間復(fù)雜度公式：

T ( n ) = ∑ ( 每 層 節(jié) 點 數(shù) ∗ ( 堆 的 高 度 − 當(dāng) 前 層 數(shù) ) )

所以，建堆的時間復(fù)雜度為O(N)。

【上面學(xué)了那么多，這里小小總結(jié)一下】

• 堆的向下調(diào)整算法就是，在該節(jié)點左右子樹都是一個小/大堆的前提下，將以該節(jié)點為根的樹調(diào)整成一個小/大堆。

• 堆的創(chuàng)建就是倒著調(diào)整，從下到上，從倒數(shù)第一個非葉子節(jié)點的子樹開始，依次遍歷完所有子樹，分別對其進(jìn)行向下調(diào)整。

• 時間復(fù)雜度：堆的向下調(diào)整算法為O(log2N)，堆的創(chuàng)建為O(N)。

二、堆的相關(guān)接口實現(xiàn)（以大堆為例）

首先新建一個工程（ 博主使用的是 VS2019 ）

• Heap.h（堆的類型定義、接口函數(shù)聲明、引用的頭文件）

• Heap.c（堆接口函數(shù)的實現(xiàn)）

• Test.c（主函數(shù)、測試堆各個接口功能）

Heap.h 頭文件代碼如下：

#pragma once
#include<stdio.h>   // printf, perror
#include<stdbool.h> // bool
#include<assert.h>  // assert
#include<stdlib.h>  // malloc, free
#include<string.h>  // memcpy
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a; // 指向動態(tài)開辟的數(shù)組
	int size;      // 數(shù)組中有效元素個數(shù)
	int capacity;  // d容量
}Heap;
// 交換函數(shù)
void Swap(HPDataType* a, HPDataType* b);
// 向下調(diào)整函數(shù)（調(diào)成大堆，把小的往下調(diào)）
void AdjustDown(HPDataType* a, int size, int parent);
// 向上調(diào)整函數(shù)（調(diào)成大堆，把大的往上調(diào)）
void AdjustUp(HPDataType* a, int child);
// 初始化堆
void HeapInit(Heap* php, HPDataType* arr, int n);
// 銷毀堆
void HeapDestroy(Heap* php);
// 插入元素（插入到堆的末尾），插入后并保持它依然是堆
void HeapPush(Heap* php, int x);
// 刪除堆頂元素，刪除后保持它依然是堆
void HeapPop(Heap* php);
// 獲取堆頂元素，也即是最值
HPDataType HeapTop(Heap* php);
// 判斷堆是否為空，為空返回true，不為空返回false
bool HeapEmpty(Heap* php);
// 獲取堆中有效元素個數(shù)
int HeapSize(Heap* php);
// 打印堆
void HeapPrint(Heap* php);

2.1 堆的初始化

堆的初始化，首先需要實現(xiàn)一個向下調(diào)整算法：

// 交換函數(shù)
void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}
// 向下調(diào)整算法（調(diào)成大堆，把小的往下調(diào)）
void AdjustDown(HPDataType* a, int size, int parent)
{
	// 左孩子下標(biāo)，初始默認(rèn)左孩子最大
	int child = parent * 2 + 1;
	while (child < size)
	{
		// 選出左右孩子最大的那個，先判斷右孩子是否存在
		if (child + 1 < size && a[child] < a[child + 1])
		{
			child++; // 右孩子最大
		}
		// 最大的孩子與父親比較
		if (a[parent] < a[child]) // 如果父親小于孩子
		{
			// 父親與孩子交換位置
			Swap(&a[parent], &a[child]);
			// 更新父子下標(biāo)，原先最大的孩子作為父親，繼續(xù)往下調(diào)
			parent = child;
			child = parent * 2 + 1;
		}
		else // 如果父親大于孩子，說明已經(jīng)為大堆了，停止調(diào)整
		{
			break;
		}
	}
}

堆的初始化代碼：

// 初始化堆，用一個給定的數(shù)組來初始化
void HeapInit(Heap* php, HPDataType* arr, int n)
{
	assert(php); // 斷言
	// 動態(tài)開辟n個空間
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	// 把給定數(shù)組的各元素值拷貝過去
	memcpy(php->a, arr, sizeof(HPDataType) * n);
	php->size = php->capacity = n;
	// 建堆(建大堆）
	int parent = ((php->size - 1) - 1) / 2; // 倒數(shù)第一個非葉子節(jié)點下標(biāo)
	for (int i = parent; i >= 0; i--) // 從下到上，依次遍歷完所有子樹，分別對其進(jìn)行調(diào)整
	{
		AdjustDown(php->a, php->size, i);
	}
}

2.2 堆的銷毀

// 銷毀堆
void HeapDestroy(Heap* php)
{
	assert(php);
	free(php->a); // 釋放動態(tài)開辟的空間
	php->a = NULL;
	php->size = php->capacity = 0;
}

2.3 堆的插入

先插入一個新元素到數(shù)組的尾上，從插入的新元素開始，進(jìn)行向上調(diào)整算法，直到滿足（大/?。┒?。

堆的插入過程演示：

堆的插入，首先需要實現(xiàn)一個向上調(diào)整算法：

// 向上調(diào)整算法（調(diào)成大堆，把大的往上調(diào)）
void AdjustUp(HPDataType* a, int child)
{
	// 父節(jié)點的下標(biāo)
	int parent = (child - 1) / 2;
	//while (parent >= 0) parent不會小于0
	while (child > 0)
	{
		// 孩子與父親進(jìn)行比較
		if (a[child] > a[parent]) // 如果孩子大于父親
		{
			// 孩子與父親交換
			Swap(&a[child], &a[parent]);

			// 更新父子下標(biāo)，原先父親作為孩子，繼續(xù)往上調(diào)
			child = parent;
			parent = (child - 1) / 2;
		}
		else // 如果孩子小于父親，說明已經(jīng)為大堆了，停止調(diào)整
		{
			break;
		}
	}
}

堆的插入代碼：

// 插入元素（插入到堆的末尾），插入后并保持它依然是堆
void HeapPush(Heap* php, int x)
{
	assert(php);
	// 先檢查空間是否已滿
	if (php->capacity == php->size)
	{
		// 增容兩倍
		php->capacity *= 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity);
		if (tmp != NULL)
		{
			php->a = tmp;
			tmp = NULL;
		}
	}
	// 插入元素
	php->a[php->size] = x;
	php->size++;
	// 從插入的元素開始，進(jìn)行向上調(diào)整，保持它依然是堆
	AdjustUp(php->a, php->size - 1);
}

2.4 堆的刪除

• 將堆頂元素和最后一個元素交換（這樣就變成尾刪了，很方便）

• 刪除堆中最后一個元素

• 從根節(jié)點開始，對剩下元素進(jìn)行向下調(diào)整，調(diào)成（大/?。┒?/p>

堆的刪除過程演示：

堆的插入，首先需要實現(xiàn)一個向下調(diào)整算法：前面已經(jīng)實現(xiàn)過了，這里就不展示了。

堆的刪除代碼：

// 刪除堆頂元素，刪除后保持它依然是堆
void HeapPop(Heap* php)
{
	assert(php);
	assert(!HeapEmpty(php)); // 堆不能為空
	// 將堆頂元素和最后一個元素交換
	Swap(&php->a[0], &php->a[php->size - 1]);
	// 刪除堆中最后一個元素
	php->size--;
	// 從根節(jié)點開始，對剩下元素進(jìn)行向下調(diào)整成大堆，保持它依然是堆
	AdjustDown(php->a, php->size, 0);
}

2.5 獲取堆頂元素

// 獲取堆頂元素，也即是最值
HPDataType HeapTop(Heap* php)
{
	assert(php);
	assert(!HeapEmpty(php)); // 堆不能為空
	return php->a[0];
}

2.6 堆的判空

// 判斷堆是否為空，為空返回true，不為空返回false
bool HeapEmpty(Heap* php)
{
	assert(php);
	return php->size == 0;
}

2.7 找出堆中前k個最大元素

堆的相關(guān)接口實現(xiàn)好了，因為是大堆，所以我們可以很方便的來找出堆中前 k 個最大元素。

這里要和前面的堆排序區(qū)分開哦，這里我們并不是在堆中對所有元素排好序。

void TestHeap()
{
	int a[] = { 1,5,3,8,7,6 };
	Heap hp;
	HeapInit(&hp, a, sizeof(a) / sizeof(a[0])); // 初始化堆
	int k = 0;
	scanf("%d", &k);
	printf("找出堆中前%d個最大元素：\n", k);
	while (!HeapEmpty(&hp) && k--)
	{
		printf("%d ", HeapTop(&hp)); // 獲取堆頂元素
		HeapPop(&hp); // 刪除堆頂元素
	}
	printf("\n");
}

運(yùn)行結(jié)果：

2.8 堆的創(chuàng)建（向上調(diào)整）

下面給出一個數(shù)組，這個數(shù)組邏輯上可以看做一顆完全二叉樹，但不是一個堆，我們需要通過「向上調(diào)整算法」把它構(gòu)建成一個堆。如果根節(jié)點左右子樹不是一個 (大 / 小) 堆，我們應(yīng)該怎么調(diào)整呢？

我們從上到下，從「第一個節(jié)點（也就是根節(jié)點）的左孩子」開始，依次遍歷完所有節(jié)點，分別對每個節(jié)點進(jìn)行「向上調(diào)整」，一直到「最后一個節(jié)點」，就可以建成一個 (大 / 小) 堆。

我們把數(shù)組中的「第一個元素」看作是一個「堆」，剩余的元素依次插入到這個「堆」中。前面我們也實現(xiàn)了堆的插入接口，原理就是向上調(diào)整。

// 向上調(diào)整算法建堆
void CreateHeap(int* a, int size)
{
	// 把第一個元素看作是堆，剩余的元素依次插入堆中
	for (int i = 1; i < size; i++)
	{
		AdjustUp(a, i);
	}
}

讀到這里，這篇“C語言怎么實現(xiàn)堆及堆的結(jié)構(gòu)與接口”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領(lǐng)會，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。