一文學(xué)會(huì)數(shù)據(jù)結(jié)構(gòu)-堆

更新時(shí)間：2021年08月26日 16:45:08 作者：雙魚211

本文主要介紹了數(shù)據(jù)結(jié)構(gòu)-堆，文中通過(guò)圖片和大量的代碼講解的非常詳細(xì)，需要學(xué)習(xí)的朋友可以參考下這篇文章，希望可以幫助到你

2.1堆的向下調(diào)整算法(建小堆)
2.2 堆向下調(diào)整算法(建小堆)實(shí)現(xiàn)
2.3 堆的向上調(diào)整算法
2.4 向上調(diào)整算法(建小堆)實(shí)現(xiàn)
2.5 數(shù)組建堆算法(建小堆)
2.6 數(shù)組建堆算法(建小堆)實(shí)現(xiàn)
2.7 堆排序(降序)
2.8 堆排序(降序)實(shí)現(xiàn)
2.9 建堆的時(shí)間復(fù)雜度

1.堆

大根堆：所有父節(jié)點(diǎn)大于等于孩子節(jié)點(diǎn)

在這里插入圖片描述

小根堆：所有父節(jié)點(diǎn)小于等于孩子節(jié)點(diǎn)

在這里插入圖片描述

堆的性質(zhì)：

• 堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值

• 堆總是一棵完全二叉樹(shù)

2.堆的實(shí)現(xiàn)

堆的實(shí)現(xiàn)請(qǐng)點(diǎn)擊—> 實(shí)現(xiàn)堆排序?qū)嵗?/a>

現(xiàn)在我們給出一個(gè)數(shù)組，邏輯上看做一顆完全二叉樹(shù)。我們通過(guò)從根節(jié)點(diǎn)開(kāi)始的向下調(diào)整算法可以把它調(diào)整成一個(gè)小堆。

int a[] = {27,15,19,18,28,34,65,49,25,37};

2.1堆的向下調(diào)整算法(建小堆)

向下調(diào)整算法-前提：當(dāng)前樹(shù)的左右子樹(shù)必須都是一個(gè)小堆
向下調(diào)整算法的核心思想：選出左右孩子中小的哪一個(gè)，跟父親交換，小的往上浮，大的往下沉，如果要建大堆則相反

如下圖所示為一個(gè)向下調(diào)整法調(diào)小堆

在這里插入圖片描述

2.2 堆向下調(diào)整算法(建小堆)實(shí)現(xiàn)

//堆向下調(diào)整算法
//建小堆
void AdjustDown(int* a, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;
	//孩子超過(guò)數(shù)組下標(biāo)結(jié)束
	while (child < n)
	{
		//child始終左右孩子中小的那個(gè)
		if (a[child + 1] < a[child] && child + 1 <n)//防止沒(méi)有右孩子
		{
			++child;
		}
		//小的往上浮，大的往下浮
		if (a[child] < a[parent])
		{
			int tem = a[parent];
			a[parent] = a[child];
			a[child] = tem;
			parent = child;
			child = parent * 2 + 1;
		}
		//中途child>parent則已滿足小堆，直接break
		else
		{
			break;
		}
	}
}

2.3 堆的向上調(diào)整算法

使用場(chǎng)景：向堆中插入數(shù)據(jù)，需要使用向上調(diào)整算法調(diào)整，因?yàn)橄蚨阎胁迦霐?shù)據(jù)是將數(shù)據(jù)插入到下標(biāo)為size的位置，此時(shí)就不滿足小堆(大堆)，因此，需要堆其進(jìn)行調(diào)整，向上調(diào)整算法和向下調(diào)整算法思路類似，此處以小堆為例，向上調(diào)整法只需從插入的節(jié)點(diǎn)位置開(kāi)始和父節(jié)點(diǎn)比較，若a[chaild]<a[parent],則交換，若a[chaild]>=a[parent]則說(shuō)明越界滿足小堆，直接break

如下圖所示插入一個(gè)數(shù)據(jù)使用向上調(diào)整法調(diào)整

在這里插入圖片描述

2.4 向上調(diào)整算法(建小堆)實(shí)現(xiàn)

//堆的向上調(diào)整算法
//建小堆
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			int tem = a[parent];
			a[parent] = a[child];
			a[child] = tem;
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

2.5 數(shù)組建堆算法(建小堆)

若左右子樹(shù)不是小堆——想辦法把左右子樹(shù)處理成小堆
可以從倒數(shù)第一個(gè)非葉子節(jié)點(diǎn)的位置開(kāi)始向下調(diào)整

如下圖所示可以按圖中的步驟依次向下調(diào)整
最后一個(gè)非葉子節(jié)點(diǎn)的下標(biāo)為 (n-1-1)/2

在這里插入圖片描述

2.6 數(shù)組建堆算法(建小堆)實(shí)現(xiàn)

	int n = sizeof(a) / sizeof(int);
	//數(shù)組建堆算法
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(arr, n, i);
	}

2.7 堆排序(降序)

下面我們將上面建好的小堆進(jìn)行降序排序

堆排序(降序)的核心思想：因?yàn)榻ㄐ《芽梢赃x出最小的數(shù)即根節(jié)點(diǎn)，我們將每次建好的小堆的最后一個(gè)葉子節(jié)點(diǎn)和根節(jié)點(diǎn)進(jìn)行交換，交換后不把最后一個(gè)數(shù)看作堆里的數(shù)據(jù)，此時(shí)根的左右子樹(shù)依舊是大堆，然后我們?cè)儆孟蛳抡{(diào)整算法選出次小的如此循環(huán)直到堆里剩一個(gè)數(shù)結(jié)束

• 升序建大堆 • 降序建小堆

2.8 堆排序(降序)實(shí)現(xiàn)

//降序
void HeapSort(int* a, int n)
{
	//建小堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	//把最小的換到最后一個(gè)位置，不把最后一個(gè)數(shù)看作堆里的
	//每次選出剩下數(shù)中最小的
	//從后往前放
	while (end > 0)
	{
		int tem = a[end];
		a[end] = a[0];
		a[0] = tem;
		//選出次小的數(shù)
		AdjustDown(a, end, 0);
		--end;
	}
}