开发者

Decending Order Heap Sort

开发者 https://www.devze.com 2023-02-19 06:54 出处:网络
I\'ve been trying to learn how to implement a heapsort. In particular, I have a heapsort algorithm which sorts the input in acending order,

I've been trying to learn how to implement a heapsort.

In particular, I have a heapsort algorithm which sorts the input in acending order, but i can't figure out what needs to be changed to make it decending order.

Here is the code: (Some of this is from the textbook)

void heapSor开发者_开发百科t(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;
  }
}

If anyone could point out what portion of the code needs to be changed, that would be extremely helpful :).


What you have implemented is a "max heap" (i.e. the values of the children of each node are smaller than the value of the parent node). You need to just change the siftDown function so that the parent is always the smaller than the children.

This makes it a min-heap and serves up the values in reverse order (since the smallest elements are getting to the top of the heap first), thus giving you a descending order sort.

0

精彩评论

暂无评论...
验证码 换一张
取 消