优先队列【堆】的应用：
选择问题：输入时N 个元素以及一个整数k ，这N 个元素的集可以是全序的。该选择问题是要找出第 k 个最大的元素。。。
有多种解决方案：
1A算法：把这些元素读入数组，并对其进行排序，返回适当的元素。假设使用的是简单排序算法，时间复杂度是O(N^2)。
1B算法：将k 个元素读入一个数组，并对其进行排序。这些元素的最小者在第k 个位置上，一个一个的处理其余的元素。当一个元素开始被处理时，它先与第k 个元素进行比较，如果该元素大，则将第k 个元素出去，该元素放在其余k - 1 个排好序的元素中的正确位置。当算法结束时，第k 个位置上的元素就是该问题的解答。该算法的运行时间为O(N*k)，如果k = N / 2（上取整），则运行时间为O(N^2)【此时的 k 为中位数】。
2A算法：将N个元素读入一个数组，然后对该数组建立一个大顶堆。最后，执行k 次删除最大值的操作。从该堆最后提取的元素就是我们的答案。如果使用 BuildHeap 算法构造堆的最坏情况是 O(N) 【具体分析参见文章（）】，而每次删除操作用时O(logN)，由于k 次删除，因此，得到总的运行时间是O(N + k * logN), 若k = N / 2（上取整），那么运行时间为O(NlogN) 【堆排序】。
2A-改进：在任意时刻都维持k 个最大元素结合S， 在前 k 个元素读入以后，当再读入一个新的元素时，该元素将与第 k 个最大的元素进行比较，记这第k 大的元素为 Sk，注意 Sk 是 S 中的最小元素。如果新元素更大，则用新元素替代这个 Sk 。此时 S 中将有一个新的最小元。这里，我们使用一个堆来实现 S 。前 k 个元素通过堆的建立过程，建立一个堆，总时间为 O(k)，处理其余的每个元素的时间为 O(1) （检测元素是否进入堆），在加上时间O(log k)（在必要时删除 Sk, 并插入新元素）。因此，总的时间是O(k + (N - k) * log K) = O(N log k)。若 k 为中位数，则时间为 O(NlogN)。【代码如下：】
//利用堆寻找某一序列中第k大的元素（从小到大）即第k大的元素#include<iostream>#define MINHEAPSIZE 1#define MINVALUE 0.0001using namespace std;
typedef int ElemType;typedef struct HeapStruct{ ElemType *elem; int Size; int Capasity;}Heap, *PriorityQueue;
PriorityQueue InitializeHeap(int MaxSize) //堆的初始化{ if(MaxSize < MINHEAPSIZE) throw exception("The priority queue is too small!"); PriorityQueue H; H = new HeapStruct(); H->Size = 0; H->Capasity = MaxSize; H->elem = new ElemType[MaxSize + 1]; H->elem[0] = MINVALUE; return H;}
void InsertHeap(PriorityQueue H, ElemType key) //上滤过程{ if(H->Size == H->Capasity) throw exception("The priority queue is full!"); int i; for(i = ++H->Size; H->elem[i / 2] > key; i /= 2) { H->elem[i] = H->elem[i / 2]; } H->elem[i] = key;}
int DeleteMin(PriorityQueue H) //下滤过程{ int i, child; ElemType MinElem, LastElem; if(H->Size == 0) { cout << "The priority queue is empty!" << endl; return H->elem[0]; } MinElem = H->elem[1]; //此时根节点可以看做是一个空穴 LastElem = H->elem[H->Size--]; for(i = 1; i * 2 <= H->Size; i = child) //比较空穴i的两个孩子，child指向最小的孩子 { child = i * 2; if(child != H->Size && H->elem[child] > H->elem[child + 1]) child++; if(LastElem > H->elem[child]) //最小的孩子与最后一个元素比较，若最后一个元素小于该节点的最小孩子，
//则将最后的元素填入空穴中 H->elem[i] = H->elem[child]; else break; } H->elem[i] = LastElem; //填补空穴 return MinElem;}
int SearchKElem(ElemType arr[], int length, int k){ if(length < k || length <MINHEAPSIZE) throw exception("Invalidate input!"); PriorityQueue H; H = InitializeHeap(k); for(int i = 0; i < k; i++) InsertHeap(H, arr[i]); for(int j = k; j < length; j++) { if(arr[j] > H->elem[1]) { DeleteMin(H); InsertHeap(H, arr[j]); } } ElemType kMax = H->elem[1]; return kMax;}
int main(){ int arr[10] = {5, 2, 8, 1, 3, 9, 7, 4, 6,10}; int k; cout << "请输入k值：" ; cin >> k; int result = SearchKElem(arr, 10, k); cout <<"倒数第k大的元素为：" << result << endl;
system("pause"); return 0;}