减少订单堆排序

我一直在试图学习如何实现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

减少订单堆排序

回答

相关问题