Heapsort 和 priority queue

一、二叉堆含义及属性:

堆（heap)亦被称为：优先队列（priority queue），是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。在队列中，调度程序反复提取队列中第一个作业并运行，因而实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。同垃圾收集存储的堆含义不同。

表示堆的数组A有两个属性:

A.length : 代表A数组的元素个数;

A.heapsize : 代表A数组中 属于堆元素个数。有时候(排序时)，数组A的部分元素不属于堆。刚开始建堆的是偶，A.heapsize = A.length，排序时，每次从堆顶取出最大值，A.heapsize递减，直至排序完成.

下图是一个建好后的二叉堆:

从图中可知，已知某节点的索引值i，可以轻松获取其对应父节点，左,右子节点的索引值。有:

1Parent(i)
2    return i/2; 或者 return i >> 1;
3Left(i)
4    return i*2; 或者 return i << 1;
5Right(i)
6    return i*2+1; 或者 return (i << 1) + 1;

二叉堆分两种: 最大堆，最小堆，均遵循堆属性。最大堆，每个节点i满足:

A[Parent(i)] ≥ A[i]

最小堆与之相反，每个节点i满足:

A[Parent(i)] ≤ A[i]

    堆排序算法，我们用的是最大堆，因为最小堆用于实现优先队列(priority queues).二叉堆的其他属性同二叉树属性类似，如节点高度，树高度等。如n个元素的完全二叉树，树高为lgn, 故n个元素的二叉堆高度为lgn.

二、保持堆属性:

保持堆属性，或者称"大堆化", 关键函数是Max-Heapify, 构造二叉堆，以及二叉堆排序均需要调用该函数，如从无序数组构造二叉堆，就需要使所有节点"大堆化".

Max-Heapify 运行时间为O(h)，h为对应节点高度.

伪代码分析：

到line 8，已经确定A[i], A[i].left, A[i].right 三者中最大值。如果最大值是根节点A[i],满足大堆属性，不需修改；反之, 则需把根节点同子节点中最大节点交换，同时因为最大子节点替换成比其值小的父节点，需要确保以该子节点为父节点的子树是否满足大堆属性，所以需要用largest 作为新i递归调用Max-Heapify.下图是一个 Max-Heapify 处理实例:

三、建堆

我们自底向上的用Max-Heapify 将无序数组A[1...n]转换成一个最大堆。因为二叉堆是完美二叉树，可知子序列A[(n/2+1)...n]中的元素均是叶子节点，每个都可以看成是一个元素的堆, 默认就满足堆属性。

BUILD-MAX-HEAP 对树中剩余所有非叶子节点调用 Max-Heapify,以维持堆属性。 

BUILD-MAX-HEAP运行时间为O(n)。

下图是无序数组建堆示例图：

四、堆排序

接下来就是堆排序的实现了，通过BUILD-MAX-HEAP 建立大堆后，最大的元素在root，即A[0].可以先提取出该最大值,HeapSort首先把A[0]同A[n-1]交换，然后通过减小A.heap_size 来将最后一个元素a[n-1]移出堆。这样我们就获取了一个最大值。同时可以知道除了新的根节点，其他节点原来均保持堆属性，为恢复堆属性，我们调用Max-Heapify(A,0),以让以A[0]为根节点的堆保持堆属性.接下来重复该过程，每次移除最大节点(root节点)，可以完成排序操作。

下图是构建大堆后，堆排序的示例图：

HeapSort 运行时间为O(nlgn).有堆排序的平均时间复杂度为O(nlgn)，空间复杂度为O(1)。

五、优先级队列(priority queue)

    作为排序算法，实际中快排比堆排序更加有效。但二叉堆有别的用处，如高效的优先级队列。同二叉堆一样，优先级队列也分两种: 最大优先级队列，最小优先级队列。

    优先级队列作为管理一组数据集合S的数据结构，支持以下操作:

1. Insert(S,x) 将新元素插入集合S中。

2. Maximum(S) 返回集合S中最大元素。

3. Extract-Max(S) 从集合S中移除最大元素，并返回。

4. Increase-Key(S,x,key) 将集合S中x位置元素值替换成key，这里假定新key值不能小于x原来位置值，主要用来Insert时调用，新增空节点，并赋予新key值。

    最大优先级队列用于在分时系统中进行作业调度。队列对将要执行的作业和作业优先级做记录。当一个作业完成或者中断了，用Extract-Max 从所有待运行作业中，取出最高优先级作业。任何时候加入新作业，可以使用Insert 加入队列中。

    相应的，最小优先级队列支持Insert，Minimum，Extract-Min，Decrease-Key等操作。主要用于事件驱动模拟器中。

