devbox
天景科技苑
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构与算法——优先队列类的C++实现(二叉堆)

作者：天景科技苑 | 2024-08-07 17:34:43

赞

踩

c++二叉堆实现优先队列

优先队列简单介绍：

操作系统表明上看着是支持多个应用程序同一时候执行。其实是每一个时刻仅仅能有一个进程执行，操作系统会调度不同的进程去执行。

每一个进程都仅仅能执行一个固定的时间，当超过了该时间。操作系统就会暂停当前执行的进程，去调度其他进程来执行。

实现这样的进程调度的一种方法是使用队列。

開始的时候进程被放在队列的末尾，调度程序将重复提取队列中的第一个进程来执行。直到执行完成或时间片用完，若进程没有执行完成则将该进程放入队列的末尾。这样的策略不是特别合适，由于可能一些短的进程须要等待非常长的时间才干轮流到。一般来说，执行时间短的进程须要尽快的结束。所以那些执行时间短的进程须要比較高的优先权，相同，那些比較重要的进程也须要比較高的优先权。


这样的特殊的应用须要一种特殊的队列-----优先队列。能够用二叉堆实现优先队列。

二叉堆简单介绍：

二叉堆与二叉查找树类似，二叉树有两个性质：结构性质和堆序性质。


结构性质：

二叉堆是一棵全然二叉树，除了子节点外的其他节点都有两个儿子节点。


一棵高为h的全然二叉树有2^h到2^(h+1) - 1个节点。

全然二叉树的高为log(N)，N为节点数目。
因为全然二叉树的特点，实现起来非常easy，用简单的数组就能够实现。

对于数组中的任何位置i上的元素，其左儿子在位置2*i上，右儿子在(2*i)+1上，其父节点在i/2上（让根节点在位置1）。


以下是一棵全然二叉树的数组实现图示：



堆序性质：

由于假设想高速找到最小单元。则最小单元应该在根上。在堆中，对于每个节点x,x的值大于等于子节点（叶子节点除外）；没有二叉查找树的要求严格。


二叉堆的数据结构实现：

用一个数组 vector<Comparable> v;来存储全部的元素。


用currentSize来记录当前元素的数目。


  1. vector<Comparable> array;//存储二叉堆的节点 
  2. int currentSize;//当前二叉堆中的节点数目

二叉堆的主要成员函数：

  1. bool isEmpty() const;//推断二叉堆是否为空
  2. const Comparable & findMin() const;//查找最小元素
  3.  
  4. void insert(const Comparable & x);//插入元素x
  5. void deleteMin();//删除最小元素
  6. void deleteMin(Comparable & minItem);//删除最小元素，并以引用的方式返回该最小元素
  7. void makeEmpty();//清空该二叉堆 
  8. void print() const;//打印该堆元素
  9.  
  10. void buildHeap();//将元素移动到合适的位置
  11. void percolateDown(int hole);//下移动

二叉堆的主要成员函数介绍：

1、插入insert()：

比方：当插入14的时候。第一步在堆的下一个可用的位置建立空穴。假设在该空穴插入14后满足堆序性，则插入成功。
但当在该空穴插入14之后不满足堆序性，则将该空穴的父节点移入空穴，之前的父节点的位置变为了空穴。


然后再尝试插入该新的空穴，假设不满足堆序。则反复之前的操作。




  1. /****************************************************************
  2. *   函数名称：insert(const Comparable & x)
  3. *   功能描写叙述: 删除最小元素
  4. *   參数列表: 无
  5. *   返回结果：void 
  6. *****************************************************************/
  7. template<typename Comparable>
  8. void BinaryHeap<Comparable>::insert(const Comparable & x)
  9. {
  10.     if(currentSize == array.size()-1)
  11.         array.resize(2 * array.size());//扩大堆中数组的容量
  12.  
  13.     //获得空穴的位置
  14.     int hole = ++currentSize;
  15.  
  16.     //上滤
  17.     for(; hole > 1 && x < array[hole/2]; hole /= 2)
  18.         array[hole] = array[hole/2];
  19.     //将x插入到合适的位置
  20.     array[hole] = x;
  21. }

