日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

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

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

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

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

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

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

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

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

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

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

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

整法來調(diào)整，為了使每棵子樹都是父節(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)的父親開始
		{
			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;
};

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

那么建立好堆之后，在對數(shù)據(jù)進(jìn)行操作的時(shí)候?qū)Χ岩灿幸欢ǖ挠绊懀韵旅嫖覀儊砗唵螌懸幌露训膒op和push。

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

pop：由于vector沒有從堆前面直接pop的，所以要將堆的第一個(gè)元素與最后一個(gè)元素調(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ù)，將第一個(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;
			}
		}
	}

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

下面給出測試代碼：

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

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

網(wǎng)頁題目：簡單堆的創(chuàng)建和操作
地址分享：http://www.dlmjj.cn/article/ieiggg.html