1、Heap-Extract-Max 伪代码如下，类似于Heapsort for循环部分:

Heap-Extract-Max 运行时间为O(lgn).

2、Heap-increase-key 伪代码如下，因为把key值赋予(如新创建的空)i节点，可能会破坏堆属性，所有line 4的while循环用于恢复堆属性。 

Heap-increase-key 运行时间为O(lgn).

3、Max-Heap-insert伪代码如下:

Max-Heap-insert 运行时间为O(lgn). 可知，n个节点的二叉堆，优先级队列所有操作时间均为O(lng).

六、二叉堆其他应用:

1、C++中的STL 已经实现了优先队列 priority_queue， 网上也很多文章介绍如何使用。

2、哈夫曼编码。

3、一些任务调度算法。

4、一个修改版的堆排：每次不是将堆底的元素拿到上面去，而是直接比较堆顶（最大）元素的两个儿子，即选出次大的元素。由于这两个儿子之间的大小关系是很不确定的，两者都很大，说不好哪个更大哪个更小，所以这次比较的两个结果就是概率均等的了。具体参考这里。

code：因为使用了C++类，破坏了堆排序的原地性，但是原理不变，同时代码中也有提示~

1/*************************************************************************
2* heap sort algorithm and priority queue .
3* Date :    28/07/2014
4* author : alex xiao
5* tips : 
6* 1. Two different way to build a binary heap(priority queue), max_heap_insert and 
7*     build_max_heap. no need call together.
8* 2. heap_extract_max can't call with heap_sort at the same time, as m_heap_size decrease.
9* 3. heap sort no need use C++ class, destory in place property. you can replace m_array with
10*     array, replace m_length with array_length.
11*************************************************************************/
12#include <iostream>
13#include <time.h>
14#include <stdlib.h>
15using namespace std;
16
17template<typename T>
18class binary_heap
19{
20public:
21	binary_heap() : m_array(NULL), m_length(0), m_max_size(0) m_heap_size(0)
22	{}
23	binary_heap(int length);
24	~binary_heap(void)
25	{
26		delete [] m_array;
27	}
28	void build_max_heap(T * array, int array_length);
29	void heap_sort(T * array, int array_length);
30	void maxHeapify(T * array, int n);
31	void heap_dump(void);
32
33	int heap_maximum(void);
34	int heap_extract_max(void);
35	int heap_increase_key(int i, T key);
36	int max_heap_insert(T key);
37
38private:
39	T* m_array;
40	int m_length;
41	int m_max_size;
42	int m_heap_size;
43};
44
45
46int main(void)
47{
48	int i = 0;
49	int array[10] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
50	int array_length = sizeof(array)/sizeof(array[0]);
51
52	binary_heap<int> bh(array_length);
53	for(i = 0; i < array_length; i++)
54	{
55		bh.max_heap_insert(array[i]);
56	}
57
58	cout << "Before sort : " << endl;
59	bh.heap_dump();
60
61	bh.heap_sort(array, array_length);
62
63	return 0;
64}
65
66template<typename T>
67binary_heap<T>::binary_heap(int length)
68{
69	m_array = new T[length];
70	m_length = 0;
71	m_heap_size = 0;
72	m_max_size = length;
73}
74
75/******************************************************************************
76* runs in O(lgn) time, sorts an array in place.
77* tips: heap sort no need use C++ class, destory in place property. you can replace m_array with
78*     array, replace m_length with array_length.
79******************************************************************************/
80template<typename T>
81void binary_heap<T>::heap_sort(T * array, int array_length)
82{
83	int i = 0;
84	int heap_size = m_length;
85	build_max_heap(m_array, m_length);
86
87	cout << "After build_max_heap : " << endl;
88	heap_dump();
89
90	for(i = m_length-1; i>=0; i--)//数组中下标从0  -  n-1
91	{
92		int temp = m_array[0];
93		m_array[0] = m_array[i];
94		m_array[i] = temp;
95		m_heap_size--;
96		maxHeapify(m_array, 1);//在堆中，堆顶元素下标从1开始
97	}
98
99	cout << "After Sort : " << endl;
100	heap_dump();
101}
102
103/******************************************************************************
104* runs in linear time, produces a max-heap from an unordered input array
105******************************************************************************/
106template<typename T>
107void binary_heap<T>::build_max_heap(T * array, int array_length)
108{
109	int i = 0;
110	m_heap_size = array_length;
111
112	for(i = array_length/2 ; i>=1 ; i--)//注意i的取值,堆的高度从1  -  n/2
113	{
114		maxHeapify(array, i);
115	}
116}
117
118/******************************************************************************
119* runs in O(lgn) time, the key to maintaining the max-heap property.
120******************************************************************************/
121template<typename T>
122void binary_heap<T>::maxHeapify(T * array, int temp)
123{
124	int largest = 0;//以temp为顶点的子树的堆顶
125	int l = temp << 1;//求以temp为顶点的子树左儿子
126	int r = (temp << 1) + 1;//求以temp为顶点的子树右儿子
127
128	if(l <= m_heap_size && array[l-1] > array[temp-1])//首先判断左儿子是否存在，即l<=heap_size
129	{
130		largest = l;
131	}
132	else
133	{
134		largest = temp;
135	}
136
137	if(r <= m_heap_size && array[r-1] > array[largest-1])//首先判断右儿子是否存在，即r<=heap_size
138	{
139		largest = r;
140	}
141
142	if(largest != temp)
143	{
144		int t = array[temp-1];
145		array[temp-1] = array[largest-1];
146		array[largest-1] = t;
147		maxHeapify(array, largest);//调整为大顶堆
148	}
149}
150
151/******************************************************************************
152* returns the element of A with the largest key.
153******************************************************************************/
154template<typename T>
155int binary_heap<T>::heap_maximum(void)
156{
157	if(m_length < 1)
158	{
159		cout << "array underflow !" << endl;
160		return -1;
161	}
162
163	return m_array[0];
164}
165
166/******************************************************************************
167* removes and returns the element of A with the largest key.
168* Roughly same with heap_sort if extract all nodes. 
169* Can't call with heap_sort at the same time, as m_heap_size will decrease.
170******************************************************************************/
171template<typename T>
172int binary_heap<T>::heap_extract_max(void)
173{
174	int max = 0;
175
176	if(m_heap_size < 1)
177	{
178		cout << "array underflow !" << endl;
179		return -1;
180	}
181
182	max = m_array[0];
183	m_array[0] = m_array[m_heap_size -1];
184	m_heap_size--;
185	maxHeapify(m_array, 0);
186
187	return max;
188}
189
190/******************************************************************************
191* increases the value of element i's key to the new value key, which is assumed to be at least 
192* as large as i's current key value.
193* repeatedly compares an element to its parent, exchanging their keys and continuing if the 
194* element's key is larger, and terminating if the element's key is smaller, since the max-heap 
195* property now holds.
196* roughly same with maxHeapify.
197******************************************************************************/
198template<typename T>
199int binary_heap<T>::heap_increase_key(int i, T key)
200{
201	int tmp = 0;
202	int parent = i >> 1;
203
204	if(key < m_array[i-1])
205	{
206		cout << "new key is smaller than current key." << endl;
207		return 0;
208	}
209
210	m_array[i-1] = key;
211	while( (i >= 1) && (parent >= 1) && (m_array[parent-1] < m_array[i-1]) )
212	{
213		tmp = m_array[i-1];
214		m_array[i-1] = m_array[parent-1];
215		m_array[parent-1] = tmp;
216
217		i = parent;
218		parent = i >> 1;
219	}
220
221	return 0;
222}
223
224/******************************************************************************
225* INSERT operation.The procedure first expands the max-heap by adding to the tree a new leaf 
226* whose key is -1. Then it calls HEAP-INCREASE-KEY to set the key of this new node to its 
227* correct value and maintain the max-heap property.
228* roughly same with build_max_heap.
229******************************************************************************/
230template<typename T>
231int binary_heap<T>::max_heap_insert(T key)
232{
233	m_length++;
234	m_heap_size++;
235
236	if(m_max_size < m_length)
237	{
238		cout << "max heap is overflow ~" << endl;
239		return -1;
240	}
241
242	m_array[m_heap_size-1] = -1;
243	heap_increase_key(m_heap_size, key);
244
245	return 0;
246}
247
248/******************************************************************************
249* just for test, dump array infor
250******************************************************************************/
251template<typename T>
252void binary_heap<T>::heap_dump(void)
253{
254	int i = 0;
255
256	for(i = 0; i < m_length; i++)
257	{
258		cout << m_array[i] << "  ";
259	}
260
261	cout << endl;
262}

待优化的地方有：

1、在进行堆排序时，每次取出堆顶元素，用最后一个元素替换成新堆顶，这时新堆顶明显会小于之前堆顶的两个子节点，所以是必然需要调整堆，会浪费不少时间，可以优化成从原来堆顶两个子节点中选取最大值作为新堆顶。

有任何问题，还请不吝指出谢谢~

reference:

Introduction to algorithms（算法导论第三版）

http://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F

http://zh.wikipedia.org/wiki/%E5%A0%86\_(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84)

http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/