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

Question

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

我遇到了这个解释:

只需要额外的O(1)空间,因为堆是在要排序的数组中构建的.

但我认为这意味着原始数组必然已经被实现为某种树？如果原始数组只是一个向量,那么似乎仍然需要分配堆的内存.

Answer 1

可以将数组中的数据重新排列到堆中.这个算法实际上非常简单.但我不会在这里讨论它.

对于堆排序,您可以排列数据,使其在适当的位置形成堆,其中最小的元素位于back(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

Answer 2

这里很酷的技巧是，由于堆是一个完整的二叉树，您可以只使用一个普通数组，对于项目 i，它的父级将是 item i/2。