優先佇列的應用 C++實現
優先佇列的應用 C++實現
優先佇列可以用堆來實現, 堆底層可以用陣列表示,
通過索引關係,可以表示成一顆二叉完全樹
C++的STL提供了相應的容器介面卡
包含在queue
標頭檔案中
下面通過一道題來看如何使用它
ofollow,noindex" target="_blank">給定一個字串,請將字串裡的字元按照出現的頻率降序排列。
string frequencySort(string s) { }
首先,統計字元出現的頻率,通過map容器可以很簡單的統計出來
map<char, int> mp; for (auto e : s) { ++mp[e]; }
然後我們需要構建一個優先佇列,而且要指定優先佇列的排序方式
因此我們定義了一個自己的結構體, 並定義了<
操作符(降序定義小於號,升序大於號),
struct Node { Node(const pair<char, int> &val) : p(val) {} pair<char, int> p; }; bool operator<(const Node &a, const Node &b) { return a.p.second < b.p.second; }
然後把鍵值對放入優先佇列中
priority_queue<Node, vector<Node>, less<Node>> pq; for (auto e : mp) { pq.push(make_pair(e.first, e.second)); }
要用的時候,依次取出來就是了,每次取出的都是裡面最大(或最小)的
string res; while (!pq.empty()) { for (int i = 0; i < pq.top().p.second; ++i) res.push_back(pq.top().p.first); pq.pop(); }
還有好幾個類似的題,都可以用這種方式解決
比如 :
下面是堆的實現, 還是建議掌握的
#include <vector> using namespace std; template <class T> class Heap { public: Heap(size_t maxElems) { h = new HeapStruct; h->Elems = new T[maxElems + 1]; h->Capacity = maxElems; h->size = 0; } ~Heap() { destroy(); } void insert(T x) { size_t i; if (isFull()) { return; } for (i = ++h->size; i / 2 > 0 && h->Elems[i / 2] > x; i /= 2) { h->Elems[i] = h->Elems[i / 2]; } h->Elems[i] = x; } T deleteMin() { size_t i, child; T minElems, lastElems; if (isEmpty()) return h->Elems[0]; minElems = h->Elems[1]; lastElems = h->Elems[h->size--]; for (i = 1; i * 2 <= h->size; i = child) { child = i * 2; if (child != h->size && h->Elems[child + 1] < h->Elems[child]) ++child; if (lastElems > h->Elems[child]) h->Elems[i] = h->Elems[child]; else break; } h->Elems[i] = lastElems; return minElems; } bool isFull() { return h->size == h->Capacity; } bool isEmpty() { return h->size == 0; } T findMin() { return h->Elems[1]; } private: void destroy() { delete h->Elems; delete h; } void makeEmpty() {} struct HeapStruct { size_t Capacity; size_t size; T *Elems; }; HeapStruct* h; };