Heapsort 和 priority queue

一、二叉堆含义及属性:

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

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

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

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

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

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

Parent(i)
    return i/2; 或者 return i >> 1;
Left(i)
    return i*2; 或者 return i << 1;
Right(i)
    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、一些任务调度算法。

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

/*************************************************************************
* heap sort algorithm and priority queue .
* Date :    28/07/2014
* author : alex xiao
* tips : 
* 1. Two different way to build a binary heap(priority queue), max_heap_insert and 
*     build_max_heap. no need call together.
* 2. heap_extract_max can‘t call with heap_sort at the same time, as m_heap_size decrease.
* 3. heap sort no need use C++ class, destory in place property. you can replace m_array with
*     array, replace m_length with array_length.
*************************************************************************/
#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;

template<typename T>
class binary_heap
{
public:
	binary_heap() : m_array(NULL), m_length(0), m_max_size(0) m_heap_size(0)
	{}
	binary_heap(int length);
	~binary_heap(void)
	{
		delete [] m_array;
	}
	void build_max_heap(T * array, int array_length);
	void heap_sort(T * array, int array_length);
	void maxHeapify(T * array, int n);
	void heap_dump(void);

	int heap_maximum(void);
	int heap_extract_max(void);
	int heap_increase_key(int i, T key);
	int max_heap_insert(T key);

private:
	T* m_array;
	int m_length;
	int m_max_size;
	int m_heap_size;
};


int main(void)
{
	int i = 0;
	int array[10] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
	int array_length = sizeof(array)/sizeof(array[0]);

	binary_heap<int> bh(array_length);
	for(i = 0; i < array_length; i++)
	{
		bh.max_heap_insert(array[i]);
	}

	cout << "Before sort : " << endl;
	bh.heap_dump();

	bh.heap_sort(array, array_length);

	return 0;
}

template<typename T>
binary_heap<T>::binary_heap(int length)
{
	m_array = new T[length];
	m_length = 0;
	m_heap_size = 0;
	m_max_size = length;
}

/******************************************************************************
* runs in O(lgn) time, sorts an array in place.
* tips: heap sort no need use C++ class, destory in place property. you can replace m_array with
*     array, replace m_length with array_length.
******************************************************************************/
template<typename T>
void binary_heap<T>::heap_sort(T * array, int array_length)
{
	int i = 0;
	int heap_size = m_length;
	build_max_heap(m_array, m_length);

	cout << "After build_max_heap : " << endl;
	heap_dump();

	for(i = m_length-1; i>=0; i--)//数组中下标从0  -  n-1
	{
		int temp = m_array[0];
		m_array[0] = m_array[i];
		m_array[i] = temp;
		m_heap_size--;
		maxHeapify(m_array, 1);//在堆中，堆顶元素下标从1开始
	}

	cout << "After Sort : " << endl;
	heap_dump();
}

/******************************************************************************
* runs in linear time, produces a max-heap from an unordered input array
******************************************************************************/
template<typename T>
void binary_heap<T>::build_max_heap(T * array, int array_length)
{
	int i = 0;
	m_heap_size = array_length;

	for(i = array_length/2 ; i>=1 ; i--)//注意i的取值,堆的高度从1  -  n/2
	{
		maxHeapify(array, i);
	}
}

/******************************************************************************
* runs in O(lgn) time, the key to maintaining the max-heap property.
******************************************************************************/
template<typename T>
void binary_heap<T>::maxHeapify(T * array, int temp)
{
	int largest = 0;//以temp为顶点的子树的堆顶
	int l = temp << 1;//求以temp为顶点的子树左儿子
	int r = (temp << 1) + 1;//求以temp为顶点的子树右儿子

	if(l <= m_heap_size && array[l-1] > array[temp-1])//首先判断左儿子是否存在，即l<=heap_size
	{
		largest = l;
	}
	else
	{
		largest = temp;
	}

	if(r <= m_heap_size && array[r-1] > array[largest-1])//首先判断右儿子是否存在，即r<=heap_size
	{
		largest = r;
	}

	if(largest != temp)
	{
		int t = array[temp-1];
		array[temp-1] = array[largest-1];
		array[largest-1] = t;
		maxHeapify(array, largest);//调整为大顶堆
	}
}

/******************************************************************************
* returns the element of A with the largest key.
******************************************************************************/
template<typename T>
int binary_heap<T>::heap_maximum(void)
{
	if(m_length < 1)
	{
		cout << "array underflow !" << endl;
		return -1;
	}

	return m_array[0];
}

/******************************************************************************
* removes and returns the element of A with the largest key.
* Roughly same with heap_sort if extract all nodes. 
* Can‘t call with heap_sort at the same time, as m_heap_size will decrease.
******************************************************************************/
template<typename T>
int binary_heap<T>::heap_extract_max(void)
{
	int max = 0;

	if(m_heap_size < 1)
	{
		cout << "array underflow !" << endl;
		return -1;
	}

	max = m_array[0];
	m_array[0] = m_array[m_heap_size -1];
	m_heap_size--;
	maxHeapify(m_array, 0);

	return max;
}

/******************************************************************************
* increases the value of element i‘s key to the new value key, which is assumed to be at least 
* as large as i‘s current key value.
* repeatedly compares an element to its parent, exchanging their keys and continuing if the 
* element‘s key is larger, and terminating if the element‘s key is smaller, since the max-heap 
* property now holds.
* roughly same with maxHeapify.
******************************************************************************/
template<typename T>
int binary_heap<T>::heap_increase_key(int i, T key)
{
	int tmp = 0;
	int parent = i >> 1;

	if(key < m_array[i-1])
	{
		cout << "new key is smaller than current key." << endl;
		return 0;
	}

	m_array[i-1] = key;
	while( (i >= 1) && (parent >= 1) && (m_array[parent-1] < m_array[i-1]) )
	{
		tmp = m_array[i-1];
		m_array[i-1] = m_array[parent-1];
		m_array[parent-1] = tmp;

		i = parent;
		parent = i >> 1;
	}

	return 0;
}

/******************************************************************************
* INSERT operation.The procedure first expands the max-heap by adding to the tree a new leaf 
* whose key is -1. Then it calls HEAP-INCREASE-KEY to set the key of this new node to its 
* correct value and maintain the max-heap property.
* roughly same with build_max_heap.
******************************************************************************/
template<typename T>
int binary_heap<T>::max_heap_insert(T key)
{
	m_length++;
	m_heap_size++;

	if(m_max_size < m_length)
	{
		cout << "max heap is overflow ~" << endl;
		return -1;
	}

	m_array[m_heap_size-1] = -1;
	heap_increase_key(m_heap_size, key);

	return 0;
}

/******************************************************************************
* just for test, dump array infor
******************************************************************************/
template<typename T>
void binary_heap<T>::heap_dump(void)
{
	int i = 0;

	for(i = 0; i < m_length; i++)
	{
		cout << m_array[i] << "  ";
	}

	cout << endl;
}

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

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)

Heapsort 和 priority queue,布布扣,bubuko.com

Heapsort 和 priority queue

原文：http://my.oschina.net/amince/blog/296592