堆的實(shí)現(xiàn)（堆的建立及push、pop元素）

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

創(chuàng)新互聯(lián)建站主要從事網(wǎng)站設(shè)計(jì)制作、成都網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)清河,10年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來(lái)電咨詢建站服務(wù):028-86922220

堆結(jié)構(gòu)的二叉樹(shù)存儲(chǔ)：

大堆：每個(gè)父節(jié)點(diǎn)的都大于孩子節(jié)點(diǎn)；小堆：每個(gè)父節(jié)點(diǎn)的都小于孩子節(jié)點(diǎn)。

建堆：由于堆被視為完全二叉樹(shù)，故在h-1層找到第一個(gè)（從后往前找）非葉子結(jié)點(diǎn)，進(jìn)行堆的下調(diào)

建大堆時(shí)，從下往上依次判斷并調(diào)整堆，使該結(jié)點(diǎn)的左右子樹(shù)都滿足大堆

建小堆時(shí)，從下往上依次判斷并調(diào)整堆，使該結(jié)點(diǎn)的左右子樹(shù)都滿足小堆

可見(jiàn)大堆的建立與小堆的建立方式類似，下面以大堆進(jìn)行討論。

利用vactor模板存儲(chǔ)堆中元素

template<class T>
class Heap
{
public:
	Heap();
	Heap(const T* a, size_t size);
	void Push(const T& x);
	void Pop();
	T& GetTop();//訪問(wèn)堆頂元素
	bool Empty();//判空
	size_t Size();//堆元素個(gè)數(shù)
	void PrintHeap();
protected:
	void _AdjustDown(size_t Parent);//下調(diào)--建大堆(每個(gè)父結(jié)點(diǎn)都大于孩子結(jié)點(diǎn))
	void _AdjustUp(size_t Child);//上調(diào)--建小堆(每個(gè)父結(jié)點(diǎn)都小于孩子結(jié)點(diǎn))
private:
	vector<T> _a;
};

實(shí)現(xiàn)堆的建立

template<class T>
Heap<T>::Heap()
:_a(NULL)
{}
template<class T>
Heap<T>::Heap(const T* a, size_t size)
{
	assert(a);
	_a.reserve(size);//初始化_a(vector模板的使用)
	for (size_t i = 0; i < size; ++i)
	{
		_a.push_back(a[i]);
	}
	////堆的第一個(gè)非葉子結(jié)點(diǎn)的數(shù)組下標(biāo)時(shí)((size-1)-1)/2（最后一個(gè)結(jié)點(diǎn)是size-1）
	for (int i = (int)(size - 2) / 2; i >= 0; --i)//不能定義為size_t（無(wú)符號(hào)）
	{
		_AdjustDown(i);
	}
	//建小堆，類似建大堆的方式，從下向上進(jìn)行調(diào)整堆，使該結(jié)點(diǎn)處的左右子樹(shù)都滿足小堆
	//在進(jìn)行調(diào)小堆時(shí)，也通過(guò)下調(diào)實(shí)現(xiàn)
}
//下調(diào)--建大堆/小堆
template<class T>
void Heap<T>::_AdjustDown(size_t Parent)
{
	size_t Child = Parent * 2 + 1;
	while (Child < _a.size())
	{//先進(jìn)行左右結(jié)點(diǎn)的比較,使Child為較大的數(shù)的下標(biāo)，然后與父親結(jié)點(diǎn)進(jìn)行比較，使較大的數(shù)據(jù)為父親結(jié)點(diǎn)
		if (Child + 1 < _a.size() && _a[Child] < _a[Child + 1])//存在右結(jié)點(diǎn)再進(jìn)行比較
		{
			++Child;
		}
		if (_a[Child] > _a[Parent])//如果子結(jié)點(diǎn)大于父親結(jié)點(diǎn)就交換，否則就要跳出循環(huán)
		{
			swap(_a[Child], _a[Parent]);
			Parent = Child;
			Child = Parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//在建立小堆時(shí)，只需要將比較條件進(jìn)行改變就可以實(shí)現(xiàn)

在已經(jīng)是大堆或小堆的堆中加入元素使堆仍為大堆，可通過(guò)該元素與它的父結(jié)點(diǎn)進(jìn)行比較

ps：由于插入的元素在數(shù)組末尾，故需要通過(guò)上調(diào)進(jìn)行比較實(shí)現(xiàn)堆的大堆或小堆

template<class T>
void Heap<T>::_AdjustUp(size_t Child)//上調(diào)
{
	size_t Parent = (Child - 1) / 2;//結(jié)點(diǎn)為Child的父親結(jié)點(diǎn)為（Child-1）/2
	while (Child > 0)//當(dāng)Child等于0時(shí)以到堆頂，終止循環(huán)
	{
		if (_a[Parent] < _a[Child])//直接進(jìn)行父親結(jié)點(diǎn)和子結(jié)點(diǎn)的比較
		{
			swap(_a[Child], _a[Parent]);
			Child = Parent;
			Parent = (Child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
template<class T>
void Heap<T>::Push(const T& x)//元素x入堆
{
	//_a.resize(_a.size() + 1);
	//_a[_a.size()-1] = x;
	_a.push_back(x);
	_AdjustUp(_a.size() - 1);
}

堆中pop元素，刪除堆頂元素，使堆仍為大堆。

在已經(jīng)是大堆或小堆的堆中刪除堆頂元素，直接刪除堆頂元素，造成無(wú)法進(jìn)行大堆或小堆的實(shí)現(xiàn)，可通過(guò)將第一個(gè)元素與最后一個(gè)元素進(jìn)行交換，然后刪除最后一個(gè)元素，最后通過(guò)下調(diào)實(shí)現(xiàn)大堆或小堆

template<class T>
void Heap<T>::Pop()//出堆
{
	size_t size = _a.size();
	assert(size > 0);//斷言堆非空
	swap(_a[0], _a[size - 1]);
	_a.pop_back();
	_AdjustDown(0);//從堆頂開(kāi)始進(jìn)行下調(diào)
}

實(shí)現(xiàn)堆的堆頂，判空及堆元素個(gè)數(shù)

template<class T>
T& Heap<T>::GetTop()//訪問(wèn)堆頂元素
{
	return _a[0];
}
template<class T>
bool Heap<T>::Empty()//判空
{
	return _a.size() == 0;
}
template<class T>
size_t Heap<T>::Size()//堆元素個(gè)數(shù)
{
	return _a.size();
}
template<class T>
void Heap<T>::PrintHeap()
{
	for (size_t i = 0; i < _a.size(); ++i)
	{
		cout << _a[i] << " ";
	}
	cout << endl;
}

測(cè)試用例

#include"Heap.hpp"
void Test4()
{
	int arr[] = { 10, 16, 18, 12, 11, 13, 15, 17, 14, 19};
	Heap<int> h(arr, sizeof(arr) / sizeof(arr[0]));
	h.PrintHeap();
	cout << "empty: " << h.Empty() << endl;
	cout << "size: " << h.Size() << endl;
	cout << "gettop: " << h.GetTop() << endl;
	h.Push(20);
	h.PrintHeap();
	h.Pop();
	h.PrintHeap();
}

如果對(duì)于上述說(shuō)明還是不是很清楚，可自己親手畫圖分析，存在不足之處請(qǐng)多多指教。

【vector】包含著一系列連續(xù)存儲(chǔ)的元素, 其行為和數(shù)組類似。訪問(wèn)Vector中的任意元素或從末尾添加元素都可以在常量級(jí)時(shí)間復(fù)雜度內(nèi)完成，而查找特定值的元素所處的位置或是在Vector中插入元素則是線性時(shí)間復(fù)雜度。

分享題目：堆的實(shí)現(xiàn)（堆的建立及push、pop元素）
URL地址：http://muchs.cn/article38/ispisp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、定制網(wǎng)站、軟件開(kāi)發(fā)、網(wǎng)站維護(hù)、面包屑導(dǎo)航、搜索引擎優(yōu)化

廣告

聲明：本網(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)