Heapsort - 構建堆

Question

我們必須知道如何使用堆排序。我無法理解一件事：當我們構建堆時，爲什麼循環中使用的大小除以2（聲明爲計數器「i」）？下面顯示了代碼。如果有人會向我解釋，我會很感激。

// heap 

void heapify (int tab[], int o, int heapsize) 
{ 
    int l = 2 * o + 1; 
    int r = l + 1; 
    int largest; 

    if (l <= heapsize && tab[o] > tab[l]) 
     largest = l; 
    else 
     largest = o; 

    if (r <= heapsize && tab[largest] > tab[r]) 
     largest = r; 

    if (largest != o) 
    { 
     swap(tab[o], tab[largest]); 
     heapify(tab, largest, heapsize); 
    } 
} 

void build_heap(int tab[], int heapsize) 
{ 
    for (int i = heapsize/2; i >= 0; i--) 
     heapify(tab, i, heapsize); 
} 

void heap_sort(int tab[], int size) 
{ 
    int heapsize = size; 
    build_heap(tab, heapsize); 

    do{ 
     swap(tab[0], tab[heapsize]); 
     heapify(tab, 0, heapsize - 1); 
     heapsize--; 
    } while (heapsize > 0); 
} 

Answer 1

我假設你的意思行

for (int i = heapsize/2; i >= 0; i--) 

那麼，發生了什麼事是這樣的。但首先，這是一堆小費。你必須不斷在兩種方式之間切換來思考一個堆：一個連續的數組和一棵樹。

所以，如果你看一下heapify，可以在陣列表示看到，對於指數i，代碼考慮l和r這是2 * i和2 * i +。在樹形表示中，這些是左側和右側的孩子。

現在在堆表示中，什麼是heapsize/2？這是倒數第二排的一部分，實際上有孩子。這些孩子將被heapify函數考慮（我們剛剛看到了這一點）。從右邊開始沒有意義，因爲沒有兒童可以比較。