现在的位置: 首页 > 综合 > 正文

算法导论第六章 优先级队列

2013年10月26日 ⁄ 综合 ⁄ 共 3015字 ⁄ 字号 小 中 大 ⁄ 评论关闭

原文链接：http://blog.csdn.net/coder_xia/article/details/6627902  

如堆一样，队列也有2种，最大优先级队列和最小优先级队列。最大优先级队列的一个应用是在一台分时计算机上进行作业调度（终于搞到点有用的），对于最大优先级队列，支持以下操作：

     1）INSERT(S,x)把元素x插入队列S

     2）MAXIMUM（S）：返回S中最大元素

    3）EXTRACT-MAX(S)：去掉并返回Ｓ中最大元素

　4）INCRESE-KEY（S,x,key）在x位置插入值key。

     优先级队列，用堆实现，这就是看到的必杀运用了。

    我们以82页图为例

示范程序如下：

[cpp] view
plaincopy

  1. //============================================================================  
  2. // Name        : prioity.cpp  
  3. // Author      : xia  
  4. // Version     : 1.0  
  5. // Copyright   : NUAA  
  6. // Description : 优先级队列的模拟实现  
  7. //============================================================================  
  8. #include <iostream>  
  9. #include <climits> //INT_MIN  
  10. #include <vector> //vector  
  11. #include <algorithm>//for_each  
  12. using namespace std;  
  13.   
  14. int Parent(int i)  
  15. {//返回i节点的父节点  
  16.     if (i>0)  
  17.         return i/2;  
  18.     return -1;  
  19. }  
  20. void MaxHeapify(vector<int> &v ,int i ,int heap_size)  
  21. {//让A[i]在最大堆中下降，使以i为根的子树成为大顶堆  
  22.     int left=2*i; //l<-LEFT(i)  
  23.     int right = 2*i+1; //r<-RIGHT(i)  
  24.     int largest=i;  
  25.    
  26.     if ( (left <= heap_size)  && (v[left] > v[i]) )  
  27.         largest = left ;  
  28.     else  
  29.         largest = i;  
  30.     if ( (right <=heap_size ) && (v[right] > v[largest]) )  
  31.         largest = right;//从父母和自己中找出最大的  
  32.    
  33.     if (largest != i)  
  34.     {  
  35.         swap(v[i],v[largest]);//交换使i和子堆满足堆性质，不过largest为根的可能违反，递归调整  
  36.         MaxHeapify(v,largest, heap_size);  
  37.     }   
  38. }  
  39. void BuildHeap(vector<int> &v)  
  40. {//建堆  
  41.     for (int i=v.size()/2 ; i > 0 ; i--)  
  42.         MaxHeapify(v,i,v.size()-1);   
  43. }  
  44. int HeapMaximum(vector<int> A)  
  45. { //返回堆上的最大元素  
  46.     return A[1];  
  47. }  
  48. int HeapExtractMax(vector<int> &A )  
  49. { //去掉并返回A中最大的值  
  50.     int heap_size = A.size()-1;  
  51.     if ( heap_size <1 )  
  52.     {  
  53.         cout << " heap underflow" << endl;  
  54.         exit(EXIT_FAILURE);  
  55.     }  
  56.     int max = A[1];  
  57.     A[1] = A[heap_size];  
  58.     heap_size--;   
  59.     A.pop_back();  
  60.     MaxHeapify(A,1 ,heap_size);  
  61.     return max;  
  62. }  
  63. void HeapIncreaseKey(vector<int> &A , int i, int key)  
  64. { //在i处插入值为key的数，并调整堆  
  65.     if (key<A[i])  
  66.     {  
  67.         cout << " new key is smaller than current key " << endl;  
  68.         exit(EXIT_FAILURE);  
  69.     }  
  70.     A[i] = key;  
  71.     while ( (i>1) && (A[Parent(i)] < A[i]))  
  72.     {  
  73.         swap(A[i],A[Parent(i)]);  
  74.         i = Parent(i) ;  
  75.     }  
  76. }  
  77. void MaxHeapInsert(vector<int> &A , int key)  
  78. {  
  79.     A.push_back(INT_MIN); //伪代码heapsize+1，且插入负无穷  
  80.     HeapIncreaseKey(A,A.size()-1,key);//第二个参数实际为堆大小  
  81. }  
  82.   
  83. template <class T>   
  84. class Print   
  85. {  
  86.  public:   
  87.      void operator () (T& t)   
  88.      {  
  89.          cout << t << " ";   
  90.      }  
  91. };  
  92.   
  93. const int heap_size = 10; //这里假设元素为10个  
  94.   
  95. int main()  
  96. {  
  97.     int temp[heap_size]={16,14,10,8,7,9,3,2,4,1};  
  98.     vector<int> v(temp+0,temp+heap_size);  
  99.   
  100.     Print<int> print;  
  101.     v.insert(v.begin(),0);//插入个0，切合伪代码  
  102.   
  103.     BuildHeap(v); //虽然我们的数组顺序已经符合堆，不过常理还是要先建堆  
  104.   
  105.     cout << "初始堆V " << endl;  
  106.     for_each(v.begin()+1,v.end(),print);//遍历输出  
  107.     cout << endl<< endl;  
  108.   
  109.     cout <<"插入个试试 " << endl;  
  110.     HeapIncreaseKey(v,9,15);//p82图  
  111.     for_each(v.begin()+1,v.end(),print);  
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