为什么堆排序的空间复杂度为O（1）？
我知道快速排序和合并排序需要O(n)辅助空间用于构建的临时子数组，并且就地快速排序需要O(log n)递归堆栈帧的辅助空间。 但是对于堆排序来说，它似乎也有一个最坏情况的O(n)辅助空间来构建临时堆，即使节点只是指向实际元素的指针。
我遇到了这样的解释：
只需要O（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
这里很酷的技巧是因为堆是一个完整的二叉树，你可以使用一个普通的数组，而对于第i个项，它的父项就是项目i/2 。