您好,登錄后才能下訂單哦!
優(yōu)先級隊列首先是一個隊列,但是它強調(diào)的是“優(yōu)先”,所以優(yōu)先級隊列又分為最大優(yōu)先隊列和最小優(yōu)先隊列。
最大優(yōu)先級隊列:每次從隊列中取出優(yōu)先級最大的數(shù)據(jù),刪除數(shù)據(jù)也是刪除優(yōu)先級最大的數(shù)據(jù)。
最小優(yōu)先級隊列:每次從隊列中取出優(yōu)先級最小的數(shù)據(jù),刪除也是刪除優(yōu)先級最小的數(shù)據(jù)。
所以我們用一個類去實現(xiàn)優(yōu)先級隊列時就需要用到小頂堆和大頂堆的概念。我們并不關(guān)心除了最高優(yōu)先級和最低優(yōu)先級的數(shù)據(jù)在隊列中是怎體存儲的。
為了提高代碼的復用性,最大優(yōu)先級對列和最小優(yōu)先級隊列都使用同一個堆調(diào)整函數(shù),我們可以定義一個比較模板(Compare)也可以說是一個類,不過它是通過重載()實現(xiàn)的。
template<class T> struct Less { bool operator()(const T& left, const T& right) return left < right; }; template<class T> struct Greater { bool operator()(const T& left, const T& right) return left>right; };
通過Less和Grearter模板,我們就可以在優(yōu)先級隊列初始化的時候通過傳Less或者Greater的對象,來調(diào)整是最大優(yōu)先級隊列還是最小優(yōu)先級隊列。
我們的優(yōu)先級隊列所擁有的功能和STL源碼的功能差不多。在這我是用一個順序表來實現(xiàn)隊列。以下是具體的實現(xiàn)
#pragma once #include<iostream> #include<vector> using namespace std; template<class T> struct Less { bool operator()(const T& left, const T& right) { return (left < right); } }; template<class T> struct Greater { bool operator()(const T& left, const T& right) { return (left>right); } }; template<class T,template<class> class Compare=Less> class PQueue { public: PQueue() :_size(0) {} PQueue(const T* a, size_t size) :_size(size) { _data.resize(size); for (size_t i = 0; i < size; i++) { _data[i] = a[i]; } for (int i = (size - 2) / 2; i >= 0; --i) { _AdjustDown(i); } } size_t Size() { return _size; } void Push(const T& d) { _data.push_back(d); ++_size; _AdjustUp(); } void Pop() { swap(_data[0], _data[_size - 1]); _data.pop_back(); _AdjustDown(0); } T& Front() { return _data[0]; } bool Empty() { return _size; } protected: void _AdjustDown(int parent) { Compare<T> con; int child = parent * 2 + 1; while (child < _size) { if (child + 1 < _size&&con(_data[child + 1], _data[child])) ++child; if (con(_data[child], _data[parent])) { swap(_data[child], _data[parent]); parent = child; child = parent * 2 + 1; } else break; } } void _AdjustUp(int child) { Compare<T> con; parent = (child - 1) / 2; while (child > 0) { if (con(_data[child], _data[parent])) { swap(_data[child], _data[parent]); child = parent; parent = (child - 1) / 2; } else break; } } protected: vector<T> _data; size_t _size; };
優(yōu)先級隊列的核心就是調(diào)整大頂堆和小頂堆,如果對于大頂堆和小頂堆有不懂得話可以查看我的博客,互相交流學習。http://helloleex.blog.51cto.com/10728491/1768758
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。