堆數(shù)據(jù)結(jié)構(gòu)是一種數(shù)組對象,它可以被視為一棵完全二叉樹結(jié)構(gòu)。
創(chuàng)新互聯(lián)從2013年開始,先為雁江等服務(wù)建站,雁江等地企業(yè),進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為雁江企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。堆結(jié)構(gòu)的二叉樹存儲是
這是一個(gè)普通的堆,我們想把它變成大堆,就必須了解大堆的特點(diǎn)。然后我們對它進(jìn)行調(diào)整,保證每個(gè)父節(jié)點(diǎn)的都大于孩子節(jié)點(diǎn)。
我們先調(diào)整這個(gè)二叉樹的一部分,從它的最后一個(gè)節(jié)點(diǎn)開始調(diào)整,圖中紅色箭頭開始調(diào)整,如果父節(jié)點(diǎn)小于孩子節(jié)點(diǎn),就交換,否則結(jié)束。在看下一個(gè)節(jié)點(diǎn),一直這樣循環(huán),直到全部調(diào)整完。
代碼如下:
void _AdjustDown(size_t parent, size_t size) { size_t child = 2 * parent + 1; while (child < size) { //child + 1 < size保證是最后一個(gè)節(jié)點(diǎn) if (child + 1 < size&&_arr[child] < _arr[child + 1]) { child++;//孩子節(jié)點(diǎn)大的一個(gè)節(jié)點(diǎn) } //交換 if (_arr[child]>_arr[parent]) { swap(_arr[child],_arr[parent]); parent = child; child = 2 * parent + 1; } else { break; } } }
如果想把它調(diào)整成最小堆,必須符合每個(gè)父節(jié)點(diǎn)的都小于孩子節(jié)點(diǎn),代碼原理和大堆相似。
代碼如下:
void _AdjustUp(int child) { int parent = (child - 1) / 2; int size = _arr.size(); while (child > 0) { if (_arr[child] > _arr[parent]) { swap(_arr[child], _arr[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } }
下面我給出完整代碼,構(gòu)造函數(shù)用的是調(diào)整成大堆。為了讓代碼更簡潔,實(shí)現(xiàn)過程借用了庫函數(shù)中的vector。
代碼如下:
Heap.h中
#include<assert.h> #include <vector> template <class T> class Heap { public: Heap() :_arr(NULL) {} //構(gòu)造函數(shù) Heap(const T*arr, size_t size) { _arr.reserve(size); for (size_t i = 0; i < size; i++) { _arr.push_back(arr[i]); } for (int j = (_arr.size() - 2) / 2; j >= 0; j--) { _AdjustDown(j, size); } } //拷貝構(gòu)造 Heap(const vector<T>& h) { _arr.reserve(_arr.size()); for (size_t i = 0; i < _arr.size(); i++) { _arr.push_back(h[i]); } } //先儲存在順序表中,在進(jìn)行下調(diào) void push(const T& x) { _arr.push_back(x); _AdjustUp(_arr.size()-1); } //刪除 void pop() { size_t size = _arr.size(); assert(size > 0); swap(_arr[0], _arr[size - 1]);//先把根結(jié)點(diǎn)和要?jiǎng)h除的結(jié)點(diǎn)交換 _arr.pop_back();//然后刪除 size = _arr.size(); _AdjustDown(0, size);//最后上調(diào) } //堆是否為空 bool Empty() { size_t size = _arr.size(); assert(size >= 0); return size == 0; } //堆的大小 size_t Size() { size_t size = _arr.size(); assert(size >= 0); return size; } //訪問根結(jié)點(diǎn) T& Top() { size_t size = _arr.size(); assert(size > 0); return _arr[0]; } void Print() { for (int i = 0; i < Size(); i++) { cout << _arr[i] << " "; } cout << endl; } protected: //下調(diào) void _AdjustDown(size_t parent, size_t size) { size_t child = 2 * parent + 1; while (child < size) { //child + 1 < size保證是最后一個(gè)節(jié)點(diǎn) if (child + 1 < size&&_arr[child] < _arr[child + 1]) { child++;//孩子節(jié)點(diǎn)大的一個(gè)節(jié)點(diǎn) } //交換 if (_arr[child]>_arr[parent]) { swap(_arr[child],_arr[parent]); parent = child; child = 2 * parent + 1; } else { break; } } } //上調(diào) void _AdjustUp(int child) { int parent = (child - 1) / 2; int size = _arr.size(); while (child > 0) { if (_arr[child] > _arr[parent]) { swap(_arr[child], _arr[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } protected: vector<T> _arr; };
test.cpp中
#include<iostream> using namespace std; #include"Heap.h" void Test() { int a[] = { 10, 16, 18, 12, 11, 13, 15, 17, 14, 19 }; Heap<int> h(a, sizeof(a) / sizeof(a[0])); h.Print(); h.push(20); h.Print(); h.pop(); h.Print(); Heap<int> h2(h); h2.Print(); } int main() { Test(); system("pause"); return 0; }
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn,海內(nèi)外云服務(wù)器15元起步,三天無理由+7*72小時(shí)售后在線,公司持有idc許可證,提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案,具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢,專為企業(yè)上云打造定制,能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
文章標(biāo)題:用模板實(shí)現(xiàn)堆-創(chuàng)新互聯(lián)
文章來源:http://muchs.cn/article48/cdiehp.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供全網(wǎng)營銷推廣、做網(wǎng)站、外貿(mào)網(wǎng)站建設(shè)、企業(yè)網(wǎng)站制作、品牌網(wǎng)站設(shè)計(jì)、網(wǎng)站營銷
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容