Сортировка кучи по убыванию - PullRequest
Новая
       11

Сортировка кучи по убыванию

1 голос
/ 24 марта 2011

Я пытался узнать, как реализовать 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;
  }
}

Если бы кто-то мог указать, какую часть кода нужно изменить, это было бы чрезвычайно полезно:).

1 Ответ

2 голосов
/ 24 марта 2011

То, что вы реализовали, это «максимальная куча» (т. Е. Значения дочерних элементов каждого узла меньше, чем значения родительского узла).Вам нужно просто изменить функцию siftDown, чтобы родительский элемент всегда был меньше дочерних.

Это делает его минимальной кучей и подает значения в обратном порядке (поскольку самые маленькие элементы сначала попадают в верхнюю часть кучи), что дает вам сортировку по убыванию.

...