堆排序功能需要說明

Question

有人可以清楚地向我解釋堆分類的這些功能是如何工作的？

void heapSort(int numbers[], int array_size) 
{ 
    int i, temp; 

    for (i = (array_size/2)-1; i >= 0; i--) 
    siftDown(numbers, i, array_size); 

    for (i = array_size-1; i >= 1; i--) 
    { 
    temp = numbers[0]; 
    numbers[0] = numbers[i]; 
    numbers[i] = temp; 
    siftDown(numbers, 0, i-1); 
    } 
} 


void siftDown(int numbers[], int root, int bottom) 
{ 
    int done, maxChild, temp; 

    done = 0; 
    while ((root*2 <= bottom) && (!done)) 
    { 
    if (root*2 == bottom) 
     maxChild = root * 2; 
    else if (numbers[root * 2] > numbers[root * 2 + 1]) 
     maxChild = root * 2; 
    else 
     maxChild = root * 2 + 1; 

    if (numbers[root] < numbers[maxChild]) 
    { 
     temp = numbers[root]; 
     numbers[root] = numbers[maxChild]; 
     numbers[maxChild] = temp; 
     root = maxChild; 
    } 
    else 
     done = 1; 
    } 
} 

Answer 1

This page對堆排序圖有充分的解釋。它可以幫助你把它想象成一個比賽：首先你插入所有的球員，這樣頂尖球員就是勝利者。然後你提取勝利者，提升失敗者爲新的贏家，並進行調整，以便你再次獲得適當的比賽，新的贏家是剩下的最好的選手。

然後你迭代。

Answer 2

public class heapsort 
{ 


public static void buildheap(int[] a, int nextLimit) 
{ 
    // for parent 3 child is 3*2+1=7 and 3*2+2=8 hence parent if odd n+1/2-1 i.e (7+1)/2-1=3 for odd n/2-1 8/2-1=3 
    int child = nextLimit % 2 == 1 ? nextLimit + 1 : nextLimit; 
    for (int parent = child/2 - 1; parent >= 0; parent--) { 
     heapfy(a, parent, nextLimit); 
    } 


} 

public static void heapfy(int[] a, int parentIndex, int limit) 
{ 
    int maxChildIndex; 
    //if parent have only one child (java array index start from 0 hence left one 2i+1 and right one 2i+2) 
    if ((2 * parentIndex + 2) > limit) { 
     maxChildIndex = 2 * parentIndex + 1; 
    } else { 
     //find max value index from two child 
     maxChildIndex = a[2 * parentIndex + 1] > a[2 * parentIndex + 2] ? 2 * parentIndex + 1 : 2 * parentIndex + 2; 
    } 


    //swap if parent less than max child bring max value to parent 
    if (a[maxChildIndex] > a[parentIndex]) { 

     int maxValue = a[maxChildIndex]; 
     a[maxChildIndex] = a[parentIndex]; 
     a[parentIndex] = maxValue; 

    } 


} 


public static void main(String[] args) 
{ 
    int[] a = {2, 5, 4, 6, 77, 3, 1, 8}; 
    for (int nextArrayLength = a.length - 1; nextArrayLength >= 0; nextArrayLength--) { 
     buildheap(a, nextArrayLength); 

     //push to first to last 
     int highest = a[0]; 
     a[0] = a[nextArrayLength]; 
     a[nextArrayLength] = highest; 
    } 


    for (int i = 0; i < a.length; i++) { 


     System.out.println(a[i]); 
    } 


} 

}