目录
1.优先级队列
1.1 概念
在很多应用中，我们通常需要按照优先级情况对待处理对象进行处理，比如首先处理优先级最高的对象，然后处理次高的对象。最简单的一个例子就是，在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。在这种情况下，我们的数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。
1.2 内部原理
优先级队列的实现方式有很多，但最常见的是使用堆来构建。
1.3 操作-入队列
过程（以大堆为例）：
1. 首先按尾插方式放入数组
2. 比较其和其双亲的值的大小，如果双亲的值大，则满足堆的性质，插入结束
3. 否则，交换其和双亲位置的值，重新进行 2、3 步骤
4. 直到根结点
图示：
编辑
3.4 操作-出队列（优先级最高）
为了防止破坏堆的结构，删除时并不是直接将堆顶元素删除，而是用数组的最后一个元素替换堆顶元素，然后通过向下调整方式重新调整成堆
编辑
3.5 借用堆实现优先级队列
1.实现一个接口
public interface IQueue<E> { // 入队 void offer(E val); //出队 E poll(); //返回队首元素 E peek(); //判断队列是否为空 boolean isEmpty(); }
2.堆完整代码见上节
3.优先级队列
/** * 基于最大堆的优先级队列,值越大优先级越高 * 队首元素就是优先级最大的元素(值最大) */ import stack_queue.queue.IQueue; public class PriorityQueue implements IQueue<Integer> { MaxHeap heap = new MaxHeap(); public PriorityQueue(){ heap = new MaxHeap(); } @Override public void offer(Integer val) { heap.add(val); } @Override public Integer poll() { return heap.extractMax(); } @Override public Integer peek() { return heap.peekMax(); } @Override public boolean isEmpty() { return heap.isEmpty(); } }
3.6 测试
import java.util.Comparator; import java.util.PriorityQueue; import java.util.Queue; public class PriorityQueueTest { public static void main(String[] args) { // 通过构造方法传入比较器 // 默认是最小堆，"值"(比较器compare的返回值)越小，优先级就越高 // 当传入一个降序的比较器时,值(比较器compare的返回值，值越大，返回负数) // Queue<Student> queue = new PriorityQueue<>(new StudentComDesc()); // Queue<Student> queue = new PriorityQueue<>(new Comparator<Student>() { // @Override // public int compare(Student o1, Student o2) { // return o2.getAge() - o1.getAge(); // } // }); Queue<Student> queue = new PriorityQueue<>(new StudentCom()); Student stu1 = new Student(18,"雷昊"); Student stu2 = new Student(20,"张超"); Student stu3 = new Student(16,"钺浦"); queue.offer(stu1); queue.offer(stu2); queue.offer(stu3); while (!queue.isEmpty()){ System.out.println(queue.poll()); } } } //升序（最小堆） class StudentCom implements Comparator<Student> { @Override public int compare(Student o1, Student o2) { return o1.getAge() - o2.getAge(); } } //降序（最大堆） class StudentComDesc implements Comparator<Student> { @Override public int compare(Student o1, Student o2) { return o2.getAge() - o1.getAge(); } } class Student{ private int age; private String name; public int getAge() { return age; } public Student(int age, String name) { this.age = age; this.name = name; } @Override public String toString() { return "Student{" + "age=" + age + ", name='" + name + '\'' + '}'; } }
结果如下：《Java 堆 & 优先级队列（上）》
编辑
