数据结构-优先级队列（Priority Queue）

◼ 优先级队列也是个队列，因此也是提供以下接口
◼ int size(); // 元素的数量
◼boolean isEmpty();//是否为空
◼void clear();// 清空
◼void enQueue(E element);//入队
◼E deQueue();// 出队
◼E front();// 获取队列的头元素

◼ 优先级队列则是按照优先级高低进行出队，比如将优先级最高的元素作为队头优先出队

优先级队列的应用场景举例
◼ 医院的夜间门诊
p队列元素是病人
p优先级是病情的严重情况、挂号时间

◼ 操作系统的多任务调度
队列元素是任务
优先级是任务类型

优先队列的底层实现

◼ 根据优先队列的特点，很容易想到：可以直接利用二叉堆作为优先队列的底层实现

package com.njf;

import java.util.Comparator;

public class PriorityQueue<E> {
    
    private BinaryHeap<E> heap;
    
    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类

package com.njf;

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 + "]";
    }
}

验证

package com.njf;

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]