堆數據結構是一種數組對象，它可以被視為一棵完全二叉樹結構。

創新互聯建站專注于企業營銷型網站建設、網站重做改版、建德網站定制設計、自適應品牌網站建設、H5網站設計、商城系統網站開發、集團公司官網建設、外貿營銷網站建設、高端網站制作、響應式網頁設計等建站業務，價格優惠性價比高，為建德等各大城市提供網站開發制作服務。

堆結構的二叉樹存儲：

大堆：每個父節點的都大于孩子節點；小堆：每個父節點的都小于孩子節點。

建堆：由于堆被視為完全二叉樹，故在h-1層找到第一個（從后往前找）非葉子結點，進行堆的下調

建大堆時，從下往上依次判斷并調整堆，使該結點的左右子樹都滿足大堆

建小堆時，從下往上依次判斷并調整堆，使該結點的左右子樹都滿足小堆

可見大堆的建立與小堆的建立方式類似，下面以大堆進行討論。

利用vactor模板存儲堆中元素

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

實現堆的建立

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]);
	}
	////堆的第一個非葉子結點的數組下標時((size-1)-1)/2（最后一個結點是size-1）
	for (int i = (int)(size - 2) / 2; i >= 0; --i)//不能定義為size_t（無符號）
	{
		_AdjustDown(i);
	}
	//建小堆，類似建大堆的方式，從下向上進行調整堆，使該結點處的左右子樹都滿足小堆
	//在進行調小堆時，也通過下調實現
}
//下調--建大堆/小堆
template<class T>
void Heap<T>::_AdjustDown(size_t Parent)
{
	size_t Child = Parent * 2 + 1;
	while (Child < _a.size())
	{//先進行左右結點的比較,使Child為較大的數的下標，然后與父親結點進行比較，使較大的數據為父親結點
		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;
		}
	}
}
//在建立小堆時，只需要將比較條件進行改變就可以實現

在已經是大堆或小堆的堆中加入元素使堆仍為大堆，可通過該元素與它的父結點進行比較

ps：由于插入的元素在數組末尾，故需要通過上調進行比較實現堆的大堆或小堆

template<class T>
void Heap<T>::_AdjustUp(size_t Child)//上調
{
	size_t Parent = (Child - 1) / 2;//結點為Child的父親結點為（Child-1）/2
	while (Child > 0)//當Child等于0時以到堆頂，終止循環
	{
		if (_a[Parent] < _a[Child])//直接進行父親結點和子結點的比較
		{
			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元素，刪除堆頂元素，使堆仍為大堆。

在已經是大堆或小堆的堆中刪除堆頂元素，直接刪除堆頂元素，造成無法進行大堆或小堆的實現，可通過將第一個元素與最后一個元素進行交換，然后刪除最后一個元素，最后通過下調實現大堆或小堆

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);//從堆頂開始進行下調
}

實現堆的堆頂，判空及堆元素個數

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

測試用例

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

如果對于上述說明還是不是很清楚，可自己親手畫圖分析，存在不足之處請多多指教。

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

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

分享名稱：堆的實現（堆的建立及push、pop元素）-創新互聯
當前網址：http://www.js-pz168.com/article2/docjic.html

成都網站建設公司_創新互聯，為您提供電子商務、手機網站建設、響應式網站、品牌網站設計、企業網站制作、Google

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