为什么堆排序的空间复杂度为O(1)? [英] Why does heap sort have a space complexity of O(1)?

问题描述

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

I understand that both quick sort and merge sort need O(n) auxiliary space for the temporary sub-arrays that are constructed, and in-place quick sort requires O(log n) auxiliary space for the recursive stack frames. But for heap sort, it seems like it also has a worst case of O(n) auxiliary space to build the temporary heap, even if the nodes are just pointers to the actual elements.

我遇到了这个解释:

因为堆是在要排序的数组内构建的，所以仅需要O(1)额外的空间.

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

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

But I think this means the original array necessarily already had to be implemented as some sort of tree? If the original array was just a vector, it seems memory for a heap would still have to be allocated.

推荐答案

可以将数组中的数据重新安排到堆中.实际上，该算法非常简单.但是，我在这里不再赘述.

Data in an array can be rearranged into a heap, in place. The algorithm for this is actually surprisingly simple., but I won't go into it here.

对于堆排序，将数据排列成适当的位置，堆的最后是最小的元素(std::make_heap).然后，您将数组中的最后一项(堆中最小的项)与数组中的第一项(较大的数字)交换，然后将大元素向下拖移到堆中，直到其处于新的正确位置并且堆是再次是一个新的最小堆，在数组的最后一个元素中具有最小的剩余元素. (std::pop_heap)

For a heap sort, you arrange the data so that it forms a heap in place, with the smallest element at the back (std::make_heap). Then you swap the last item in the array (smallest item in the heap), with the first item in the array (a largish number), and then shuffle that large element down the heap until it's in a new proper position and the heap is again a new min heap, with the smallest remaining element in the last element of the array. (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

因此，除了交换步骤外，实际上不需要在其他任何地方存储数据.

So no data actually needs to be stored anywhere else, except maybe during the swap step.

为了可视化，这是以标准格式显示的原始堆

For visualization, here's that original heap shown in a standard form

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

这篇关于为什么堆排序的空间复杂度为O(1)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！