您好,登錄后才能下訂單哦!
堆數(shù)據(jù)結(jié)構(gòu)是一種數(shù)組對象,它可以被視為一棵完全二叉樹結(jié)構(gòu)。
堆結(jié)構(gòu)的二叉樹存儲:
大堆:每個父節(jié)點的都大于孩子節(jié)點;小堆:每個父節(jié)點的都小于孩子節(jié)點。
建堆:由于堆被視為完全二叉樹,故在h-1層找到第一個(從后往前找)非葉子結(jié)點,進(jìn)行堆的下調(diào)
建大堆時,從下往上依次判斷并調(diào)整堆,使該結(jié)點的左右子樹都滿足大堆
建小堆時,從下往上依次判斷并調(diào)整堆,使該結(jié)點的左右子樹都滿足小堆
可見大堆的建立與小堆的建立方式類似,下面以大堆進(jìn)行討論。
利用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();//堆元素個數(shù) void PrintHeap(); protected: void _AdjustDown(size_t Parent);//下調(diào)--建大堆(每個父結(jié)點都大于孩子結(jié)點) void _AdjustUp(size_t Child);//上調(diào)--建小堆(每個父結(jié)點都小于孩子結(jié)點) private: vector<T> _a; };
實現(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]); } ////堆的第一個非葉子結(jié)點的數(shù)組下標(biāo)時((size-1)-1)/2(最后一個結(jié)點是size-1) for (int i = (int)(size - 2) / 2; i >= 0; --i)//不能定義為size_t(無符號) { _AdjustDown(i); } //建小堆,類似建大堆的方式,從下向上進(jìn)行調(diào)整堆,使該結(jié)點處的左右子樹都滿足小堆 //在進(jìn)行調(diào)小堆時,也通過下調(diào)實現(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é)點的比較,使Child為較大的數(shù)的下標(biāo),然后與父親結(jié)點進(jìn)行比較,使較大的數(shù)據(jù)為父親結(jié)點 if (Child + 1 < _a.size() && _a[Child] < _a[Child + 1])//存在右結(jié)點再進(jìn)行比較 { ++Child; } if (_a[Child] > _a[Parent])//如果子結(jié)點大于父親結(jié)點就交換,否則就要跳出循環(huán) { swap(_a[Child], _a[Parent]); Parent = Child; Child = Parent * 2 + 1; } else { break; } } } //在建立小堆時,只需要將比較條件進(jìn)行改變就可以實現(xiàn)
在已經(jīng)是大堆或小堆的堆中加入元素使堆仍為大堆,可通過該元素與它的父結(jié)點進(jìn)行比較
ps:由于插入的元素在數(shù)組末尾,故需要通過上調(diào)進(jìn)行比較實現(xiàn)堆的大堆或小堆
template<class T> void Heap<T>::_AdjustUp(size_t Child)//上調(diào) { size_t Parent = (Child - 1) / 2;//結(jié)點為Child的父親結(jié)點為(Child-1)/2 while (Child > 0)//當(dāng)Child等于0時以到堆頂,終止循環(huán) { if (_a[Parent] < _a[Child])//直接進(jìn)行父親結(jié)點和子結(jié)點的比較 { 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)是大堆或小堆的堆中刪除堆頂元素,直接刪除堆頂元素,造成無法進(jìn)行大堆或小堆的實現(xiàn),可通過將第一個元素與最后一個元素進(jìn)行交換,然后刪除最后一個元素,最后通過下調(diào)實現(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);//從堆頂開始進(jìn)行下調(diào) }
實現(xiàn)堆的堆頂,判空及堆元素個數(shù)
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()//堆元素個數(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; }
測試用例
#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】包含著一系列連續(xù)存儲的元素, 其行為和數(shù)組類似。訪問Vector中的任意元素或從末尾添加元素都可以在常量級時間復(fù)雜度內(nèi)完成,而查找特定值的元素所處的位置或是在Vector中插入元素則是線性時間復(fù)雜度。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。