Каков самый быстрый способ (по крайней мере теоретически) отсортировать кучу?

StackOverflow https://stackoverflow.com/questions/113991

  •  02-07-2019
  •  | 
  •  

Вопрос

Куча — это список, к которому применимо следующее:

l[i] <= l[2*i] && l[i] <= [2*i+1]

для 0 <= i < len(list)

Я ищу сортировку на месте.

Это было полезно?

Решение

Итак, вы уже наполовину выполнили пирамидальную сортировку, поскольку ваши данные собраны в кучу.Вам просто нужно реализовать вторую часть алгоритма сортировки кучей.Это должно быть быстрее, чем использование быстрой сортировки в массиве кучи.

Если вы чувствуете себя смелым, вы можете попробовать реализовать гладкая сортировка, что быстрее, чем пирамидальная сортировка для почти отсортированных данных.

Другие советы

Просто используйте пирамидальную сортировку.Это на месте.Это был бы самый естественный выбор.

Вы также можете просто использовать свою кучу и отсортировать ее с помощью другого алгоритма.После этого вы заново создаете кучу из отсортированного списка.Быстрая сортировка — хороший кандидат, потому что вы можете быть уверены, что она не будет работать в наихудшем порядке O(n²) просто потому, что ваша куча уже предварительно отсортирована.

Это может быть быстрее, если ваша функция сравнения дорогая.Сортировка кучей имеет тенденцию довольно часто оценивать функцию сравнения.

Сортировка кучи на месте звучит как работа для Сортировка кучей.

Я предполагаю, что память ограничена, возможно, встроенное приложение?

Поскольку у вас уже есть куча, не могли бы вы просто использовать вторую фазу сортировка кучей?Он работает на месте и должен быть красивым и эффективным.

Для сортировки на месте следует самый быстрый способ.Остерегайтесь ошибок в моем коде.Обратите внимание, что этот метод дает обратно отсортированный список, который необходимо отменить на последнем этапе.Если вы используете max-heap, эта проблема исчезнет.

Общая идея ясна:замените наименьший элемент (с индексом 0) последним элементом в куче, опустите этот элемент вниз до тех пор, пока свойство кучи не будет восстановлено, уменьшите размер кучи на единицу и повторите.

Как показывает Дэвид Маккей, это не самый быстрый способ сортировки не на месте. здесь - вы можете добиться большего, поместив элемент, который, скорее всего, будет самым маленьким, в верхней части кучи, а не в нижнем ряду.

Временная сложность равна T(n.log n) в худшем случае - n итераций с возможно log n (высотой кучи) проходят через цикл while.

for (int k=len(l)-1;k>0;k--){
swap( l, 0, k );
while (i*2 < k)
  {
int left = i*2;
int right = l*2 + 1;
int swapidx = i;
if ( l[left] < l[right] )
  {
    if (l[i] > l[left])
      {
    swapidx = left;
      }
  }
else
  {
    if (l[i] > l[right])
      {
    swapidx = right;
      }
  }

if (swapidx == i)
  {
    // Found right place in the heap, break.
    break;
  }
swap( l, i, swapidx );
i = swapidx;
  }}

// Now reverse the list in linear time:
int s = 0; 
int e = len(l)-1;
while (e > s)
  {
    swap( l, s, e );
    s++; e--:
  }

Прочитайте элементы сверху кучи один за другим.По сути, у вас есть сортировка кучи.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top