2、删除最小元素deleteMin()：

将堆中最小的一个元素删除之后（最下的元素位于堆数组的最前面）。必须将堆中最后一个元素x移动到堆中的某个合适的位置。

.


比方:在下图中删除最小元素的操作。
删除最小元素13。将最后一个元素31移动到13的位置；31比13的两个孩子的值都大，全部将两个孩子值比較小的上移动。所以将14上移动。然后31再和14的两个孩子的值比較。直到31比空穴的两个孩子的值都小，或者是空穴到了叶子节点。则直接将31插入到空穴。




  1. /****************************************************************
  2. *   函数名称：deleteMin()
  3. *   功能描写叙述: 删除最小元素
  4. *   參数列表: 无
  5. *   返回结果：void 
  6. *****************************************************************/
  7. template<typename Comparable>
  8. void BinaryHeap<Comparable>::deleteMin()
  9. {
  10.     if(isEmpty()){
  11.         cout << "BinaryHeap is empty." << endl;
  12.         return;
  13.     }
  14.  
  15.     array[1] = array[currentSize];//将最后一个元素移动到最小元素的位置
  16.     currentSize--;//元素总数减去1
  17.     //将最后一个元素移动到合适的位置
  18.     percolateDown(1); 
  19. }
  20.  
  21. /****************************************************************
  22. *   函数名称：percolateDown(int hole)
  23. *   功能描写叙述: 将array(hole)处的值向下移动 
  24. *   參数列表: hole为堆中元素的位置标号
  25. *   返回结果：void 
  26. *****************************************************************/
  27. template<typename Comparable>
  28. void BinaryHeap<Comparable>::percolateDown(int hole)
  29. {
  30.     int child;
  31.     //先保存array[hole]的值
  32.     Comparable temp = array[hole];
  33.  
  34.     for(; hole * 2 <= currentSize; hole = child){
  35.         child = hole * 2;
  36.  
  37.         //child != currentSize,表明此时空穴有右儿子
  38.         //array[child] > array[child+1] 表明此时空穴有右儿子小于左儿子
  39.         if(child != currentSize && array[child] > array[child+1])
  40.             child++;//此时child表示为空穴的右儿子
  41.  
  42.         //空穴的右儿子小于array[hole]
  43.         if(array[child] < temp)
  44.             array[hole] = array[child];
  45.         else
  46.             break;
  47.     }
  48.  
  49.     array[hole] = temp;
  50. }

以下是main函数，主要是对散列表类进行測试。


  1. //測试主函数
  2. int main()
  3. {
  4.     srand(unsigned(time(0)));
  5.     BinaryHeap<int> binaryHeap;
  6.  
  7.     vector<int> v;
  8.  
  9.     for(int i = 0; i < 10; ++i)
  10.         v.push_back(rand() % 10);
  11.     cout << "v: ";
  12.     for(int i = 0; i < 10; ++i)
  13.         cout << v[i] << " ";
  14.     cout << endl;
  15.     
  16.  
  17.     for(int i = 0; i < 10; ++i)
  18.         binaryHeap.insert(v[i]);
  19.  
  20.     binaryHeap.print();
  21.  
  22.  
  23.     for(int i = 0; i < 12; i++){
  24.         int minVal = 0;
  25.         binaryHeap.deleteMin(minVal);
  26.         cout << "删除最小元素："  << minVal << endl;
  27.         binaryHeap.print();
  28.     }
  29.  
  30.     cout << "*****************************************" << endl;
  31.     cout << "測试第二个构造函数: " << endl;
  32.     BinaryHeap<int> binaryHeap2(v);
  33.     binaryHeap2.print();
  34.  
  35.     for(int i = 0; i < 12; i++){
  36.         int minVal = 0;
  37.         binaryHeap2.deleteMin(minVal);
  38.         cout << "删除最小元素："  << minVal << endl;
  39.         binaryHeap2.print();
  40.     }
  41.  
  42.  
  43.     return 0;
  44. }

