优先队列

优先队列

优先队列是对前面两章的补充。

一种支持：删除最大元素和插入元素的数据结构被叫做优先队列。他与队列和栈相类似，不同点在于，他的运作方式与前面所提到的二叉堆相同，或者说堆排序就是借助了优先队列的思想。

核心点为：将数组排为有序堆，这样便能完成删除最大元素的步骤。

优先队列API： class MaxPQ{ MaxPQ{构建一个空优先队列bool Empty()队列是否为空int size()队列长void trave()遍历队列string delMax()删除最大元素void sort()堆排序}; 

工具函数： eaxh(string &i,string &j)交换函数void swim(int k)上浮函数void sink(int k)下沉函数

具体步骤是：

一、插入元素：（数组0位不使用）

1.尾插入；

2.然后上浮新元素。

二、删除最大元素：

1.记录首元素；

2.交换首尾元素；

3.删除新尾元素；

4.新首元素下沉；

5.输出尾元素。

三、遍历：

数组遍历。

四、排序

堆排序。

代码：

class MaxPQ { public: MaxPQ(){ pq.push_back("null"); }//数组0位不使用. bool Empty(){ return N == 0; } int size(){ return N; } void insert(string item)//尾插入新元素 { pq.push_back(item); swim(++N); } void trave()//遍历 { for (int i = 1; i <= N; ++i) cout << pq[i] << " "; cout << endl; } string delMax()//删除最大元素 { if (Empty())exit(0);//不存在元素，结束进程 string max = pq[1];//取得根结点元素（最大元素） eaxh(pq[1], pq[N--]);//将其和最后一个结点交换 pq.pop_back();//删除尾元素 if(N>0)sink(1);//如果有，下沉首元素 return max; } void sort()//堆排序数组 { int N = size(); while (N > 1) { eaxh(pq[1], pq[N--]); sink(1, N); } } private: vector<string> pq ; int N = 0; void eaxh(string &i, string &j)//交换 { string t = i; i= j; j= t; } void swim(int k)//大元素上浮 { string temp = pq[k]; while (k > 1 && pq[k / 2] <temp) { pq[k] = pq[k / 2]; k = k / 2; } pq[k] = temp; } void sink(int k)//小元素下沉 { string temp = pq[k]; while (2 * k <= N) { int j = 2 * k; if (j < N&&pq[j] < pq[j + 1])j++; if (temp >= pq[j])break; pq[k] = pq[j]; k = j; } pq[k] = temp; } void sink(int k, int N) { string temp = pq[k]; while (2 * k <= N) { int j = 2 * k; if (j < N&&pq[j] < pq[j + 1])j++; if (temp >= pq[j])break; pq[k] = pq[j]; k = j; } pq[k] = temp; } };

索引优先队列：

template<typename Item> class IndexMinPQ { private: int N;//元素数量 vector<int> pq;//二叉堆索引，由1开始 vector<int> qp;//逆序：qp[pq[i]]=pq[qp[i]]=i;元素找索引 vector<Item> items;//元素 bool greater(int i, int j){ return items[pq[i]] > items[pq[j]]; } void eaxh(int i, int j)//交换 { int t = pq[i]; pq[i] = pq[j]; pq[j] = t; qp[pq[i]] = i; qp[pq[i]] = j; } void swim(int k)//小元素上浮 { while (k > 1 && greater(k / 2, k)) { eaxh(k / 2, k); k = k / 2; } } void sink(int k)//大元素下沉 { while (2 * k <= N) { int j = 2 * k; if (j < N&&greater(j, j + 1))j++; if (!greater(k, j))break; eaxh(k, j); k = j; } } public: //创建一个maxN的优先队列，索引取值为0~maxN IndexMinPQ(int maxN) :items(maxN + 1), pq(maxN),qp(maxN + 1, -1), N(0){} bool Empty(){ return N == 0; } bool contains(int k){ return qp[k] != -1; }//是否存在索引为k的元素 void insert(int k, Item item)//索引，元素 { N++; qp[k] = N; pq[N] = k; //pq.push_back(k);//pq[N] = K,第N个数的索引为K items[k] = item;//索引->值 swim(N);//上浮 } int delMin()//删除元素，并返回他的索引 { int indexofMin = pq[1];//存储最小值 eaxh(1, N--);//交换首尾 sink(1);//新头元素下沉 items[pq[N + 1]] = NULL; qp[pq[N + 1]] = -1; //pq.pop_back(); return indexofMin; } void change(int k, Item item)//将索引为K的元素设为item { items[k] = item;//替换值 swim(qp[k]);//索引排序 sink(qp[k]); } void trave()//遍历 { for (int i = 1; i <= N; ++i) cout << pq[i] << ":" << items[i] << " "; cout << endl; } };

测试用例：

int main() { IndexMinPQ<string> p(9); string item; int m; cout << "****************************" << endl; cout << "0.菜单. 1.插入元素." << endl; cout << "2.是否存在索引为k的元素. " << endl; cout << "3.删除最小元素. 4.遍历." << endl; cout << "****************************" << endl; while (cin >> m) { switch (m) { case 0: cout << "****************************" << endl; cout << "0.菜单. 1.插入元素." << endl; cout << "2.是否存在索引为k的元素. " << endl; cout<<"3.删除最小元素. 4.遍历." << endl; cout << "****************************" << endl; break; case 1: cout << "输入插入元素的索引和值:" << endl; cin >> m>>item; p.insert(m,item); break; case 2: cout << "是否存在索引为k的元素：" << endl; cin >> m; cout << p.contains(m) << endl;; break; case 3: cout << "删除最小元素：" << p.delMin() << endl; break; case 4: p.trave(); break; } } system("pause"); }