優先隊列的應用 C++實現

優先隊列可以用堆來實現, 堆底層可以用數組表示，
通過索引關系，可以表示成一顆二叉完全樹

C++的STL提供了相應的容器適配器
包含在queue頭文件中

下面通過一道題來看如何使用它

給定一個字符串，請將字符串里的字符按照出現的頻率降序排列。

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();
}

還有好幾個類似的題，都可以用這種方式解決

比如 :

• leetcode-692
• leetcode-378
• leetcode-373
• leetcode-347

下面是堆的實現, 還是建議掌握的

#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];elsebreak;}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;
};

轉載于:https://www.cnblogs.com/kwebi/p/9811990.html

總結

以上是生活随笔為你收集整理的优先队列的应用 C++实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。