Java堆&优先级队列示例讲解(下)_Java教程

Java堆&优先级队列示例讲解(下)

2022-10-09 13:57爱干饭的猿 Java教程

这篇文章主要通过示例详细为大家介绍Java中的堆以及优先级队列，文中的示例代码讲解详细，对我们了解java有一定帮助，需要的可以参考一下

1.优先级队列

1.1 概念

在很多应用中，我们通常需要按照优先级情况对待处理对象进行处理，比如首先处理优先级最高的对象，然后处理次高的对象。最简单的一个例子就是，在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。在这种情况下，我们的数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。

1.2 内部原理

优先级队列的实现方式有很多，但最常见的是使用堆来构建。

1.3 操作-入队列

过程（以大堆为例）：

1. 首先按尾插方式放入数组

2. 比较其和其双亲的值的大小，如果双亲的值大，则满足堆的性质，插入结束

3. 否则，交换其和双亲位置的值，重新进行 2 、 3 步骤

4. 直到根结点

图示：

Java堆&优先级队列示例讲解(下)

1.4 操作-出队列（优先级最高）

为了防止破坏堆的结构，删除时并不是直接将堆顶元素删除，而是用数组的最后一个元素替换堆顶元素，然后通过向下调整方式重新调整成堆

Java堆&优先级队列示例讲解(下)

1.5 借用堆实现优先级队列

1.实现一个接口

public interface IQueue<E> {
  // 入队
  void offer(E val);
  //出队
  E poll();
  //返回队首元素
  E peek();
  //判断队列是否为空
  boolean isEmpty();
}

2.堆完整代码见Java堆&优先级队列示例讲解(上)

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();
  }
}

1.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堆&优先级队列示例讲解(上)

Java堆&优先级队列示例讲解(下)