回顧前面的知識(shí)，我們學(xué)了二叉樹(shù)，而二叉樹(shù)有很多種存儲(chǔ)方式，比如一維數(shù)組存儲(chǔ)，

藤縣ssl適用于網(wǎng)站、小程序/APP、API接口等需要進(jìn)行數(shù)據(jù)傳輸應(yīng)用場(chǎng)景，ssl證書(shū)未來(lái)市場(chǎng)廣闊！成為創(chuàng)新互聯(lián)的ssl證書(shū)銷售渠道，可以享受市場(chǎng)價(jià)格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：18980820575（備注：SSL證書(shū)合作）期待與您的合作！

鏈表存儲(chǔ)，在剛剛學(xué)習(xí)建立二叉樹(shù)的時(shí)候，我們用的是鏈表存儲(chǔ)的方式，也就是利用結(jié)構(gòu)體定義一個(gè)二

叉樹(shù)節(jié)點(diǎn)，然后將這些節(jié)點(diǎn)連接起來(lái)。現(xiàn)在為了更好地存儲(chǔ)二叉樹(shù)，我們學(xué)習(xí)了堆，即將二叉樹(shù)存儲(chǔ)在

一個(gè)一維數(shù)組里面，由于按照不同的存儲(chǔ)順序，可以將一個(gè)堆分為大堆和最小堆。

大堆：每個(gè)父節(jié)點(diǎn)必須大于左右孩子，而每個(gè)孩子所代表的子樹(shù)也是大堆

最小堆：每個(gè)父節(jié)點(diǎn)必須小于左右孩子，而每個(gè)孩子所代表的子樹(shù)也是最小堆

那么如何將一個(gè)堆變成一個(gè)大堆或者最小堆呢，就是通過(guò)向下調(diào)整法或者向上調(diào)整法，下面會(huì)做詳細(xì)的說(shuō)明。

首先我們來(lái)舉一個(gè)栗子，給出如下一棵二叉樹(shù)：

首先我們需要一個(gè)數(shù)組將這個(gè)二叉樹(shù)存儲(chǔ)起來(lái)，因?yàn)関ector的操作與順序表相似，為了簡(jiǎn)便，我們調(diào)用

庫(kù)里的vector來(lái)存儲(chǔ)二叉樹(shù)，只不過(guò)存儲(chǔ)類型為模板類T，此時(shí)我們默認(rèn)建大堆，所以要提供過(guò)向下調(diào)

整法來(lái)調(diào)整，為了使每棵子樹(shù)都是父節(jié)點(diǎn)大，我們先從最后一個(gè)節(jié)點(diǎn)找起，然后找到該節(jié)點(diǎn)的父節(jié)

點(diǎn)，比較父節(jié)點(diǎn)和兩個(gè)子節(jié)點(diǎn)的大小，若左右節(jié)點(diǎn)有一個(gè)比父節(jié)點(diǎn)大，則和父節(jié)點(diǎn)交換值，然后依次

往前比較，直到整個(gè)堆調(diào)整為大堆。

代碼如下：

#pragma once
#include
#include

using namespace std;

template
class Heap
{
public:
	Heap()
	{}
	//建堆
	Heap(const T* a,size_t size)
	{
		for (size_t i = 0; i < size; i++)//將數(shù)組中的數(shù)據(jù)放到堆里去
		{
			_a.push_back(a[i]);
		}

		for (int j = (_a.size() - 2) / 2; j >= 0; j--)  //第一個(gè)非葉子結(jié)點(diǎn)的父親開(kāi)始
		{
			AdjustDown(j);
		}
	}
	
protected:
	void AdjustDown(size_t parent)
	{
		int child = parent * 2 + 1;; //找到左孩子

 		while (child< _a.size())
		{
			if ((child + 1 < _a.size())&&_a[child] < _a[child + 1] )  //找到左右孩子較大的一個(gè)
			{
				++child;
			}

			if (_a[child] > _a[parent])   //如果孩子比父親大，交換孩子和父親的值
			{
				swap(_a[child], _a[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}
protected:
	vector _a;
};

通過(guò)調(diào)整整個(gè)堆變?yōu)榇蠖?，調(diào)整后的二叉樹(shù)如下所示

那么建立好堆之后，在對(duì)數(shù)據(jù)進(jìn)行操作的時(shí)候?qū)Χ岩灿幸欢ǖ挠绊?，所以下面我們?lái)簡(jiǎn)單寫(xiě)一下堆的pop和push。

push：可以直接調(diào)用vector的push_back（），然后再通過(guò)向上調(diào)整法調(diào)整變成大堆

pop：由于vector沒(méi)有從堆前面直接pop的，所以要將堆的第一個(gè)元素與最后一個(gè)元素調(diào)換位置，再通過(guò)pop_back（）pop出去，再通過(guò)調(diào)整變成大堆。

具體代碼如下：

void push(const T& x)
	{
		_a.push_back(x);

		AdjustUp(_a.size() - 1);
	}
	void pop()
	{
		assert(!_a.empty());

		swap(_a[0], _a[_a.size() - 1]);  //由于沒(méi)有頭刪函數(shù)，將第一個(gè)數(shù)據(jù)和最后一個(gè)交換，再尾刪
		_a.pop_back();

		for (int j = (_a.size() - 2) / 2; j >= 0; j--)  //調(diào)整為大堆
		{
			AdjustDown(j);
		}
	}


protected:
	void AdjustDown(size_t parent)
	{
		int child = parent * 2 + 1;; //找到左孩子

 		while (child< _a.size())
		{
			if ((child + 1 < _a.size())&&_a[child] < _a[child + 1] )  //找到左右孩子較大的一個(gè)
			{
				++child;
			}

			if (_a[child] > _a[parent])   //如果孩子比父親大，交換孩子和父親的值
			{
				swap(_a[child], _a[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}

	void AdjustUp(size_t child)
	{
		int parent = (child - 1) / 2;

		while (child>0)
		{
			if (_a[child]>_a[parent])
			{
				swap(_a[child], _a[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}

以上便是堆的建立以及簡(jiǎn)單的操作，小伙伴們看明白了么？

下面給出測(cè)試代碼：

#include"Heap.h"


void test()
{
	int array[10] = { 7, 14, 12, 15, 10, 11, 13, 16, 9, 8 };
	Heap hp1(array, 10);
	hp1.push(17);
	hp1.pop();   
}

int main()
{
	test();
	return 0;
}

由于這里只給出了具體方法，類的成員沒(méi)有給完全，小伙伴們可以下去自行補(bǔ)全哦，重要的是方法，可能我給出的方法也有一定的不足之處，還希望大家指出共同進(jìn)步！

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國(guó)云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開(kāi)啟，新人活動(dòng)云服務(wù)器買多久送多久。

網(wǎng)站欄目：簡(jiǎn)單堆的創(chuàng)建和操作-創(chuàng)新互聯(lián)
地址分享：http://weahome.cn/article/ccpdph.html