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

Question

Куча представляет собой список, в котором применяется следующее:

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

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

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

Answer 1

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

Если вы чувствуете себя храбрым, вы можете пойти на реализацию smoothsort, который быстрее, чем у heapsort для почти отсортированных данных.

Answer 2

Считывание предметов с верхней части кучи по одному. В принципе, у вас есть куча сортировки.

Answer 3

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

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

Answer 4

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

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

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

Answer 5

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

Answer 6

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

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

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

Сложность времени 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--: 
    }