編程開發(fā)中如何實現(xiàn)堆

這篇文章主要介紹了編程開發(fā)中如何實現(xiàn)堆，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

一、堆的概念  

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

  堆結(jié)構(gòu)的二叉樹存儲是：

  最大堆：每個父節(jié)點的都大于孩子節(jié)點。

  最小堆：每個父節(jié)點的都小于孩子節(jié)點。

     堆棧中的物體具有一個特性： 最后一個放入堆棧中的物體總是被最先拿出來， 這個特性通常稱為后進先出(LIFO)隊列。 堆棧中定義了一些操作。 兩個最重要的是PUSH和POP。 PUSH操作在堆棧的頂部加入一 個元素。POP操作相反， 在堆棧頂部移去一個元素， 并將堆棧的大小減一。

    在此，用vector容器來實現(xiàn)存儲，vector容器是一個模板類，可以存放任何類型的對象（但必須是同一類對象）。vector對象可以在運行時高效地添加元素，并且vector中元素是連續(xù)存儲的。當(dāng)容量不夠時，它能夠自己去擴容。故我們在push數(shù)據(jù)時就不用考慮一些其他容量不足等等因素。

二、堆的實現(xiàn)

  通過二叉樹來實現(xiàn)堆的結(jié)構(gòu)。

先實現(xiàn)一個compare，如果實現(xiàn)大小堆用對象調(diào)其對應(yīng)類運算符“（）”重載

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

先定義一個堆：

  用模板的模板參數(shù)：

   如：當(dāng) 測試用例為：

      int arr[] = { 12, 10, 43, 23, 22, 45, 67,9 };

 Heap<int,Big>  N(arr, sizeof(arr)/sizeof(arr[0])); 

 當(dāng)你給定compare為Big時它會按照大堆去排序

 Heap<int,Less>  N(arr, sizeof(arr)/sizeof(arr[0])); 

 當(dāng)你給定compare為Big時它會按照小堆去排序

template<class T , template<class>  class compare >  //模板的模板參數(shù)
class Heap
{

public:
	Heap()
	{}
	Heap(T* a, size_t size)
	{
		_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)
		{
			_AdjustDown(i);
		}
	    Disp(_a, size);
	}
	//Pop時，先將第一個與最后一個交換，（這樣不至于打亂其他子堆的順序），然后
	//刪除最后一個，再讓它下調(diào)重新調(diào)整順序
	void Pop()       
	{
		size_t _size = _a.size();
		assert(_size > 0);
		swap(_a[0], _a[_size-1]);
		_a.pop_back();
		_size = _a.size();
		_AdjustDown(0);
		Disp(_a, _size);
	}
	//push一個數(shù)據(jù)后，讓其上調(diào)，以調(diào)整順序
	void Push(const T& x)
	{
		_a.push_back(x);
		size_t _size = _a.size();
		_AdjustUp(_size-1);
		Disp(_a, _size);
	}
	T& Top()
	{
		assert(!_a.empty());
	    return _a[0];
	}
	bool empty()
	{
		return _a.size() == 0;
	}
	void Disp(vector<T> a, size_t k)//打印
	{
		for (size_t j = 0; j < k; j++)
		{
			cout << a[j] << " ";
		}
		cout << endl;
	}

在建堆時，首先來定義一個下調(diào)函數(shù)_AdjustDown（）；用來調(diào)整已實現(xiàn)大小堆順序。

 實現(xiàn)思想：

     1、找最后一個非葉子結(jié)點

2、如果當(dāng)前結(jié)點的孩子結(jié)點左孩子大于右孩子，就讓child指向最大孩子結(jié)點（在此必須滿足存在右孩子）

3、如果當(dāng)前結(jié)點小于孩子結(jié)點，就交換，下調(diào)，將孩子給父親，孩子結(jié)點下移

4、不滿足  就break；

	void _AdjustDown(size_t parent)    //     下調(diào)
	{
		size_t child = parent * 2 + 1;
		while (child < _a.size())
		{
			compare<T> _com;  
			if ( child + 1 < _a.size()&&_com(_a[child + 1], _a[child]) )
			{
				++child;
			}
			if (_com(_a[child],_a[parent]))
			{
				swap(_a[child], _a[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}

再寫一個上調(diào)函數(shù)_AdjustUp（）當(dāng)Push一個數(shù)時，讓它上調(diào)，以調(diào)整整個堆的順序。

實現(xiàn)思想：

     1、上調(diào)，傳當(dāng)前結(jié)點，令當(dāng)前節(jié)點為孩子結(jié)點，上一結(jié)點為父結(jié)點，

2、在這里不用考慮左右結(jié)點誰大誰小

3、如果孩子結(jié)點大于父親結(jié)點，交換，上移

4、不滿足  就break；

注意：在此不用考慮左右子數(shù)誰大誰小，上調(diào)是如果孩子結(jié)點比父結(jié)點大，那它肯定比兄弟結(jié)點大。

void _AdjustUp(size_t child)   //上調(diào)
	{
		compare<T> _com;
		size_t parent = (child - 1) / 2;
		while (child > 0)
		{
			if (_com(_a[child], _a[parent]))
			{
				swap(_a[child], _a[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}

三、優(yōu)先隊列

template<class T, template<class>  class compare = Big>//利用模板的模板參數(shù)
class PriorityQueue  //優(yōu)先隊列
{
protected:
	Heap<T, compare> _hP;
public:
	void _push(const T& x)
	{
		_hP.Push(x);
	}
	void Pop()
	{
		_hP.Pop();
	}
	T& Top()
	{
		return _hP.Top();
	}
};

測試用例：
PriorityQueue<int,Big> s;
	s._push(3);
	s._push(12);
	s._push(5);
	s._push(78);
	s._push(43);
	s._push(10);
	s._push(32);	

結(jié)果會以大堆形式實現(xiàn)為：

如果將測試用例改為：

PriorityQueue<int,Less> s;
	s._push(3);
	s._push(12);
	s._push(5);
	s._push(78);
	s._push(43);
	s._push(10);
	s._push(32);

  結(jié)果會以小堆實現(xiàn) 為：

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“編程開發(fā)中如何實現(xiàn)堆”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識等著你來學(xué)習(xí)!