堆（heap）——C++实现

优先队列从名字我们就可以猜到，其与队列之间存在一定的练习，优先队列与队列一样主要是入队和出队两个操作。但是优先队列与队列的不同之处在于，优先队列会将优先级高的先出队，这在很多情况下非常有用。例如，Windows的MFC是基于消息的响应的机制，内部管理着一个消息队列，计算机不断从消息队列中抓取消息进行响应，那么系统的消息和应用软件的消息优先级必然不同，我们需要优先响应系统的消息，那么优先队列就显示它强大的功能。

堆的实现我们可以通过一个表，或者一个二叉树都可以实现。如果通过一个表实现，入队很方便，但是出队，必须遍历一遍表找到优先级最高的那个，需要花费O(N)的时间，效率太低。对于二叉树来说入队和出队都是O(logN)的时间复杂度，但是二叉树的频繁删除会导致树向右边倾斜，当然我们可以通过平衡树来解决这个问题，但是对于优先队列来说最简单的方式是通过二叉堆实现。

二叉堆的实质是一个数组，只是我们用完全二叉树的形式将其表述出来，完全二叉树与不完全二叉树的区别如下图：

数组的第一位我们空出来是为了去满足二叉堆的性质：设某元素所处于数组中的位置为i，那么他的左儿子的位置使2*i，他的父元素的位置在i/2；

因为对于堆来说插入比删除要频繁，因此将优先级最高的放在第一个，因为删除比插入麻烦的多。

以下是例程，用vector实现：

1 /************************************************************************/
 2 /* 堆的实现                                                                     */
 3 /************************************************************************/
 4 #include<vector>
 5 namespace stl
 6 {
 7     template<typename T>
 8     class Heap
 9     {
10     public:
11         /************************************************************************/
12         /*构造函数*/
13         Heap(int capacity = 100)
14             :size(0)   //堆中包含数据个数
15         {
16             H.resize(capacity);
17         }
18 
19         ~Heap()
20         {
21         }
22 
23         bool isEmpty()
24         {
25             return size == 0;
26         }
27 
28         void makeEmpty()
29         {
30             size = 0;
31             for (auto it = H.begin(); it != H.end(); it++)
32             {
33                 H.erase(it);
34             }
35         }
36         /************************************************************************/
37         /*插入函数 */
38         void insert(const T & x)
39         {
40             //如果vector中已经存满了，重新分为大小，数组首地址不存数据
41             if (size == H.size() -1)
42             {
43                 H.resize(2*size);
44             }
45             //size大小加一
46             for (int current = ++size; current > 1 && H[current/2] > x; current /= 2)
47             {
48                  H[current] = H[current/2];
49             }
50             //找到空位将x插入
51             H[current] = x;
52         }
53 
54         /*删除函数*/
55         T deleteMin()
56         {
57             if (isEmpty())
58             {
59                 throw();
60             }
61             int current, child;
62             T returnVal = H[1];
63             T lastElement = H[size--];   //将最后一个值保存下来，删除一个元素所以自减运算
64             for (current = 1; 2 * current > size; current = child)
65             {
66                 child = 2 * current;
67                 //防止访问越界
68                 if (child != size && H[2 * current] > H[2 * current + 1])  
69                 {
70                     ++child;
71                 }
72                 //比较子较小的儿子与最后一个值的大小，如果儿子较小用儿子上滤，否则跳出循环
73                 if (H[child] < lastElement)
74                 {
75                     H[current] = H[child];
76                 }
77                 else
78                 {
79                     break;
80                 }
81             }
82             H[current] = lastElement;
83             return returnVal;
84         }
85 
86     private:
87         std::vector<T> H;
88         int size;
89     };
90 }

原文链接: https://www.cnblogs.com/liuteng/p/6048322.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