# 算法导论第六章优先队列（二）

1）Insert(S, x):插入x到集合S中；

2）Maximum(S):返回S中具有最大关键字的元素；

3）Extract_Max(S):去掉并返回集合S中具有最大关键字的元素；

4）Increase_Key(S, x, key):将元素x的关键字增加到key。

```1 int PriorityQueue::HeapMaximum()    //return the maximum key from priority queue;
2 {
3     return GetQueueElement(0);        //the first element is max;
4 }```

``` 1 int PriorityQueue::HeapExtractMax()        //delete and return the maximum key from queue;
2 {
3     if (IsEmptyHeap())
4         throw "heap underflow";
5
6     int heap_size = GetHeapSize();
7     int maxNum = GetQueueElement(0);
8     SetQueueElement(0, GetQueueElement(heap_size-1)); //A[1] = A[heap_size]
9     SetHeapSizeMinus1();
10     MaxHeapify(0);    //Max_Heapify()
11     return maxNum;
12 }```

``` 1 void PriorityQueue::HeapIncreaseKey(int srcIndex, int dstKey)    //increasing the srcKey to dstKey
2 {
3     if (dstKey < GetQueueElement(srcIndex))
4         throw "new key is smaller than current key!";
5     SetQueueElement(srcIndex, dstKey); //x = key
6     while(srcIndex > 0 && GetQueueElement(getParent(srcIndex)) < GetQueueElement(srcIndex)) {
7         Swap(srcIndex, getParent(srcIndex));
8         srcIndex = getParent(srcIndex); //get parent
9     }
10 }```

```1 void PriorityQueue::HeapInsert(int key)    //insert key to the priority queue;
2 {
4     int heap_size = GetHeapSize();
5     HeapIncreaseKey(heap_size-1, key);
6 }```

```1 Heap-Delete(A, i)
2     A[i] = A[A.heap-size]
3     A.heap-size = A.heap-size - 1
4     Heapify(A, i)```

``` 1 //PriorityQueue.h
2
3
4 #ifndef _PRIORITY_QUEUE_H_
5 #define _PRIORITY_QUEUE_H_
6
7 /************************************************************************/
8 /*    priority queue
9 /************************************************************************/
10 class PriorityQueue {
11 public:
12     PriorityQueue() { m_heapSize = 0; m_length = 0; }
13     ~PriorityQueue() {}
14
15     //inline
16     int getParent(int index) { return (index-1)/2; }
17     int getLeft(int index) { return 2*index + 1; }
18     int getRight(int index) { return 2*index + 2; }
19
20     //heap operation
21     void BuildMaxHeap();        //build the max heap
22     void MaxHeapify(int index);    //protect the max heap
23     void HeapSort();            //heap sort
24
25     //priority queue operation
26     void HeapInsert(int key);    //insert key to the priority queue;
27     int HeapMaximum();            //return the maximum key from priority queue;
28     int HeapExtractMax();        //delete and return the maximum key from queue;
29     void HeapIncreaseKey(int srcIndex, int dstKey);    //increasing the srcKey to dstKey
30
31     void HeapDelete(int key);    //delete key 习题6.5-8
32
33     //other assist functions
35     void DisplayQueue();
36     void DisplayHeapQueue();
37
38 public:
39
40
41 private:
42     int GetQueueElement(int index) { return m_vecQueue[index]; }
43     void SetQueueElement(int index, int key) { m_vecQueue[index] = key; }
44     void Swap(int i, int j) {
45         int temp = m_vecQueue[i];
46         m_vecQueue[i] = m_vecQueue[j];
47         m_vecQueue[j] = temp;
48     }
49     int GetHeapSize() { return m_heapSize; }
50     int GetArrayLength() { return m_length; }
51     void SetHeapSizeMinus1() { m_heapSize = m_heapSize - 1; }
52     void SetHeapSizePlus1() { m_heapSize = m_heapSize + 1; }
53
54     bool IsEmptyHeap() { return (m_heapSize > 1 ? false : true); }
55
56 private:
57     vector<int>        m_vecQueue;
58     int                m_heapSize;    //堆元素个数
59     int                m_length;    //数组元素个数
60
61 };
62
63
64 #endif//_PRIORITY_QUEUE_H_```
```  1 //PriorityQueue.cpp
2
3
4 #include <iostream>
5 #include <vector>
6 using namespace std;
7
8 #include "PriorityQueue.h"
9
10 //heap operation
11 void PriorityQueue::BuildMaxHeap()        //build the max heap
12 {
13     int heap_size = GetHeapSize();
14     for (int i = (heap_size-1)/2; i >= 0; i --)
15         MaxHeapify(i);
16 }
17
18 void PriorityQueue::MaxHeapify(int index)    //protect the max heap
19 {
20     if (index < 0 || index >= GetHeapSize())
21         return;
22
23     int heap_size = GetHeapSize();
24     bool isHeapify = true;
25
26     int largest = -1;
27     while (isHeapify && index < heap_size) {
28         int left = getLeft(index);
29         int right = getRight(index);
30
31         if (left < heap_size && GetQueueElement(left) > GetQueueElement(index) )
32             largest = left;
33         else
34             largest = index;
35         if (right < heap_size && GetQueueElement(right) > GetQueueElement(largest) )
36             largest = right;
37
38         if (largest != index) {
39             Swap(index, largest);
40             index = largest;
41         }
42         else
43             isHeapify = false;
44     }
45
46 }
47
48 void PriorityQueue::HeapSort()            //heap sort
49 {
50     BuildMaxHeap();
51     int heap_size = GetHeapSize();
52     for (int i = heap_size-1; i >= 1; i --) {
53         Swap(0, i);
54         SetHeapSizeMinus1(); //heap_size--;
55         MaxHeapify(0);
56     }
57 }
58
59 //priority queue operation
60 void PriorityQueue::HeapInsert(int key)    //insert key to the priority queue;
61 {
62 //     SetHeapSizePlus1();
63 //     int heap_size = GetHeapSize();
65     int heap_size = GetHeapSize();
66     HeapIncreaseKey(heap_size-1, key);
67 }
68
69 int PriorityQueue::HeapMaximum()    //return the maximum key from priority queue;
70 {
71     return GetQueueElement(0);        //the first element is max;
72 }
73
74 int PriorityQueue::HeapExtractMax()        //delete and return the maximum key from queue;
75 {
76     if (IsEmptyHeap())
77         throw "heap underflow";
78
79     int heap_size = GetHeapSize();
80     int maxNum = GetQueueElement(0);
81     SetQueueElement(0, GetQueueElement(heap_size-1)); //A[1] = A[heap_size]
82     SetHeapSizeMinus1();
83     MaxHeapify(0);    //Max_Heapify()
84     return maxNum;
85 }
86
87 void PriorityQueue::HeapIncreaseKey(int srcIndex, int dstKey)    //increasing the srcKey to dstKey
88 {
89     if (dstKey < GetQueueElement(srcIndex))
90         throw "new key is smaller than current key!";
91     SetQueueElement(srcIndex, dstKey); //x = key
92     while(srcIndex > 0 && GetQueueElement(getParent(srcIndex)) < GetQueueElement(srcIndex)) {
93         Swap(srcIndex, getParent(srcIndex));
94         srcIndex = getParent(srcIndex); //get parent
95     }
96 }
97
98 void PriorityQueue::HeapDelete(int key)    //delete key 习题6.5-8
99 {
100     int heap_size = GetHeapSize();
101     int index = 0;
102     for (;index < heap_size; index ++) {
103         if (GetQueueElement(index) == key)
104             break;
105     }
106     SetQueueElement(index, GetQueueElement(heap_size-1));
107     SetHeapSizeMinus1();
108     MaxHeapify(index);
109 }
110
111 //other assist functions
112 void PriorityQueue::DisplayQueue()
113 {
114     int nLen = GetArrayLength();
115     cout << "------------------------" << endl;
116     for (int i = 0; i < nLen; i ++)
117         cout << GetQueueElement(i) << " ";
118     cout << endl;
119 }
120
121 void PriorityQueue::DisplayHeapQueue()
122 {
123     int heap_size = GetHeapSize();
124     cout << "------------------------" << endl;
125     for (int i = 0; i < heap_size; i ++)
126         cout << GetQueueElement(i) << " ";
127     cout << endl;
128 }
129
131 {
132     m_vecQueue.push_back(key);
133     m_heapSize ++;
134     m_length ++;
135 }
136
137
138 // int main()
139 // {
140 //     //int key, num;
141 //     PriorityQueue PQ;
142 //
143 // //     cout << "the number:" << endl;
144 // //     cin >> num;
145 //     int arr[] = {10,8,7,16,14,9,3,2,4,1};
146 //     cout << "the key:" << endl;
147 //     for (int i = 0; i < 10; i ++) {
149 //     }
150 //
151 //     PQ.BuildMaxHeap();
152 //     PQ.DisplayQueue();
153 //
154 //     //Max
155 //     cout << "Max:" << PQ.HeapMaximum() << endl;
156 //
157 //     //IncreaseKey
158 //     cout << "IncreaseKey:" << endl;
159 //     PQ.HeapIncreaseKey(0, 18);
160 //     PQ.DisplayHeapQueue();
161 //
162 //     //InsertKey
163 //     cout << "InsertKey:" << endl;
164 //     PQ.HeapInsert(20);
165 //     PQ.DisplayHeapQueue();
166 //
167 //     //Extract_Max
168 //     cout << "Extract_Max:" << PQ.HeapExtractMax() << endl;
169 //     PQ.DisplayHeapQueue();
170 //
171 //     //Extract_Max
172 //     cout << "Extract_Max:" << PQ.HeapExtractMax() << endl;
173 //     PQ.DisplayHeapQueue();
174 //
175 //     return 0;
176 // }```

