java - minheap 按什么顺序排序？

Question

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

1. minHeap 用于降序排序。
2. maxHeap 用于升序排序。

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

标签： javaalgorithmsortingdata-structuresheap

Answer 1

博客中的解释是正确的

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

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

在每次迭代中，对于ifrom n-1to 0， arr[0] 与 the 交换，arr[i] 并且堆再次被堆化，其大小比前一次迭代小 1。