堆排序

数据结构

  一个堆是一个完全二叉树，如下图所示。每个节点的值小于等于其子节点的值，最小值在根节点。

堆使用的是下标从1开始的数组，常用的函数定义有：

1. root = 1
2. value[i] = x[i]
3. leftchild(i) = 2 * i
4. rightchild(i) = 2 * i + 1
5. parent(i) = i / 2 ( 向下取整 )
6. null[i] = (i < 1) or (i > n)

两个关键的函数

  在排序的过程中当数组不满足堆的性质时需要进行动态调整。siftup()用来调整堆中增加元素的情况, siftdown()用来调整堆减少元素时的情况。

siftup

  思路：新元素加入到数组末尾，比较新元素跟父元素的大小，如果比父元素小，则交换二者位置，再继续比较，直到根节点或者比父元素大为止。

void siftup(int *tree, int n)
{    
    int i = n, p = i / 2;
    while(tree[p] > tree[i] && i != 1) {
        swap(tree, p, i);
        i = p;
        p = i / 2;
    }
}

siftdown

  思路：将根节点元素取出（最小元素），把末尾元素放到根节点，向下调整。若根节点值大于子节点的值，交换二者位置，直到父节点的值小于两个子节点的值或者到达数组末尾。

void siftdown(int *tree, int n)
{
    int i = 1;
    int c;
    while(1) {
        c = 2 * i;
        if (c > n)
            break;
        if(c + 1 <= n && tree[c] > tree[c+1])
            c++;
        if(tree[c] > tree[i])
            break;
        swap(tree, c, i);
        i = c;
    }
}

  两个函数是通过*2或者/2来进行操作，因此动态调整一次堆的复杂度为log(n)。

排序

  有了上面两个函数，我们就可以很方便的对数组进行排序。首先将数组构建为堆，然后不断取堆顶元素，调整堆，直到元素取完。

void hsort(int * tree, int n)
{
    int i;
    /* 堆下标从1开始，只有1个元素时不需要调整，因此i从2开始 */
    for(i=2; i<n; i++)
        siftup(tree, i);
    
    for(i=n-1; i>1; i--) {
        swap(tree, 1, i);
        siftdown(tree, i-1);
    }
}