1）习题6.5-6：在Heap_Increase_Key的第5行操作中，一般需要通过三次赋值来完成。想一想如何利用Insertion_Sort内循环部分的思想，只用一次赋值就完成这一交换操作？

```1 Heap-Increase-Key(A, i, key)
2     if A[i] < key
3         error "new key is smaller than original"
4     while i > 1 and A[Parent(i)] < key
5         A[i] = A[Parent(i)]
6         i = Parent(i)
7     A[i] = key```

2）习题6.5-9：请设计一个能够在O(nlgk)的算法，它能够将k个有序链表合并成一个有序链表，这里n是所有输入链表包含的总的元素个数。（提示：使用最小堆来完成k路归并）。

```  1 //MinHeap_KMerge.cpp
2
3 #include <iostream>
4 #include <vector>
5
6 using namespace std;
7
8 #include "MinHeap.h"
9
10 //merge the k list to a heap;
11 template<class T>
12 MinHeap<T>::MinHeap(size_t kSize)
13 {
14     if (!m_minHeap)
15         delete []m_minHeap;
16     m_minHeap = new T[kSize+1];
17     m_heapSize = 0;
18 }
19
21 template<class T>
22 void MinHeap<T>::MinHeapify(size_t index)
23 {
24     //assert
25     size_t heap_size = GetHeapSize();
26
27     while (true) {
28         size_t left = LEFT(index);
29         size_t right = RIGHT(index);
30
31         size_t smallest;
32         if (left < heap_size && HeapCompare(left, index))
33             smallest = left;
34         else smallest = index;
35         if (right < heap_size && HeapCompare(right, smallest))
36             smallest = right;
37
38         if (smallest != index) {
39             Swap(index, smallest);
40             index = smallest;
41         }
42         else break;
43     }
44 }
45
46 //insert element
47 template<class T>
48 void MinHeap<T>::HeapInsert(const T &element)
49 {
50     m_minHeap[m_heapSize] = element;
51     m_heapSize += 1;
52
53     size_t index = m_heapSize-1;
54
55     while (index > 0 && HeapCompare(index, PARENT(index))) {
56         Swap(index, PARENT(index));
57         index = PARENT(index);
58     }
59 }
60
61 //return and delete the min element
62 template<class T>
63 T MinHeap<T>::HeapExtractMin()
64 {
65     if (IsEmptyHeap())
66         throw "Heap is Empty!";
67     T minElement = HeapMin();
68
69     int heap_size = GetHeapSize();
70     m_minHeap[0] = m_minHeap[heap_size-1];
71     m_heapSize -= 1;
72     MinHeapify(0);
73     return minElement;
74 }
75
76 //return min element;
77 template<class T>
78 T    MinHeap<T>::HeapMin()  const
79 {
80     return m_minHeap[0];
81 }
82
83 int main()
84 {
85     const size_t k = 3;
86     vector<int> vecList[k];
87     vector<int>::iterator iterList[k];
88     vector<int> vecSort;
89     vector<int>::iterator iterS;
90
91     vector<int>::iterator it;
92
93     MinHeap<vector<int>::iterator> minHeap(k);
94     //first list
95     vecList[0].push_back(12);
96     vecList[0].push_back(24);
97     vecList[0].push_back(52);
98     cout << "first list:" << endl;
99     for ( it = vecList[0].begin();it != vecList[0].end(); ++it)
100         cout << *it << "->";
101     cout << "NULL" << endl;
102
103     vecList[1].push_back(9);
104     vecList[1].push_back(32);
105
106     cout << "second list:" << endl;
107     for ( it = vecList[1].begin();it != vecList[1].end(); ++it)
108         cout << *it << "->";
109     cout << "NULL" << endl;
110
111     vecList[2].push_back(34);
112     vecList[2].push_back(42);
113     vecList[2].push_back(78);
114     cout << "third list:" << endl;
115     for ( it = vecList[2].begin();it != vecList[2].end(); ++it)
116         cout << *it << "->";
117     cout << "NULL" << endl;
118
119     iterList[0] = vecList[0].begin();
120     iterList[1] = vecList[1].begin();
121     iterList[2] = vecList[2].begin();
122
123
124     minHeap.HeapInsert(iterList[0]);
125     minHeap.HeapInsert(iterList[1]);
126     minHeap.HeapInsert(iterList[2]);
127
128     while(minHeap.GetHeapSize()) {
129         it = minHeap.HeapExtractMin();
130         vecSort.push_back(*it);
131         ++it;
132         if (it != vecList[0].end() && it != vecList[1].end() && it != vecList[2].end()) { //!!!!Expression vector iterators incompatible
133             minHeap.HeapInsert(it);
134         }
135     }
136
137     cout << "merge:" << endl;
138     for (iterS = vecSort.begin(); iterS != vecSort.end(); ++ iterS)
139         cout << *iterS << "->";
140     cout << "NULL" << endl;
141
142     return 0;
143 }```

