堆排序堆化

Question

我从以下位置找到堆排序代码：http://rosettacode.org/wiki/Sorting_algorithms/Heapsort#C

我的理解方式（在某些地方是错误的）是 heapsort() 函数有两个循环。第一个循环是创建堆结构（最小或最大），第二个循环是对双打进行实际排序。但是我想我的第一个循环是错误的。

整个代码是这样的

#include <stdio.h>
#include <stdlib.h>

#define ValType double
#define IS_LESS(v1, v2)  (v1 < v2)

void siftDown( ValType *a, int start, int count);

#define SWAP(r,s)  do{ValType t=r; r=s; s=t; } while(0)

void heapsort( ValType *a, int count)
{
    int start, end;

    /* heapify */
    for (start = (count-2)/2; start >=0; start--) {
        siftDown( a, start, count);
    }

    for (end=count-1; end > 0; end--) {
        SWAP(a[end],a[0]);
        siftDown(a, 0, end);
    }
}

void siftDown( ValType *a, int start, int end)
{
    int root = start;

    while ( root*2+1 < end ) {
        int child = 2*root + 1;
        if ((child + 1 < end) && IS_LESS(a[child],a[child+1])) {
            child += 1;
        }
        if (IS_LESS(a[root], a[child])) {
            SWAP( a[child], a[root] );
            root = child;
        }
        else
            return;
    }
}


int main()
{
    int ix;
    double valsToSort[] = {
        1.4, 50.2, 5.11, -1.55, 301.521, 0.3301, 40.17,
        -18.0, 88.1, 30.44, -37.2, 3012.0, 49.2};
#define VSIZE (sizeof(valsToSort)/sizeof(valsToSort[0]))

    heapsort(valsToSort, VSIZE);
    printf("{");
    for (ix=0; ix<VSIZE; ix++) printf(" %.3f ", valsToSort[ix]);
    printf("}\n");
    return 0;
}

我的问题是，为什么 /heapify/ 循环从 (count-2)/2 开始？

这里是 heapsort() 的片段：

    /* heapify */
    for (start = (count-2)/2; start >=0; start--) {
        siftDown( a, start, count);
    }

更新

我想我可能刚刚回答了我自己的问题，但是否因为我们必须建立一个堆结构，其中循环的部分重点是创建平衡树？也就是说，堆必须填满除最后一层以外的每一层。这是正确的想法吗？

Answer 1

对于奇数，heapify 的第一个 child 对是 a[((count-2)/2)*2 + 1] 和 a[((count-2)/2)*2 + 2]，数组的最后两个元素。对于偶数，solo child 位于数组的最后一个元素 [((count-2)/2)*2 + 1] 处。这是堆化整个数组的起点。第二个循环只需要 re-heapify 一个大部分堆积的数组 [0 到结束] 作为结束递减。

维基文章：

http://en.wikipedia.org/wiki/Heapsort

堆排序堆化

Heapsort heapify

c

sorting

heap

heapsort