什么是优先队列？
优先队列是一种能按照数据的优先级，在输出的时候能依次输出的一种数据结构。
优先队列的核心方法
*peek() 方法，返回队列中优先级最高元素。
*pop() 方法，返回队列中优先级最高元素，并将它移出队列。
*offer(Int) 方法，向队列中添加一个元素。
实现原理分析
- 优先队列内部维护一个小顶堆
- 新增元素，则将元素放到最后，并向上sift
- 删除元素，则将最后一个元素放到第一个，向下sift
一些基本概念
-
完全二叉树：二叉树的子节点从上至下，从左向右遍历，不存在空节点的二叉树就是完全二叉树
完全二叉树1
完全二叉树2
非完全二叉树 -
小顶堆：将一个数组看做一个完全二叉树的层序遍历，任意父节点的值都小于子节点，则称为小顶堆
对于数组[0,1,4,3,8,5,6,7]
小顶堆
对于数组[0,1,7,3,8,9,6,5],7的右节点比它本身小，所以不是小顶堆
非小顶堆
代码实现
class PriorityQueue {
// 初始化queue的容量为16
var queue = IntArray(16)
// queue的真实存储元素个数
var size = 0
fun offer(v: Int): Boolean {
// 如果最后一个元素超出最大容量，则扩容
if (size >= queue.size) {
grow()
}
siftUp(size++, v)
return true
}
fun peek(): Int {
return if (size <= 0) throw IndexOutOfBoundsException("没有元素") else queue[0]
}
fun poll(): Int {
if (size <= 0) throw IndexOutOfBoundsException("没有元素")
val res = queue[0]
siftDown(0, queue[--size])
return res
}
// 将v从index=i的位置向上移动，直到queue成为小顶堆
private fun siftUp(i: Int, v: Int) {
var child = i
while (child > 0) {
val parent = (child - 1).ushr(1)
if (v >= queue[parent]) break
queue[child] = queue[parent]
child = parent
}
queue[child] = v
}
// 将v从index=i的位置向下移动，直到queue成为小顶堆
private fun siftDown(i: Int, v: Int) {
var parent = i
while (parent.shl(1) + 1 < size) {
var child = parent.shl(1) + 1
if (child + 1 < size && queue[child + 1] < queue[child]) child++
if (queue[child] >= v) break
queue[parent] = queue[child]
parent = child
}
queue[parent] = v
}
// 每次容量翻倍，如果容量已经到达Int.MAX_VALUE, 则抛出异常
private fun grow() {
if (queue.size == Int.MAX_VALUE) throw OutOfMemoryError("超出最大容量")
val newCapacity = minOf(queue.size.toLong() * 2, Int.MAX_VALUE.toLong()).toInt()
queue = queue.copyOf(newCapacity)
}
}
fun main() {
PriorityQueue().apply {
offer(1)
offer(12)
offer(0)
println(peek())
offer(7)
offer(6)
println(poll())
println(poll())
println(poll())
println(peek())
println(poll())
}
}
后续
本文提供了优先队列的最简单实现，但已经包含了优先队列的最核心算法，如果有小伙伴想继续完善它，可以从下面几个方面入手：
- 1.支持泛型
- 2.支持自定义Comparator
- 3.支持Iterator
- 4.多线程安全