0 条评论

• ### 算法导论第六章堆排序（一）

现在来看， 堆的含义大概有两种，一种是数据结构，一种是在一些语言中所定义的“垃圾回收机制”，如Java，在书本上的开篇强调了这两者，并强调若非特殊说明，皆把堆看...

• ### Pascal三角形

作者：bakari   时间：2012.8.4 Pascal三角形又称杨辉三角形，是多项式系数的一种规律展示，最早是由我国数学家杨辉发现，比Pascal早200...

• ### 算法导论2-9章补充几道题

本篇博文意在对前几章中遗漏的，本人觉得有意思的习题当独拿出来练练手。 1、习题2-4，求逆序对，时间复杂度要求Θ(nlgn) 定义：对于一个有n个不同的数组A,...

• ### EX2: 用CImg改写canny算法 EX2

主要在于double newValue = (r * 0.2126 + g * 0.7152 + b * 0.0722);这句话，把每个点转为灰色

• ### BZOJ1485: [HNOI2009]有趣的数列(Catalan数,质因数分解求组合数)

考虑到每个数的最小的质因数\$ \geqslant 2\$，因此极限复杂度为\$O(n log n)\$

• ### Java 并发排序

利用并发来实现排序 <!-- create time: 2016-03-14 09:49:12 --> 1. 说明 本节主要结合排序的实例来演示多线程执行任...

• ### 10:矩阵转置

10:矩阵转置 总时间限制: 1000ms 内存限制: 65536kB描述 输入一个n行m列的矩阵A，输出它的转置AT。 输入第一行包含两个整数n和m，...

• ### BZOJ 1188: [HNOI2007]分裂游戏(multi-nim)

Description 聪聪和睿睿最近迷上了一款叫做分裂的游戏。该游戏的规则试：共有n个瓶子，标号为0,1,2.....n-1,第i个瓶子中 装有p[i]颗巧...

• ### [算法] 数组排序 - 冒泡排序法与直接选择排序法

两种算法都很基础，但是思考的方向还是有着些许差异的。 另外想要更快的去解决排序问题的话，可以下功夫去研究一下库里面的 qsort函数，也非常的实用！