sorting - 为什么堆排序的空间复杂度为O(1)？

Question

我知道快速排序和合并排序都需要O(n)辅助空间来构建临时子数组，而就地快速排序也需要O(log n)辅助空间来递归堆栈帧。但是对于堆排序，即使节点只是指向实际元素的指针，似乎也最糟糕的情况是使用O(n)辅助空间来构建临时堆。

我碰到了这个explanation:

Only O(1) additional space is required because the heap is built inside the array to be sorted.

但是我认为这意味着原始数组一定已经必须实现为某种树形结构吗？如果原始数组只是一个 vector ，则似乎仍必须分配堆的内存。

Answer 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