Почему сортировка кучи имеет пространственную сложность O (1)?

Я понимаю, что для быстрой сортировки и сортировки слияния требуется O(n) вспомогательное пространство для созданных временных подмассивов, а для быстрой сортировки на месте требуется O(log n) вспомогательное пространство для рекурсивных кадров стека. Но для сортировки кучи, похоже, имеет худший случай вспомогательного пространства O(n) для создания временной кучи, даже если узлы просто указывают на фактические элементы.

Я наткнулся на это объяснение:

Только O (1) требуется дополнительное пространство, потому что куча встроена в массив, который нужно отсортировать.

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

Ответ 1

Данные в массиве могут быть перегруппированы в кучу, на месте. Алгоритм для этого на самом деле удивительно прост., Но я не буду вдаваться в него здесь.

Для сортировки кучи вы упорядочиваете данные так, чтобы они формировали кучу на месте, с наименьшим элементом на обратной стороне (std::make_heap). Затем вы меняете последний элемент в массиве (самый маленький элемент в куче), с первым элементом в массиве (довольно большим числом), а затем перетасовываете этот большой элемент вниз по куче, пока он не станет в новом правильном положении, а куча снова новую минимальную кучу, с наименьшим оставшимся элементом в последнем элементе массива. (std::pop_heap)

data:         1 4 7 2 5 8 9 3 6 0

make_heap:   [8 7 9 3 4 5 6 2 1 0] <- this is a min-heap, smallest on right

pop_heap(1): [0 7 9 3 4 5 6 2 1 8] <- swap first and last elements
pop_heap(2): 0 [7 9 3 4 8 6 2 5 1] <- shuffle the 8 down the heap

pop_heap(1): 0 1 [9 3 4 8 6 2 5 7] <- swap first and last elements
pop_heap(2): 0 1 [9 7 4 8 6 3 5 2] <- shuffle the 7 down the heap

etc

Таким образом, данные на самом деле не должны храниться где-либо еще, кроме, возможно, во время этапа свопинга.

Для визуализации здесь оригинальная куча, показанная в стандартной форме

make_heap 
           0
     2           1
  3     4     5     6
               8   7 9
pop_heap
           8                           1                           1
     2           1               2           8               2           5 
  3     4     5     6    ->   3     4     5     6    ->   3     4     8     6 
                   7 9                         7 9                         7 9

Ответ 2

Прохладный трюк здесь, так как куча - полное двоичное дерево, вы можете просто использовать простой массив, а для элемента я его родителем будет элемент i/2.

Ответ 3

HEAP-SORT(A)
{
BUILD-MAX-HEAP(A)
if(i= A.length down to 2)
    exchange A[i] with A[1]
    A.heapSize = A.heapSize-1
    MAX-HEAPIFY(A,1)

}

i/p хранится в массиве, который передается в сортировку кучи algorithm- HEAP-SORT (A). Массив A интерпретируется как дерево и после BUILD-MAX-HEAP из него и замены последнего элемента корневым элементом и уменьшения размера кучи каждый раз на единицу, а затем вызова MAX-HEAPIFY (A, 1) для него.

это все операции, которые мы выполняем только внутри этого массива (A), который задается как i/p для алгоритма. мы не используем никакого дополнительного пространства при выполнении этой операции. Таким образом, сложность пространства - O (1).

Ответ 4

Сортировка кучи - это алгоритм на месте; это не требует дополнительного места. Элементы реорганизуются во время каждой рекурсии только внутри одного массива.

Это дает представление о том, что двоичная куча или дерево формируется, но в реальном сценарии никакое дерево или куча не формируется.