堆排序heapify

Question

我發現代碼從一個堆排序：http://rosettacode.org/wiki/Sorting_algorithms/Heapsort#C

我的理解（這是錯誤的某處沿着線）的方式是堆排序（）函數有兩個循環。第一個循環是創建堆結構（最小或最大），第二個循環是實際對雙精度進行排序。但我認爲我的第一個循環錯了。

整個代碼是這樣

#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 /循環開始（計數2）/ 2？

從堆排序的片段（）位置：

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

UPDATE

我想我可能只是回答我自己的問題，但它是因爲我們要建立一個堆結構，循環的部分重點在於創建一個平衡樹？也就是說，除了最後一個之外，堆必須填滿每個級別。這是正確的想法嗎？

Answer 1

對於奇數計數，堆積的第一個子對是[（（count-2）/ 2）* 2 + 1]和[（（count-2）/ 2）* 2 + 2]，數組的最後兩個元素。對於偶數，獨奏子在[（（count-2）/ 2）* 2 + 1]，即數組的最後一個元素。這是堆棧整個陣列的起點。第二個循環只需要重新heapified一個大部分heapfied數組[0結束]作爲結束降低。

維基文章：

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

你說