【恋上数据结构与算法一】(十五)优先级队列

优先级队列(Priority Queue)

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

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

◼普通的队列是 FIFO 原则，也就是先进先出

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

优先级队列的应用场景举例

◼ 医院的夜间门诊
队列元素是病人
优先级是病情的严重情况、挂号时间

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

优先队列的底层实现

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

◼可以通过Comparator 或Comparable 去自定义优先级高低

优先级队列

package alangeit.queue;

// 优先级队列

import java.util.Comparator;
import alangeit.heap.BinaryHeap;

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模型

package alangeit;

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;// boneBreak大的优先级高
    }

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

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]

作业

数组中的第K个最大元素
根据字符出现频率排序
数据流中的第K大元素
有序矩阵中第K小的元素
前K个高频元素
前K个高频单词
查找和最小的K对数字
合并K个排序链表