一、堆（heap）
别称：优先队列（priority queue）
思想：（参考维基百科：http://zh.wikipedia.org/zh-cn/堆 ）
在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。
http://en.wikipedia.org/wiki/Heapsort）
In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then the key of node A is ordered with respect to the key of node B with the same ordering applying
across the heap.
堆是一种树形数据结构，根据结点和父结点的关系，堆可以分为：
最大堆 / 大根（顶）堆（max heap）：每个节点的值 >= 其左右孩子值（如果有），最大值位于根结点。
最小堆 / 小根（顶）堆（min heap）：每个节点的值 <= 其左右孩子值（如果有），最小值位于根结点。
实现：通常采用二叉堆（binary heap），此时堆的一棵完全二叉树（complete binary tree），方便使用数组形式进行实现。
（其他实现：斐波那契堆、二项式堆）
二、堆的抽象数据类型
一般采用顺序存储结构（数组）形式实现。
基本操作：
建立一个空堆；
清空一个堆；
销毁一个堆；（针对动态数组）
堆化一个数组：使给定数组满足堆的性质(heapify)；
向堆中插入一个新元素，并使新堆满足堆性质；（时间复杂度：O(lgn)）
删除堆顶元素，并使新堆满足堆性质；（时间复杂度：O(lgn)）
获取当前堆顶的元素值；
三、堆的思考
1.实现抽象数据类型：优先队列（priority queue）
普通队列：一种先进先出（first-in,first-out）的数据结构，元素在队列尾追加，而从队列头删除。
优先队列：元素被赋予优先级，优先队列具有最高进先出 （largest-in,first-out）的行为特征。一般普通的队列添加是在最后加入，但优先级队列却不一定添加到最后，它会按照优先级算法把它插入到队列当中去，出队时还是从第一个开始，即取根元素，这样保证了队列中优先级高（即根结点）的先服务，而不是先来先服务了。至于优先级算法如何得出最高权限完全是根据需要自定义。（参考：http://gwoham-163-com.iteye.com/blog/1940227）
关键：优先队列出队操作：优先级最高的先出队。
2.堆排序（Heap Sort）
其基本思想是将待排序的数组构造成一个大顶堆，从而获得数组最大的元素，即当前的根节点。将其移走之后，再把剩余的n-1个数组元素重新构造成一个大顶堆。反复执行，最后得到一个有序序列。
堆排序属于选择排序。
堆排序时间复杂度O(nlgn)。
四、算法C实现
二叉堆：顺序存储结构（数组），利用完全二叉树的性质来实现。
注意：
二叉堆可通过宏定义设置为最大堆或最小堆。
这里二叉堆的实现数组第一个位置不存放元素保证数组元素对应下标与完全二叉树索引一致，方便对结点到父亲结点和孩子结点索引的转换，此时数组下标0时的位置存储的数据无意义的。（网上另一些实现中不使用这个方法，数组第一个下标0的位置存储堆顶元素。）
入队（插入）操作：自下而上重新建堆，入队前的堆必须满足堆性质。这里的算法在实现时，把入队元素一次插入到正确位置，避免频繁交换元素。
出队（删除）操作：自上而下重新建堆，出队前的堆必须满足堆性质。
堆化数组：堆化一个数组时，所有的叶子结点的子树已满足堆条件，故只考虑非叶子结点，调整每个子树，使之满足堆性质，最终使整个数组成为堆。
堆排序步骤：
1.堆化一个给定的数组（最大堆和最小堆不同以实现数组从小到大排序及数组从大到小排序）；
2.堆顶数据和堆尾互换；
3.把堆长度缩小一，重新堆化数组；
4.重复步骤2、3，直到堆长度为1，此时数组按序排列。
头文件：
/**
* @file heap.h
* @brief heap data structure header.
* The heap use sequence list by dynamic array.
* @author chenxilinsidney
* @version 1.0
* @date 2015-02-05
*/
#ifndef __HEAP__
#define __HEAP__
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// #define NDEBUG
#include <assert.h>
/// function return state
#ifndef OK
#define OK 1
#endif
#ifndef ERROR
#define ERROR 0
#endif
#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif
/// data type, can be modified
typedef int Status; ///< status data type
typedef int ElementType; ///< element data type
typedef int CommonType; ///< common data type
/// heap data structure
#define MAX_HEAP 1
#define MIN_HEAP 0
#define HEAP_TYPE MIN_HEAP ///< heap type, can by modified
#if HEAP_TYPE == MAX_HEAP
#define HEAP_CMP_SYMBOL >
#elif HEAP_TYPE == MIN_HEAP
#define HEAP_CMP_SYMBOL <
#endif
/// macro definition of child node and parent node
#define LCHILD(i) ((unsigned)(i) << 1)
#define RCHILD(i) (((unsigned)(i) << 1) + 1)
#define PARENT(i) ((unsigned)(i) >> 1)
typedef struct {
ElementType* data; ///< heap elements array pointer
CommonType max_size; ///< heap max elements count
CommonType size; ///< heap elements count
}Heap;
/// heap methods
/// initialize heap:create an empty heap with special max size
void InitHeap(Heap* H, CommonType max_size);
/// create a heap out of given array of elements
void BuildHeap(Heap* H, CommonType max_size,
ElementType* array, CommonType length);
/// clear heap: make heap as first initialized
void ClearHeap(Heap* H);
/// destroy heap: free heap memory, need to intitialize it if reused
void DestroyHeap(Heap* H);
/// return true if the heap is empty, false otherwise
Status HeapEmpty(Heap* H);
/// return true if the heap is full, false otherwise
Status HeapFull(Heap* H);
/// return the number of items in the heap
CommonType HeapSize(Heap* H);
/// find the maximum item of a max-heap or a minimum item of a min-heap
Status HeapGet(Heap* H, ElementType* e);
/// adding a new key to the heap
Status HeapInsert(Heap* H, ElementType e);
/// remove the root node of a max-heap or min-heap, respectively
Status HeapDelete(Heap* H, ElementType* e);
/// heap sort method for input array
void HeapSort(ElementType* array, CommonType length);
#endif // __HEAP__
实现文件：
/**
* @file heap.c
* @brief heap method implements.
* The methods use <assert.h> to help debug the program.
* The heap use sequence list by dynamic array.
* @author chenxilinsidney
* @version 1.0
* @date 2015-02-05
*/
#include "heap.h"
/**
* @brief swap two elements
*
* @param[in] a element pointer a
* @param[in] b element pointer b
*/
static void swap(ElementType* a, ElementType* b)
{
/// swap by third element
ElementType c = *a;
*a = *b;
*b = c;
}
/**
* @brief initialize heap:create an empty heap with special max size.
*
* @param[in,out] H heap struct pointer
* @param[in] H heap max size
*
*/
void InitHeap(Heap* H, CommonType max_size)
{
assert(H != NULL && max_size > 0);
if ((H->data = (ElementType*)malloc((max_size + 1) *
sizeof(ElementType))) == NULL) {
assert(0);
exit(EXIT_FAILURE);
}
H->max_size = max_size;
H->size = 0;
}
/**
* @brief heap shift down: move a element down in the tree.
* as long as needed(depending on the condition:min-heap or max-heap).
*
* @param[in] array heap elements array
* @param[in] index array begin index to create heap
* @param[in] size heap elements array length
*
*/
static void Heapify(ElementType* array, CommonType index,
CommonType length)
{
assert(array != NULL && index >= 1 && length >= 0);
CommonType min_index;
while (index < length) {
min_index = index;
/// get maximum or minimum child index
if (LCHILD(index) <= length &&
array[LCHILD(index)] HEAP_CMP_SYMBOL array[min_index])
min_index = LCHILD(index);
if (RCHILD(index) <= length &&
array[RCHILD(index)] HEAP_CMP_SYMBOL array[min_index])
min_index = RCHILD(index);
if (min_index != index) {
swap(array + index, array + min_index);
index = min_index;
} else {
break;
}
}
}
/**
* @brief create a heap out of given array of elements.
*
* @param[in,out] H heap struct pointer
* @param[in] H heap max size
* @param[in] array heap elements array
* @param[in] length heap elements array count
*
*/
void BuildHeap(Heap* H, CommonType max_size,
ElementType* array, CommonType length)
{
assert(H != NULL && array != NULL && max_size > 0 && length > 0);
/// memory pointer
H->data = array;
/// size
H->max_size = max_size;
H->size = length;
/// heapify
CommonType index;
for (index = PARENT(length); index > 0; index--)
Heapify(H->data, index, length);
}
/**
* @brief clear heap: make heap as first initialized.
*
* @param[in,out] H heap struct pointer
*
*/
void ClearHeap(Heap* H)
{
assert(H != NULL && H->data != NULL && H->max_size > 0);
H->size = 0;
}
/**
* @brief destroy heap: free heap memory, need to intitialize it if reused.
*
* @param[in,out] H heap struct pointer
*
*/
void DestroyHeap(Heap* H)
{
assert(H != NULL);
free(H->data);
H->data = NULL;
H->max_size = 0;
H->size = 0;
}
/**
* @brief return true if the heap is empty, false otherwise.
*
* @param[in] H heap struct pointer
*
* @return return TRUE if empty, FALSE otherwise
*/
Status HeapEmpty(Heap* H)
{
assert(H != NULL && H->data != NULL && H->max_size > 0 && H->size >= 0);
if (H->size)
return FALSE;
else
return TRUE;
}
/**
* @brief return true if the heap is full, false otherwise.
*
* @param[in] H heap struct pointer
*
* @return return TRUE if empty, FALSE otherwise
*/
Status HeapFull(Heap* H)
{
assert(H != NULL && H->data != NULL && H->max_size > 0 && H->size >= 0);
if (H->size == H->max_size)
return TRUE;
else
return FALSE;
}
/**
* @brief return the number of elements in the heap.
*
* @param[in] H heap struct pointer
*
* @return the number of elements in the heap
*/
CommonType HeapSize(Heap* H)
{
assert(H != NULL && H->data != NULL && H->max_size > 0 && H->size >= 0);
return H->size;
}
/**
* @brief find the maximum item of a max-heap or a minimum item of a min-heap.
*
* @param[in] H heap struct pointer
* @param[out] e the element
*
* @return OK if success, ERROR otherwise
*/
Status HeapGet(Heap* H, ElementType* e)
{
assert(H != NULL && H->data != NULL && H->max_size > 0 && H->size >= 0);
/// detect if heap if empty
if (HeapEmpty(H) == TRUE)
return ERROR;
/// delete root element
*e = H->data[1];
return OK;
}
/**
* @brief adding a new element to the heap.
*
* @param[in] H heap struct pointer
* @param[in] e the element
*
* @return OK if success, ERROR otherwise
*/
Status HeapInsert(Heap* H, ElementType e)
{
assert(H != NULL && H->data != NULL && H->max_size > 0 && H->size >= 0);
/// detect if heap if full
if (HeapFull(H) == TRUE)
return ERROR;
/// add element to last
CommonType index = ++(H->size);
/// heap shift up: move a element up in the tree.
/// as long as needed(depending on the condition:min-heap or max-heap).
while (index > 1 && e HEAP_CMP_SYMBOL H->data[PARENT(index)]) {
H->data[index] = H->data[PARENT(index)];
index = PARENT(index);
}
H->data[index] = e;
return OK;
}
/**
* @brief remove the root element of a max-heap or min-heap, respectively.
*
* @param[in] H heap struct pointer
* @param[out] e the element
*
* @return OK if success, ERROR otherwise
*/
Status HeapDelete(Heap* H, ElementType* e)
{
assert(H != NULL && H->data != NULL && H->max_size > 0 && H->size >= 0);
/// detect if heap if empty
if (HeapEmpty(H) == TRUE)
return ERROR;
/// delete root element and move last element to root
*e = H->data[1];
H->data[1] = H->data[(H->size)--];
/// heapify
Heapify(H->data, 1, H->size);
return OK;
}
/**
* @brief heap sort method for input array.
*
* @param[in,out] array input and output array
* @param[in] length array length
*
* @warning if the heap is max-heap, the elements in the array will increase
* by index, otherwise decrease.
*/
void HeapSort(ElementType* array, CommonType length)
{
/// make heap elements index begin from 1
ElementType* array_new = array - 1;
/// build heap by elements
Heap heap;
BuildHeap(&heap, length, array_new, length);
/// move root element to the end and heapify smaller size array
CommonType new_size = length;
while (new_size > 1) {
swap(array_new + new_size, array_new + 1);
Heapify(array_new, 1, --new_size);
}
}