为什么堆排序的空间复杂度为O(1)？
我理解快速排序和合并排序都需要为所构造的临时子数组提供O(n)辅助空间，而就地快速排序则需要递归堆栈帧的O(log n)辅助空间。但是对于堆排序，它似乎也存在构建临时堆的O(n)辅助空间的最坏情况，即使节点只是指向实际元素的指针。
我偶然发现了一个解释：
只需要O(1)额外的空间，因为堆构建在要排序的数组中。
但我认为这意味着原来的数组必须作为某种树来实现吗？如果原始数组只是一个向量，那么堆的内存似乎仍然需要分配。
回答 4
Stack Overflow用户
发布于 2014-03-06 19:27:42
数组中的数据可以重新排列到堆中。这个算法实际上非常简单，但是我不会在这里讨论。
对于堆排序，您可以安排数据，以便它在适当的位置形成堆，后面是最小的元素(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 9Stack Overflow用户
发布于 2014-03-06 19:02:16
这里最酷的窍门是，因为堆是一个完整的二叉树，所以您可以只使用一个普通数组，而对于item i，它的父项将是项i/2。
Stack Overflow用户
发布于 2019-07-18 01:13:44
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存储在数组中，数组传递给堆排序算法-堆排序(A)。数组A被解释为树和构建后的最大堆，然后用根交换最后的元素，每次减少堆的大小一次，然后在它上调用MAX(A，1)。
这是我们在数组(A)中执行的所有操作--这是作为i/p给算法的。在执行此操作时，我们不会使用任何额外的空间。所以空间复杂性- O(1)。
https://stackoverflow.com/questions/22233532
复制相似问题
腾讯云开发者
