当前位置: 首页>后端>正文

PriorityQueue原理与最简实现[kotlin]

什么是优先队列?

优先队列是一种能按照数据的优先级,在输出的时候能依次输出的一种数据结构。

优先队列的核心方法

*peek() 方法,返回队列中优先级最高元素。
*pop() 方法,返回队列中优先级最高元素,并将它移出队列。
*offer(Int) 方法,向队列中添加一个元素。

实现原理分析

  • 优先队列内部维护一个小顶堆
  • 新增元素,则将元素放到最后,并向上sift
  • 删除元素,则将最后一个元素放到第一个,向下sift

一些基本概念

  • 完全二叉树: 二叉树的子节点从上至下,从左向右遍历,不存在空节点的二叉树就是完全二叉树

    PriorityQueue原理与最简实现[kotlin],第1张
    完全二叉树1

    PriorityQueue原理与最简实现[kotlin],第2张
    完全二叉树2

    PriorityQueue原理与最简实现[kotlin],第3张
    非完全二叉树
  • 小顶堆: 将一个数组看做一个完全二叉树的层序遍历,任意父节点的值都小于子节点,则称为小顶堆
    对于数组[0,1,4,3,8,5,6,7]

    PriorityQueue原理与最简实现[kotlin],第4张
    小顶堆

    对于数组[0,1,7,3,8,9,6,5],7的右节点比它本身小,所以不是小顶堆
    PriorityQueue原理与最简实现[kotlin],第5张
    非小顶堆

代码实现

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.多线程安全

java版点这里


https://www.xamrdz.com/backend/3mh1945779.html

相关文章: