堆排序空间复杂度

Question

我正在阅读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)，并且需要大约两倍的内存，而不是“没有额外的内存”吗？

Answer 1

上面描述的堆排序的实现看起来不像在恒定空间中工作，这正是您担心的原因。

但是，这并不意味着不可能在O(1)辅助空间中实现堆排序。通常，堆排序的实现将重新排序数组中的元素，以隐式存储二进制最大堆。关于max堆的一个巧妙的细节是，从max堆中排出队列的方法是将根节点(第一个数组元素)与最右边的叶(堆中的最后一个元素)交换，然后向下气泡该元素。这意味着您可以通过将第一个数组元素与尚未填充的数组中最右边的槽交换，从而重复地从max堆中排出队列，然后将交换的元素冒泡到适当的位置。这只需要O(1)辅助存储空间，是实现堆排序的典型方式。

如果你好奇的话，我在我的个人网站上有我自己的堆排序实现，它展示了如何做到这一点。