java - 堆排序和通过最小堆排序

Question

我知道如何使用堆排序和最大堆属性对数组进行就地排序。
但我想不出如何使用 min-heap 属性对其进行排序。

我可以使用临时中间数组使用最小堆对其进行排序，例如

public static int[] heapSort2(int[] array){
     buildMinHeap(array);
     int [] temp = new int[array.length];
     for(int i = 0; i < array.length; i++ ){
      temp[i] = extractMin(array);
      } 
   return temp;//returns array input sorted
}

但我想不出不使用 temp 的方法。有可能吗，还是最小堆只适用于优先级队列？

Answer 1

使用最小堆就地排序与使用最大堆排序是对称的。

假设您按升序排序，并且您有一个最大堆数组，根始终在第一个元素(索引 1)中，并且您通过将根移出到最后一片叶子(这是最右边还没有排序的元素)，使这个叶子成为新的根并将其沉入堆中。

然后您使用最小堆数组按升序排序，方法是让根始终在最后一个元素(索引 N)，然后通过将根移出到该位置来执行一个排序步骤最后一片叶子(最左边尚未排序的元素)，使这片叶子成为新的根并将其放入堆中。

在这样的堆中，获取父、左、右 child 索引的方程是不同的。在前一种情况下，假设索引 1->N，方程式为:

parent(i) = floor(i / 2)
leftchild(i) = 2 * i
rightchild(i) = 2 * i + 1

在后一种反向最小堆情况下，方程是通过反转上述输入和输出处的索引获得的:

parent(i) = N + 1 - floor((N + 1 - i) / 2)
leftchild(i) = N + 1 - (2 * (N + 1 - i))
rightchild(i) = N + 1 - (2 * (N + 1 - i) + 1)

你可以看到，与前者相比，后者的方程式看起来很难看(但有可能简化它们)。因此，按升序排序时，最好只使用最大堆，而不是最小堆。 仅当您想按降序排序时才使用最小堆 - 方向与按升序排序时使用最大堆的方向相同(根在第一个元素上)。