当前位置：首页 > news >正文

【数据结构与算法】第十一篇：优先级队列

news 来源：原创 2024/5/14 2:03:52

知识星球

一.优先级对列的引用背景
二.优先级队列接口设计
三.二叉堆实现优先级对列
四.辅助类和测试代码

一.优先级对列的引用背景

优先级队列其实就是一个对列，在接口设计与大部分运用上都是一致的，但是普通队列与优先级队列不同的是：普通的队列都是遵循 FIFO 原则，也就是先进先出原则，优先级队列则改变了这个原则，优先级队列是根据一个准则设计优先级，优先级高的先进行出队，而优先级低的则后进行出队。

比如下面这两个实例：

实例1🥳🥳：
◼ 医院的夜间门诊
1.队列元素是病人
2.优先级是病情的严重情况、挂号时间（由于夜间医生数量有限，所以不是单纯根据先来先进行检测的原则的，而是考虑到病情的严重程度）

实例2😎😎
◼ 操作系统的多任务调度
1.队列元素是任务
2.优先级是任务类型

二.优先级队列接口设计

由于优先级队列也是对列，所以接口设计基本与普通队列相同

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

在这里插入图片描述

三.二叉堆实现优先级对列

既然优先级对列是根据优先级大小进行出队的操作的，我们很容易想到上节课提到的二叉堆中的最大堆，如果我们自己设计优先级，将优先级最高的放在最大堆的堆顶，便能很好的解决这个问题。

import java.util.Comparator;

import com.mj.heap.BinaryHeap;

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

	}

}