簡單堆的創(chuàng)建和操作

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

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

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

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

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

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

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

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

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

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

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

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

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

代碼如下：

#pragma once
#include<assert.h>
#include<vector>

using namespace std;

template<class T>
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é)點(diǎn)的父親開始
		{
			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<T> _a;
};

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

那么建立好堆之后，在對數(shù)據(jù)進(jìn)行操作的時候?qū)Χ岩灿幸欢ǖ挠绊懀韵旅嫖覀儊砗唵螌懸幌露训膒op和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<int> hp1(array, 10);
	hp1.push(17);
	hp1.pop();   
}

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

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