CODEWITHSUNDEEP
csortingheapheapsort
Blackbinary
Blackbinary

Reputation: 3986

Decending Order Heap Sort

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

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

Upvotes: 1

Views: 2616

Answers (1)

MAK
MAK

Reputation: 26586

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.

Upvotes: 2

Related Questions