以下是二叉堆类的源码：

  1. /*************************************************************************
  2. 	> File Name: binaryHeap.cpp
  3. 	> Author: 
  4. 	> Mail: 
  5. 	> Created Time: 2016年04月14日 星期四 11时37分43秒
  6.  ************************************************************************/
  7.  
  8. #include <iostream>
  9. #include <vector>
  10. #include <time.h>
  11. #include <stdlib.h>
  12. using namespace std;
  13.  
  14.  
  15.  
  16. /******************************************
  17. *   类的名称：二叉堆
  18. ******************************************/
  19.  
  20. template<typename Comparable>
  21. class BinaryHeap
  22. {
  23.     public:
  24.         explicit BinaryHeap(int capacity = 100):array(capacity), currentSize(0){}
  25.         explicit BinaryHeap(const vector<Comparable> & items);
  26.  
  27.         bool isEmpty() const;//推断二叉堆是否为空
  28.         const Comparable & findMin() const;//查找最小元素
  29.         
  30.         void insert(const Comparable & x);//插入元素x
  31.         void deleteMin();//删除最小元素
  32.         void deleteMin(Comparable & minItem);//删除最小元素。并以引用的方式返回该最小元素
  33.         void makeEmpty();//清空该二叉堆 
  34.         void print() const;//打印该堆元素
  35.  
  36.     private:
  37.         vector<Comparable> array;//存储二叉堆的节点 
  38.         int currentSize;//当前二叉堆中的节点数目
  39.     private:
  40.         void buildHeap();//将元素移动到合适的位置
  41.         void percolateDown(int hole);//下移动
  42. };
  43.  
  44. /****************************************************************
  45. *   函数名称：print() const
  46. *   功能描写叙述: 打印该堆元素 
  47. *   參数列表: 无 
  48. *   返回结果：无
  49. *****************************************************************/
  50. template<typename Comparable>
  51. void BinaryHeap<Comparable>::print() const
  52. {
  53.     cout << "二叉堆的元素: " << endl;
  54.     for(int i = 1; i <= currentSize; ++i)
  55.         cout << array[i] << " ";
  56.     cout << endl;
  57. }
  58.  
  59. /****************************************************************
  60. *   函数名称：BinaryHeap(const vector<Comparable> & items)
  61. *   功能描写叙述: 构造函数
  62. *   參数列表: items 是构造二叉堆须要的数据
  63. *   返回结果：无
  64. *****************************************************************/
  65. template<typename Comparable>
  66. BinaryHeap<Comparable>::BinaryHeap(const vector<Comparable> & items):array(items.size()+10), currentSize(items.size())
  67. {
  68.     for(unsigned i = 0; i < items.size(); ++i)
  69.         array[i+1] = items[i];
  70.  
  71.     buildHeap();
  72. }
  73. /****************************************************************
  74. *   函数名称：buildHeap()
  75. *   功能描写叙述: 将元素移动到合适的位置，满足堆序
  76. *   參数列表: 无
  77. *   返回结果：void
  78. *****************************************************************/
  79. template<typename Comparable>
  80. void BinaryHeap<Comparable>::buildHeap()
  81. {
  82.     for(int i = currentSize / 2; i > 0; --i)
  83.         percolateDown(i);
  84. }
  85.  
  86. /****************************************************************
  87. *   函数名称：findMin()
  88. *   功能描写叙述: 查找最小元素
  89. *   參数列表: 无
  90. *   返回结果：返回最小元素的引用
  91. *****************************************************************/
  92. template<typename Comparable>
  93. const Comparable & BinaryHeap<Comparable>::findMin() const
  94. {
  95.    return array[1]; 
  96. }
  97.  
  98. /****************************************************************
  99. *   函数名称：insert(const Comparable & x)
  100. *   功能描写叙述: 删除最小元素
  101. *   參数列表: 无
  102. *   返回结果：void 
  103. *****************************************************************/
  104. template<typename Comparable>
  105. void BinaryHeap<Comparable>::insert(const Comparable & x)
  106. {
  107.     if(currentSize == array.size()-1)
  108.         array.resize(2 * array.size());//扩大堆中数组的容量
  109.  
  110.     //获得空穴的位置
  111.     int hole = ++currentSize;
  112.  
  113.     //上滤
  114.     for(; hole > 1 && x < array[hole/2]; hole /= 2)
  115.         array[hole] = array[hole/2];
  116.     //将x插入到合适的位置
  117.     array[hole] = x;
  118. }
  119.  
  120. /****************************************************************
  121. *   函数名称：deleteMin()
  122. *   功能描写叙述: 删除最小元素
  123. *   參数列表: 无
  124. *   返回结果：void 
  125. *****************************************************************/
  126. template<typename Comparable>
  127. void BinaryHeap<Comparable>::deleteMin()
  128. {
  129.     if(isEmpty()){
  130.         cout << "BinaryHeap is empty." << endl;
  131.         return;
  132.     }
  133.  
  134.     array[1] = array[currentSize];//将最后一个元素移动到最小元素的位置
  135.     currentSize--;//元素总数减去1
  136.     //将最后一个元素移动到合适的位置
  137.     percolateDown(1); 
  138. }
  139.  
  140. /****************************************************************
  141. *   函数名称：percolateDown(int hole)
  142. *   功能描写叙述: 将array(hole)处的值向下移动 
  143. *   參数列表: hole为堆中元素的位置标号
  144. *   返回结果：void 
  145. *****************************************************************/
  146. template<typename Comparable>
  147. void BinaryHeap<Comparable>::percolateDown(int hole)
  148. {
  149.     int child;
  150.     //先保存array[hole]的值
  151.     Comparable temp = array[hole];
  152.  
  153.     for(; hole * 2 <= currentSize; hole = child){
  154.         child = hole * 2;
  155.  
  156.         //child != currentSize,表明此时空穴有右儿子
  157.         //array[child] > array[child+1] 表明此时空穴有右儿子小于左儿子
  158.         if(child != currentSize && array[child] > array[child+1])
  159.             child++;//此时child表示为空穴的右儿子
  160.  
  161.         //空穴的右儿子小于array[hole]
  162.         if(array[child] < temp)
  163.             array[hole] = array[child];
  164.         else
  165.             break;
  166.     }
  167.  
  168.     array[hole] = temp;
  169. }
  170. /****************************************************************
  171. *   函数名称：deleteMin(Comparable & minItem)
  172. *   功能描写叙述: 删除最小元素
  173. *   參数列表: minItem 将最小元素赋值给引用minItem
  174. *   返回结果：void 
  175. *****************************************************************/
  176. template<typename Comparable>
  177. void BinaryHeap<Comparable>::deleteMin(Comparable & minItem)
  178. {
  179.     if(isEmpty()){
  180.         cout << "binaryHeap is empty." << endl;
  181.         return;
  182.     }
  183.  
  184.     minItem = array[1];
  185.  
  186.     array[1] = array[currentSize--];
  187.     percolateDown(1);
  188. }
  189.  
  190. /****************************************************************
  191. *   函数名称：makeEmpty()
  192. *   功能描写叙述: 情况二叉堆
  193. *   參数列表: 无
  194. *   返回结果：void 
  195. *****************************************************************/
  196. template<typename Comparable>
  197. void BinaryHeap<Comparable>::makeEmpty()
  198. {
  199.     currentSize = 0;
  200. }
  201.  
  202. /****************************************************************
  203. *   函数名称：isEmpty()
  204. *   功能描写叙述: 推断二叉堆是否为空
  205. *   參数列表: 无
  206. *   返回结果：假设为空，则返回true。否则返回false
  207. *****************************************************************/
  208. template<typename Comparable>
  209. bool BinaryHeap<Comparable>::isEmpty() const
  210. {
  211.     return currentSize == 0;
  212. }
  213.  
  214.  
  215.  
  216.  
  217. //測试主函数
  218. int main()
  219. {
  220.     srand(unsigned(time(0)));
  221.     BinaryHeap<int> binaryHeap;
  222.  
  223.     vector<int> v;
  224.  
  225.     for(int i = 0; i < 10; ++i)
  226.         v.push_back(rand() % 10);
  227.     cout << "v: ";
  228.     for(int i = 0; i < 10; ++i)
  229.         cout << v[i] << " ";
  230.     cout << endl;
  231.     
  232.  
  233.     for(int i = 0; i < 10; ++i)
  234.         binaryHeap.insert(v[i]);
  235.  
  236.     binaryHeap.print();
  237.  
  238.  
  239.     for(int i = 0; i < 12; i++){
  240.         int minVal = 0;
  241.         binaryHeap.deleteMin(minVal);
  242.         cout << "删除最小元素："  << minVal << endl;
  243.         binaryHeap.print();
  244.     }
  245.  
  246.     cout << "*****************************************" << endl;
  247.     cout << "測试第二个构造函数: " << endl;
  248.     BinaryHeap<int> binaryHeap2(v);
  249.     binaryHeap2.print();
  250.  
  251.     for(int i = 0; i < 12; i++){
  252.         int minVal = 0;
  253.         binaryHeap2.deleteMin(minVal);
  254.         cout << "删除最小元素："  << minVal << endl;
  255.         binaryHeap2.print();
  256.     }
  257.  
  258.  
  259.     return 0;
  260. }

