堆排序
维基百科，自由的百科全书
堆排序（Heap Sort）是指利用堆（heaps）这种数据结构来构造的一种排序算法。堆是一个近似完全二叉树结构，并同时满足堆属性：即子节点的键值或索引总是小于（或者大于）它的父节点。
目录 |
[编辑] 堆节点的访问
在起始索引为0的实现中:
- 堆的根节点（即堆的最大值）存放在位置0
- 节点j的左子节点在位置（2*j+1）
- 节点j的右子节点在位置（2*j+2）
- 节点j的父节点在位置floor((j-1)/2)
在起始索引为1的实现中:
- 堆的根节点（即堆的最大值）存放在位置1
- 节点j的左子节点在位置（2*j）
- 节点j的右子节点在位置（2*j+1）
- 节点j的父节点在位置floor(j/2)
[编辑] 堆的操作
在堆的数据结构中，堆中的最大值总是位于根节点。堆中定义了以下几种操作：
- 删除根节点（delete_max）：从堆的根节点处取出数据，然后删除根节点
- 插入一节点（insert）：将一数据插入堆中
- 删除一节点（delete）：将一数据从堆中删除
[编辑] 堆属性的保持
在堆中进行了上述操作后，堆的特殊属性可能发生变化。例如，当在堆尾插入一个数据，它可能大于它的父节点，因而需要进行一系列的置换操作，调整它的位置，从而保持堆的特有属性。和此相关的操作包括：
- 筛选上移（sift_up）：给定某个数据后，将其上移到相应的位置，从而保证其值不大于父节点。
- 筛选下移（sift_down）：给定某个数据后，将其下移到相应的位置，从而保证其值不大于父节点。
[编辑] 示例代码
#define MAX_HEAP_LEN 100
static int heap[MAX_HEAP_LEN];
static int heap_size = 0; // the number of elements in heaps
static void swap(int* a, int* b)
{
int temp = 0;
temp = *b;
*b = *a;
*a = temp;
}
static void sift_up(int i)
{
int done = 0;
if( i == 0) return; //node is the root already
while((i!=0)&&(!done))
{
if(heap[i] > heap[(i-1)/2])
{//if the current is larger than the parent, then swap
swap(&heap[i],&heap[(i-1)/2]);
}
else
{// the job is already done.
done =1;
}
i = (i-1)/2;
}
}
static void sift_down(int i)
{
int done = 0;
if (2*i + 1> heap_size) return; // node i is a leaf
while((2*i+1 < heap_size)&&(!done))
{
i =2*i+1; // jump to left child
if ((i+1< heap_size) && (heap[i+1] > heap[i]))
{// find the bigger one of the two children
i++;
}
if (heap[(i-1)/2] < heap[i])
{
swap(&heap[(i-1)/2], &heap[i]);
}
else
{
done = 1;
}
}
}
static void delete(int i)
{
int current = heap[i]; // the one to be deleted
int last = heap[heap_size - 1]; // get the last one;
heap_size--; // shrink the heap
if (i == heap_size) return;
heap[i] = last; // use the last item to overwrite the current
if(last >= current)
sift_up(i);
else
sift_down(i);
}
int delete_max()
{
int ret = heap[0];
delete(0);
return ret;
}
void insert(int new_data)
{
if(heap_size >= MAX_HEAP_LEN) return;
heap_size++;
heap[heap_size - 1] = new_data;
sift_up(heap_size - 1);
}
[编辑] in-place堆排序
基于以上堆相关的操作，我们可以很容易的定义堆排序。例如，假设我们已经读入一系列数据并创建了一个堆，一个最直观的算法就是反复的调用del_max()函数，因为该函数总是能够返回堆中最大的值，然后把它从堆中删除，从而对这一系列返回值的输出就得到了该序列的降序排列。真正的in-place的堆排序使用了另外一个小技巧。对排序的过程是：
- 建立一个堆H[0..n-1]
- 把堆首（最大值）和堆尾互换
- 把堆的尺寸缩小1，并调用sift_down(0),目的是把新的数组顶端数据调整到相应位置
- 重复2号步骤，直到堆的尺寸为1
[编辑] 平均复杂度
堆排序的平均时间复杂度为O(n log n)，空间复杂度为Θ (1)。
