数据结构与算法笔记目录： 《恋上数据结构》 笔记目录

想加深 Java 基础推荐看这个： Java 强化笔记目录

我的《恋上数据结构》源码（第1季 + 第2季）：https://github.com/szluyu99/Data_Structure_Note

优先级队列简介

优先级队列也是个队列，因此也提供以下接口：

public interface Queue<E> {
    int size();    // 元素的数量
    boolean isEmpty();    // 是否为空
    void enQueue(E element);    // 入队
    E deQueue();    // 出队
    E front();    // 获取队列的头元素
    void clear();    // 清空
}

队列与优先级队列对比：

• 普通的队列是 FIFO 原则，也就是先进先出
• 优先级队列则是按照优先级高低进行出队，
  比如将优先级最高的元素作为队头优先出队。

优先级队列应用场景：

• 医院的夜间门诊
  队列元素是病人
  优先级是病情的严重情况、挂号时间
• 操作系统的多任务调度

队列元素是任务
优先级是任务类型

优先队列的底层实现

• 利用二叉堆作为优先队列的底层实现
• 可以通过 Comparator 或 Comparable 去自定义优先级高低

二叉堆实现优先级队列源码

利用二叉堆实现优先级队列。

/**
 * 二叉堆实现优先级队列
 * @author yusael
 */
public class PriorityQueue<E> {
    private BinaryHeap<E> heap;
    
    // 通过 comparator 自定义优先级高低
    public PriorityQueue(Comparator<E> comparator) {
        heap = new BinaryHeap<>(comparator);
    }
    
    public PriorityQueue() {
        this(null);
    }
    
    public int size() {
        return heap.size();
    }

    public boolean isEmpty() {
        return heap.isEmpty();
    }
    
    public void clear() {
        heap.clear();
    }

    public void enQueue(E element) {
        heap.add(element);
    }

    public E deQueue() {
        return heap.remove();
    }

    public E front() {
        return heap.get();
    }
}

测试代码

Person.java

public class Person implements Comparable<Person> {
    private String name;
    private int boneBreak;
    public Person(String name, int boneBreak) {
        this.name = name;
        this.boneBreak = boneBreak;
    }
    
    @Override
    public int compareTo(Person person) {
        return this.boneBreak - person.boneBreak;
    }

    @Override
    public String toString() {
        return "Person [name=" + name + ", boneBreak=" + boneBreak + "]";
    }
}

Main.java

 public class Main {
    public static void main(String[] args) {
        PriorityQueue<Person> queue = new PriorityQueue<>();
        queue.enQueue(new Person("Jack", 2));
        queue.enQueue(new Person("Rose", 10));
        queue.enQueue(new Person("Jake", 5));
        queue.enQueue(new Person("James", 15));
        
        while (!queue.isEmpty()) {
            System.out.println(queue.deQueue());
        }
    }
}

Person [name=James, boneBreak=15]
Person [name=Rose, boneBreak=10]
Person [name=Jake, boneBreak=5]
Person [name=Jack, boneBreak=2]