当前位置：首页 > ds >正文

Java是实现大根堆

ds 2025/7/16 4:17:21

什么是大根堆？

大根堆是一种特殊的完全二叉树，主要用于快速访问和操作集合中的最大值，是堆的一种形式；

什么是完全二叉树？

完全二叉树是指一棵二叉树中，除了最后一层外，其余层的节点数都达到最大值（即满的），并且最后一层的节点都连续地靠左排列，注意如果最底层的叶子节点不满的情况下，是靠左排列才可以是完全二叉树。

下面两个是完全二叉树：

这个就不是一个完全二叉树，因为最底层的叶子节点没有连续靠左排列；

在完全二叉树的基础上，满足：

每个节点的值都大于或等于其子节点的值。也就是说，对于任意节点 i，都必须大于其子节点的值，最终也就是堆的根节点（即树的顶部）始终是整个堆的最大值；

大根堆最主要的性质：

根节点永远是最大值

下面就是一个大根堆的示例：

什么是小根堆？

与大根堆相比，小根堆（Min Heap）是相反的，每个节点的值小于或等于其子节点的值，根节点是最小值，其余相同。

Java提供了什么方式快速的实现大根堆和小根堆？

大根堆和小根堆都可以使用PriorityQueue（优先队列）实现；

小根堆的创建

Java中PriorityQueue默认是小根堆的方式，也就是直接创建一个PriorityQueue对象就好了，相当于创建一个小根堆；

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(10);  // 插入元素
minHeap.offer(30);
minHeap.offer(20);System.out.println(minHeap.peek()); // 10（获取堆顶最小值）
System.out.println(minHeap.poll()); // 10（移除堆顶）
System.out.println(minHeap.poll()); // 20（下一个最小值）

大根堆的创建

大根堆的创建需要通过自定义比较器 (Comparator.reverseOrder())实现

// 使用比较器反转顺序
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(10); 
maxHeap.offer(30); 
maxHeap.offer(20);System.out.println(maxHeap.peek()); // 30（获取堆顶最大值）
System.out.println(maxHeap.poll()); // 30（移除堆顶）
System.out.println(maxHeap.poll()); // 20（下一个最大值）

自定义对象实现堆

我知道的有两种方式：

类实现 `Comparable` 接口：

class Person implements Comparable<Person> {int age;// 构造函数、getter/setter...@Overridepublic int compareTo(Person other) {return Integer.compare(this.age, other.age); // 默认升序（小根堆）}
}// 使用
PriorityQueue<Person> minHeap = new PriorityQueue<>();

动态传入比较器

// 大根堆（按年龄降序）
PriorityQueue<Person> maxHeap = new PriorityQueue<>((p1, p2) -> Integer.compare(p2.getAge(), p1.getAge())
);// 等价于
PriorityQueue<Person> maxHeap = new PriorityQueue<>(Comparator.comparingInt(Person::getAge).reversed());