使用Kotlin实现Java的优先队列PriorityQueue

这篇具有很好参考价值的文章主要介绍了使用Kotlin实现Java的优先队列PriorityQueue。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

上周在面试时,偶然一个算法用到了优先队列思想。我只懂效果不懂实现,当时感觉和堆排序的思想差不多。今天深入源码,自己又实现一遍加深印象。

源码有什么

  1. 具有Queue和Collection集合和Queue队列的性质
  2. 可以保证每次取出的元素都是最值(默认是最小,可以自己设置)
  3. 内部采用推排序思想,上浮siftUp和下沉siftDown
  4. 存储采用可变数组(和ArrayList一样),默认大小是11,刚开始每次*2+2,后面每次加一半(size+=size>>2)

如何实现一个优先队列

  1. 队列最基本的offer,peek,poll
  2. 集合最基本的isEmpty,toString,size
  3. 供内部使用的siftUp,siftDown,grow

代码实现

个人有写算法加注释的习惯,看不懂私聊文章来源地址https://www.toymoban.com/news/detail-665486.html

import java.util.*
import kotlin.math.max

fun main() {
    val queue = MyPriorityQueue().apply {
        repeat(10) {
            offer(Random().nextInt(100))
        }
    }
    while (queue.isNotEmpty()) {
        println(queue.poll())
    }
}

class MyPriorityQueue {
    // 保存元素,方便实现泛型,默认大小是11
    private var array = Array(11) { 0 }

    // 当前数目
    private var size = 0

    // 增
    fun offer(value: Int) {
        if (size == array.size) {
            grow(size + 1)
        }
        array[size++] = value
        siftUp(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 == 0

    fun isNotEmpty() = size > 0

    // 上浮,默认最小在上面
    private fun siftUp(index: Int, value: Int) {
        // 在上面选个大的和当前交换,没有退出
        var i = index
        while (i > 0) {
            val parent = (i - 1) / 2
            if (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,*2+2,大于,+>>2
    private 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()
}

到了这里,关于使用Kotlin实现Java的优先队列PriorityQueue的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构 之 优先级队列(堆) (PriorityQueue)

    🎉欢迎大家观看AUGENSTERN_dc的文章(o゜▽゜)o☆✨✨ 🎉感谢各位读者在百忙之中抽出时间来垂阅我的文章,我会尽我所能向的大家分享我的知识和经验📖 🎉希望我们在一篇篇的文章中能够共同进步!!! 🌈个人主页:AUGENSTERN_dc 🔥个人专栏:C语言 | Java | 数据结构 ⭐个人

    2024年03月20日
    浏览(49)
  • 【JavaDS】优先级队列(PriorityQueue),堆,Top-k问题

    ✨ 博客主页: 心荣~ ✨ 系列专栏: 【Java实现数据结构】 ✨ 一句短话: 难在坚持,贵在坚持,成在坚持! 如果有一个 关键码的集合K = {k0,k1, k2,…,kn-1} ,把它的所有元素 按完全二叉树的顺序存储方式存储 在一 个一维数组中 ,并满足: Ki = K2i+1 且 Ki= K2i+2 (Ki = K2i+1 且 Ki = K2i

    2024年02月01日
    浏览(46)
  • 使用Kotlin优化Java开发

    Kotlin是一种静态类型的编程语言,运行于Java虚拟机(JVM)、Android和WebAssembly。由JetBrains开发,其设计的主要目的是支持函数式编程和面向对象编程特性。Kotlin可以与Java互相调用,使得它对于现有Java生态系统中的开发人员来说非常有吸引力。与Java相比,它提供了更多的功能和语

    2024年02月09日
    浏览(43)
  • kotlin实现java的单例模式

    Kotlin的5种单例模式

    2024年02月10日
    浏览(37)
  • 【JoAPP】Android WebView与H5交互实现(JAVA+KOTLIN)

           最近一个应急平台的项目移动端开发,原计划用UNI-APP实现,客户想着要集成语音、视频通话功能,基于经验判断需要买一套IM原生移动端框架去结合H5整合比较合适,没想到最后客户不想采购,而且语音视频通话功能也迟迟未能完全确认,H5部分所开发的业务功能已经

    2024年02月03日
    浏览(46)
  • Kotlin:使用flow实现倒计时功能

    一、效果图 二、ExtendContext.kt 文件代码 注意:创建ExtendContext.kt选择file 使用kotlin扩展方法的特性创建countDown扩展方法,避免多个地方使用倒计时重复创建countDown方法 三、MainActivity.kt代码 四、build.gradle.kts代码

    2024年02月19日
    浏览(39)
  • 【堆的认识及其优先级队列】java代码实现,保姆级教程学习堆和优先级队列

    前言: 大家好,我是 良辰 丫💞💞⛽,我们又见面了,前面我们讲了用链表实现的二叉树,今天我们来接触 堆 的概念,堆是一种特殊的二叉树,只不过咱们的对底层原理是数组,堆也是我们在做题中经常见到的,那么,接下来我们就慢慢的去接触堆, 认识堆,理解堆,掌

    2024年02月02日
    浏览(53)
  • 【Kotlin】Kotlin 与 Java 互操作 ① ( 变量可空性 | Kotlin 类型映射 | Kotlin 访问私有属性 | Java 调用 Kotlin 函数 )

    在 Java 语言 中 , 任何 引用类型变量 都可以为 空 null ; Java 中 八种 基本数据类型 变量 的 默认值 为 0 或 false ; 但是在 Kotlin 语言 中 , 所有的 变量 都是引用类型变量 , 没有基本数据类型 , 默认情况下 所有的变量 都为 非空类型 ; 下面分别定义一个 Java 类 和 Kotlin 脚本 , 在 K

    2024年02月02日
    浏览(64)
  • 【Kotlin】使用 ProgressBar 的样式属性来实现圆形进度条,进度使用gradient渐变效果

    Android ProgressBar 默认提供了水平和圆形两种进度条,水平进度条通过 ProgressBar 控件实现,而圆形进度条通过 ProgressDialog 控件实现。如果想要将 ProgressBar 控件设置为圆形进度条,可以使用 ProgressBar 的样式属性来实现。 首先,在布局文件中添加一个 ProgressBar 控件,并设置其样

    2024年02月10日
    浏览(44)
  • Java 数据结构篇-用数组、堆实现优先级队列

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍    文章目录         1.0 优先级队列说明         2.0 用数组实现优先级队列         3.0 无序数组实现优先级队列         3.1 无序数组实现优先级队列 - 入队列 offer(E value)         3.2 无序数组实现优先

    2024年02月04日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包