堆排序空间复杂性
我正在阅读Skiena的算法设计手册书，特别是关于堆排序的章节。 他表示
这是一种就地排序，意味着它不会在包含要排序的元素的数组上使用额外的内存
本书中的算法如下所示：
heapsort(item_type s[], int n)
{
int i;
priority_queue q;
make_heap(&q, s, n);
for (i=0; i<n; i++)
s[i] = extract_min(&q);
}
对我来说，它看起来像除了输入数组s的项目，我们正在创建的一个堆数据结构priority_queue变量。 这是不是意味着所需的空间复杂度是O（n），并且需要大约两倍的内存，而不是“没有额外的内存”？
上面描述的heapsort的实现确实看起来不像它在恒定空间中工作，正是你担心的原因。
但是，这并不意味着不可能在O（1）辅助空间中实现堆排序。 通常情况下，heapsort的实现会重新排列数组中的元素以隐式存储二进制最大堆。 关于最大堆的一个很好的细节是，从最大堆出队的方式是将根节点（第一个数组元素）与最右边的叶（堆中的最后一个元素）交换并且然后向下滚动该元素。 这意味着您可以通过交换第一个数组元素与数组中最右侧的槽未被填充的位置，然后将交换后的元素冒泡到位来反复从最大堆中出列。 这只需要O（1）辅助存储空间，并且是实施堆排序的典型方式。
如果你很好奇，我的个人网站上有自己的heapsort实现，它展示了如何做到这一点。
链接地址: http://www.djcxy.com/p/40051.html