minheap 按什么顺序排序？

Question

我一直在阅读有关 minHeap 和 maxHeap 的各种定义。我偶然发现了这样的陈述：

minHeap用于降序排序
maxHeap用于升序排序

摘自 https://www.geeksforgeeks.org/heap-sort-for-decreasing-order-using-min-heap/ 中 "Note" 的陈述。但是当我使用 Java 中的 PriorityQueue<Integer> 和默认比较器实现 minHeap 并对其进行 poll() 时，我得到了最小元素。这是为什么？感谢任何试图提供帮助的人:)。

Answer 1

博客中的解释是正确的

细看heapSort()函数，巧妙地利用了最小堆。数组的最小元素被最后一个元素替换，堆的大小再次减少 1 到 heapify()。

arr[0] -> 表示最小的元素。

在每次迭代中，对于从 n-1 到 0 的 i，arr[0] 与 arr[i] 交换并且堆再次堆化，大小为比上一次迭代小 1。

Answer 2

基本思想是就地排序。每次算法从堆中轮询时，堆大小都会缩小一个。所以数组末尾的一个地方不再是堆的一部分。在此索引中放置第 n 个最小的数字。

// One by one extract an element from heap 
for (int i = n - 1; i >= 0; i--) { 
    // Move current root to end 
    swap(arr[0], arr[i]); 

    // call max heapify on the reduced heap 
    heapify(arr, i, 0); 
}

所以为什么你的算法使用 PriorityQueue 的行为如此奇怪的解释是你使用一个单独的数组来输出。您可以切换到最大堆并坚持您的方法，或者反向填充输出数组。两者应该产生相同的行为。

Answer 3

min-heap 和 max-heap 不排序。您可以使用 min-heap 或 max-heap 进行排序，但在标准使用中，堆不会排序。相反，他们按照所谓的堆顺序排列。这种安排使得添加项目和删除最小（或最大）项目变得高效，同时保持数据的正确顺序。

例如，这是 min-heap 的插图：

                1
            3       2
          4   7   6   5

遵循没有 child 大于其 parent 的规则。该堆的结果数组表示形式是 [1,3,2,4,7,6,5]。请注意，还有其他具有相同编号的有效堆。例如，以下两个也是有效的：

                1                          1
            2       5                  2       3
          4   3   6   7              4   5   6   7

对应的数组表示为[1,2,5,4,3,6,7]和[1,2,3,4,5,6,7]。

Max-heap 类似，只是规则是 child 不能大于它的 parent。

Wikipedia article on binary heap 很好地解释了这一点。

现在，当您谈论使用堆排序时，您构建一个堆，然后反复交换根元素与数组中的最后一个元素，减少计数，然后 re-heapify。因此，您从后到前构建排序数组。如果您使用 min-heap，则根（最小值）将位于数组的末尾。

所以如果你想用堆排序降序排序，你可以使用min-heap。

minheap 按什么顺序排序？

In what order does a minheap sort?

java

sorting

algorithm

heap

data-structures