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

專注于為中小企業(yè)提供成都做網(wǎng)站、網(wǎng)站設(shè)計服務(wù),電腦端+手機端+微信端的三站合一,更高效的管理,為中小企業(yè)和平免費做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了成百上千企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實現(xiàn)規(guī)模擴充和轉(zhuǎn)變。

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

叉樹節(jié)點，然后將這些節(jié)點連接起來?，F(xiàn)在為了更好地存儲二叉樹，我們學(xué)習(xí)了堆，即將二叉樹存儲在

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

最大堆：每個父節(jié)點必須大于左右孩子，而每個孩子所代表的子樹也是最大堆

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

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

首先我們來舉一個栗子，給出如下一棵二叉樹：

首先我們需要一個數(shù)組將這個二叉樹存儲起來，因為vector的操作與順序表相似，為了簡便，我們調(diào)用

庫里的vector來存儲二叉樹，只不過存儲類型為模板類T，此時我們默認建最大堆，所以要提供過向下調(diào)

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

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

往前比較，直到整個堆調(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--)  //第一個非葉子結(jié)點的父親開始
		{
			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] )  //找到左右孩子較大的一個
			{
				++child;
			}

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

通過調(diào)整整個堆變?yōu)樽畲蠖?，調(diào)整后的二叉樹如下所示

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

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

pop：由于vector沒有從堆前面直接pop的，所以要將堆的第一個元素與最后一個元素調(diào)換位置，再通過pop_back（）pop出去，再通過調(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]);  //由于沒有頭刪函數(shù)，將第一個數(shù)據(jù)和最后一個交換，再尾刪
		_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] )  //找到左右孩子較大的一個
			{
				++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;
			}
		}
	}

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

下面給出測試代碼：

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

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