數(shù)據(jù)結(jié)構(gòu)之堆（Heap）的實(shí)現(xiàn)-創(chuàng)新互聯(lián)

堆數(shù)據(jù)結(jié)構(gòu)是一種數(shù)組對(duì)象，它可以被視為一棵完全二叉樹(shù)結(jié)構(gòu)，所以堆也叫做二叉堆。

環(huán)縣網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián),環(huán)縣網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為環(huán)縣上千多家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站建設(shè)公司要多少錢，請(qǐng)找那個(gè)售后服務(wù)好的環(huán)縣做網(wǎng)站的公司定做！

• 二叉堆滿足二個(gè)特性：

 1．父結(jié)點(diǎn)的鍵值總是大于或等于（小于或等于）任何一個(gè)子節(jié)點(diǎn)的鍵值。

 2．每個(gè)結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)都是一個(gè)二叉堆（都是大堆或最小堆）。

 當(dāng)父結(jié)點(diǎn)的鍵值總是大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為大堆。當(dāng)父結(jié)點(diǎn)的鍵值總是小于或等于  任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為最小堆。

 大堆和最小堆是堆數(shù)據(jù)結(jié)構(gòu)的重點(diǎn)。堆排序中使用特別的多。

•  堆的存儲(chǔ)一般是用一個(gè)數(shù)組實(shí)現(xiàn)的，當(dāng)然也可以用鏈?zhǔn)酱鎯?chǔ)，但是特別麻煩。

 如下我們給出一個(gè)數(shù)組：

 int* Arry={10,16,18,12,11,13,15,17,14,19};

 現(xiàn)在我們要根據(jù)這個(gè)數(shù)組來(lái)建一個(gè)不是真正意義上的堆。

 現(xiàn)在的堆并不是真正的堆，它不滿足大堆或者最小堆，所以它是無(wú)意義的，我們要調(diào)整這個(gè)“堆”讓它變成大堆或者最小堆，這一步操作就是調(diào)整堆。

 調(diào)整堆：首先我們要明確調(diào)整堆的目的就是讓整棵樹(shù)中的雙親節(jié)點(diǎn)都大于孩子節(jié)點(diǎn)（這里以大堆為例），所以我們要從葉子結(jié)點(diǎn)開(kāi)始調(diào)整，直到調(diào)整到根節(jié)點(diǎn)結(jié)束，可能調(diào)整好這棵樹(shù)后，子樹(shù)又不符合大堆規(guī)則，轉(zhuǎn)而調(diào)整子樹(shù)，所以我們把這種方式叫下調(diào)（AdjustDown）

#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;

template<class T>
struct Less
{
	bool operator()(const T& l, const T& r)
	{
		return l < r;
	}
};


template<class T>
struct Greater
{
	bool operator()(const T& l, const T& r)
	{
		return l > r;
	}
};

template<class T,template<class> class Continer = Greater>//默認(rèn)為大堆
class Heap
{
public:
	Heap(){};
	Heap(const T* a, size_t size, Continer<T> con);
	Heap(const vector<T>& v);
	void Push(const T& x);
	void Pop();
	T& GetTop();
	bool Empty();
	size_t Size();
	void HeapSort(T* a, size_t size);
protected:
	void _AdjustDown(size_t parent);
	void _AdjustUp(size_t child);
protected:
	vector<T> _a;
	Continer<T> _con;
};

template<class T, template<class> class Continer = Less>
Heap<T,Continer>::Heap(const T* a,size_t size ,Continer<T> con)
{
	_a.reserve(size);

	for (size_t i = 0; i < size; ++i)
	{
		_a.push_back(a[i]);
	}

	//建堆
	for (int i = (_a.size() - 2) / 2; i >= 0; i--)
		//從第一個(gè)非葉子結(jié)點(diǎn)開(kāi)始下調(diào)，葉子結(jié)點(diǎn)可以看作是一個(gè)大堆或小堆
	{

		_AdjustDown(i);
	}
}
template<class T, template<class> class Continer = Less>
void Heap<T,Continer>::_AdjustDown(size_t parent)
{
	size_t child = parent * 2 + 1;
	size_t size = _a.size();
	while (child < size)
	{
		if (child + 1 < size&&_con(_a[child+1],_a[child]))
			//注意這必須是child+1更大或更小，所以把child+1放在前面
			++child;
		if (_con(_a[child],_a[parent]))
		{
			swap(_a[parent], _a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

 在這里是使用的類去封裝堆結(jié)構(gòu)，并且用了仿函數(shù)的方式去復(fù)用大堆和最小堆的代碼。在這里默認(rèn)把堆調(diào)整為大堆。

 以下是堆的調(diào)用：

	int array[] = { 10, 16, 18, 12, 11, 13, 15, 17, 14, 19 };
	size_t size = sizeof(array) / sizeof(int);
	Greater<int> ger;
	Heap<int,Greater> h(array, size, ger);//因?yàn)槟J(rèn)為大頂堆，所以可以省略Greater

 我們的調(diào)整堆的操作是從二叉樹(shù)的第一個(gè)非葉子結(jié)點(diǎn)開(kāi)始調(diào)整。有的讀者會(huì)問(wèn)為什么不從最后一個(gè)結(jié)點(diǎn)調(diào)整呢？因?yàn)樗腥~子結(jié)點(diǎn)我們都可以看作一個(gè)大堆或者最小堆，我們完全不需要去調(diào)整。

 要調(diào)整為一個(gè)最小堆的話只要修改一下調(diào)用即可：

	int array[] = { 10, 16, 18, 12, 11, 13, 15, 17, 14, 19 };
	size_t size = sizeof(array) / sizeof(int);
	Less<int> les;
	Heap<int，Less> h2(array, size, les);

• 向一個(gè)大堆（最小堆中插入一個(gè)數(shù)據(jù)），讓堆仍為大堆（最小堆）。

  Push操作：向堆中插入一個(gè)數(shù)據(jù)，也就是往數(shù)組中插入一個(gè)數(shù)據(jù)，插入數(shù)據(jù)以后一般都不是大堆（最小堆），我們得去調(diào)整。

 上調(diào)（AdjustUP）：把新插入的結(jié)點(diǎn)大于（小于）雙親節(jié)點(diǎn)則往上調(diào)，直到滿足大堆（最小堆）。

template<class T, template<class> class Continer = Less>
void Heap<T, Continer>::Push(const T& x)
{
	_a.push_back(x);
	_AdjustUp(_a.size() - 1);
}
template<class T, template<class> class Continer = Less>
void Heap<T, Continer>::_AdjustUp(size_t child)
{
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		if (_con(_a[child] , _a[parent]))
		{
			swap(_a[child], _a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

•  刪除大堆（最小堆）中的根結(jié)點(diǎn)。

 我們把根節(jié)點(diǎn)刪除以后剩下的結(jié)點(diǎn)就不構(gòu)成一棵樹(shù)結(jié)構(gòu)了，所以我們可以換一種思路讓堆保持原來(lái)的結(jié)構(gòu)。

 方法就是把根節(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)交換，刪除最后一個(gè)結(jié)點(diǎn)，這樣就不會(huì)破環(huán)結(jié)構(gòu)了。

 把結(jié)點(diǎn)刪除后，堆肯定不滿足大堆（最小堆）了，所以我們還要調(diào)整堆。這次我們要從根節(jié)點(diǎn)往葉子結(jié)點(diǎn)調(diào)，這樣很快，因?yàn)樵瓉?lái)的堆根節(jié)點(diǎn)的左右子樹(shù)都已經(jīng)滿足大小堆了。利用下調(diào)來(lái)調(diào)整：

template<class T, template<class> class Continer = Less>
void Heap<T, Continer>::Pop()
{
	assert(!_a.empty());
	size_t size = _a.size();
	swap(_a[0], _a[size - 1]);
	_a.pop_back();
	_AdjustDown(0);
}

 堆和棧是計(jì)算機(jī)內(nèi)存最常用的結(jié)構(gòu)。

 有了大堆和最小堆，我們可以利用他們的特性來(lái)實(shí)現(xiàn)堆排序。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

名稱欄目：數(shù)據(jù)結(jié)構(gòu)之堆（Heap）的實(shí)現(xiàn)-創(chuàng)新互聯(lián)
本文來(lái)源：http://muchs.cn/article20/dscjco.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App設(shè)計(jì)、手機(jī)網(wǎng)站建設(shè)、響應(yīng)式網(wǎng)站、關(guān)鍵詞優(yōu)化、定制開(kāi)發(fā)、云服務(wù)器

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)