減少訂單堆排序

我一直在試圖學習如何實現heapsort。減少訂單堆排序

特別是，我有一個heapsort算法，它將輸入的排列順序排序，，但我無法弄清楚需要改變什麼才能使它降序。

下面是代碼：（一些，這是從教科書）

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

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

    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; 
    } 
}

如果有人能指出需要什麼樣的代碼的部分改變，這將是非常有幫助:)。

來源

2011-03-24 Blackbinary

提示：你如何確定哪個元素應該在另一個之前？改變這一點。 – 2011-03-24 16:19:35

感謝您的提示，我只是在siftDown中改變了一個地方。一旦我改變了它的功能:)如果其他和交換部分:) – Blackbinary 2011-03-24 16:48:43

你實現的是一個「最大堆」（即每個節點的子節點的值小於父節點的值）。您只需更改siftDown函數，以便父項總是小於子項。

這使它成爲最小堆並以相反的順序提供值（因爲最小的元素首先到達堆頂部），因此會給出降序排序。

來源

2011-03-24 16:41:35 MAK

謝謝，我唯一的問題是我只是在siftDown改變一個點。 – Blackbinary 2011-03-24 16:49:14

減少訂單堆排序

回答

相關問題