1.堆

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

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

堆的性質(zhì)：

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

• 堆總是一棵完全二叉樹

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

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

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

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

如下圖所示為一個向下調(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;
	//孩子超過數(shù)組下標(biāo)結(jié)束
	while (child < n)
	{
		//child始終左右孩子中小的那個
		if (a[child + 1] < a[child] && child + 1 <n)//防止沒有右孩子
		{
			++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)整算法

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

如下圖所示插入一個數(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ù)第一個非葉子節(jié)點(diǎn)的位置開始向下調(diào)整

如下圖所示可以按圖中的步驟依次向下調(diào)整
最后一個非葉子節(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)，我們將每次建好的小堆的最后一個葉子節(jié)點(diǎn)和根節(jié)點(diǎn)進(jìn)行交換，交換后不把最后一個數(shù)看作堆里的數(shù)據(jù)，此時根的左右子樹依舊是大堆，然后我們再用向下調(diào)整算法選出次小的如此循環(huán)直到堆里剩一個數(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;
	//把最小的換到最后一個位置，不把最后一個數(shù)看作堆里的
	//每次選出剩下數(shù)中最小的
	//從后往前放
	while (end > 0)
	{
		int tem = a[end];
		a[end] = a[0];
		a[0] = tem;
		//選出次小的數(shù)
		AdjustDown(a, end, 0);
		--end;
	}
}

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

最壞的情況及滿二叉樹，且每個節(jié)點(diǎn)都需要調(diào)整

由以上推論過程可得建堆的時間復(fù)雜度為O(N);
向下調(diào)整算法的時間復(fù)雜度為O(log2N);
所以堆排序的時間復(fù)雜度為O(N*log2N);

到此這篇關(guān)于一文學(xué)會數(shù)據(jù)結(jié)構(gòu)-堆的文章就介紹到這了,更多相關(guān)堆內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論