首页 > 代码库 > 优先队列的应用:求序列第 k 个最大的元素

优先队列的应用:求序列第 k 个最大的元素

优先队列【堆】的应用:

    选择问题:输入时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 次删除最大值的操作。从该堆最后提取的元素就是我们的答案。该算法构造堆的最坏情况是 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.0001
using 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;
}

 

 

优先队列的应用:求序列第 k 个最大的元素