以下是程序的执行结果：

v: 5 3 8 4 3 6 1 5 4 5 
二叉堆的元素: 
1 3 3 4 4 8 6 5 5 5 
删除最小元素：1
二叉堆的元素: 
3 4 3 5 4 8 6 5 5 
删除最小元素：3
二叉堆的元素: 
3 4 5 5 4 8 6 5 
删除最小元素：3
二叉堆的元素: 
4 4 5 5 5 8 6 
删除最小元素：4
二叉堆的元素: 
4 5 5 6 5 8 
删除最小元素：4
二叉堆的元素: 
5 5 5 6 8 
删除最小元素：5
二叉堆的元素: 
5 6 5 8 
删除最小元素：5
二叉堆的元素: 
5 6 8 
删除最小元素：5
二叉堆的元素: 
6 8 
删除最小元素：6
二叉堆的元素: 
8 
删除最小元素：8
二叉堆的元素: 

binaryHeap is empty.
删除最小元素：0
二叉堆的元素: 

binaryHeap is empty.
删除最小元素：0
二叉堆的元素: 

*****************************************
測试第二个构造函数: 
二叉堆的元素: 
1 3 5 4 3 6 8 5 4 5 
删除最小元素：1
二叉堆的元素: 
3 3 5 4 5 6 8 5 4 
删除最小元素：3
二叉堆的元素: 
3 4 5 4 5 6 8 5 
删除最小元素：3
二叉堆的元素: 
4 4 5 5 5 6 8 
删除最小元素：4
二叉堆的元素: 
4 5 5 8 5 6 
删除最小元素：4
二叉堆的元素: 
5 5 5 8 6 
删除最小元素：5
二叉堆的元素: 
5 6 5 8 
删除最小元素：5
二叉堆的元素: 
5 6 8 
删除最小元素：5
二叉堆的元素: 
6 8 
删除最小元素：6
二叉堆的元素: 
8 
删除最小元素：8
二叉堆的元素: 

binaryHeap is empty.
删除最小元素：0
二叉堆的元素: 

binaryHeap is empty.
删除最小元素：0
二叉堆的元素:

转载于:https://www.cnblogs.com/gccbuaa/p/7261740.html

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号