网站几个关键词,网站备案为什么要关闭,查看网站空间,网上购物商城介绍前言
上周在面试时#xff0c;偶然一个算法用到了优先队列思想。我只懂效果不懂实现#xff0c;当时感觉和堆排序的思想差不多。今天深入源码#xff0c;自己又实现一遍加深印象。
源码有什么
具有Queue和Collection集合和Queue队列的性质可以保证每次取出的元素都是最值…前言
上周在面试时偶然一个算法用到了优先队列思想。我只懂效果不懂实现当时感觉和堆排序的思想差不多。今天深入源码自己又实现一遍加深印象。
源码有什么
具有Queue和Collection集合和Queue队列的性质可以保证每次取出的元素都是最值默认是最小可以自己设置内部采用推排序思想上浮siftUp和下沉siftDown存储采用可变数组和ArrayList一样默认大小是11刚开始每次*22后面每次加一半sizesize2
如何实现一个优先队列
队列最基本的offerpeekpoll集合最基本的isEmptytoStringsize供内部使用的siftUpsiftDowngrow
代码实现
个人有写算法加注释的习惯看不懂私聊
import java.util.*
import kotlin.math.maxfun main() {val queue MyPriorityQueue().apply {repeat(10) {offer(Random().nextInt(100))}}while (queue.isNotEmpty()) {println(queue.poll())}
}class MyPriorityQueue {// 保存元素方便实现泛型默认大小是11private var array Array(11) { 0 }// 当前数目private var size 0// 增fun offer(value: Int) {if (size array.size) {grow(size 1)}array[size] valuesiftUp(size - 1, value)}// 看队头fun peek(): Int {return if (size 0) -1 else array[0]}// 取对头fun poll(): Int {if (size 0) {return -1}val result array[0]array[0] array[size - 1]size--siftDown(0, array[0])return result}// 没有size方法fun size() size// 没有isEmpty方法fun isEmpty() size 0fun isNotEmpty() size 0// 上浮默认最小在上面private fun siftUp(index: Int, value: Int) {// 在上面选个大的和当前交换没有退出var i indexwhile (i 0) {val parent (i - 1) / 2if (array[parent] value) {break}array[i] array[parent]i parent}array[i] value}// 下沉默认最大在下面private fun siftDown(index: Int, value: Int) {// 选出子节点最小的一个没有则退出var i index// 当至少存在左子节点时while (i * 2 1 size) {// 找出最小的子节点下标val minChild if (i * 2 2 size || array[i * 2 1] array[i * 2 2]) i * 2 1 else i * 2 2// 如果最小的还是比父节点大退出if (array[minChild] value) {break}array[i] array[minChild]i minChild}array[i] value}// 扩容机制小于64*22大于2private fun grow(minCapacity: Int) {var newCapacity array.size if (array.size 64) array.size 2 else array.size / 2// 在一次添加大量元素才可能用到newCapacity max(newCapacity, minCapacity)array Arrays.copyOf(array, newCapacity)}// 重写toString方法override fun toString() StringBuilder().apply {append([)for (i in 0 until size) {append(if (i 0) array[i] else ${array[i]})}append(])}.toString()
}
