RyukieDev
  • 关于我-AboutMe
  • 我的作品-MyApps
    • 「梦见」账本
      • 「梦见」账本(Umemi):极致的记账体验
      • 隐私协议:Privacy Policy
      • 服务协议:Terms of use
      • 外观预览:Preview
        • 赛博朋克-Cyberpunk
        • 樱-Sakura
        • 初恋-FirstLove
        • 永生-Eternal
        • 菲尼克斯-Phoenix
        • 报丧女妖-Banshee
        • 九霄-NYXL
        • Dream
        • 猕猴桃-Kiwi
        • 蜂蜜-Hachimitsu
        • DC
    • Elic-扫雷无尽天梯
    • 隐私访问记录
      • 03.如何分析iOS15隐私访问记录
      • PrivacyPolicy
      • FrameWorks
    • 醒词
      • PrivacyPolicy
      • TermsOfUse
    • 一色
      • PrivacyPolicy
    • 醒诗
      • PrivacyPolicy
    • 醒词键盘
      • PrivacyPolicy
    • 中文数字键盘
      • PrivacyPolicy
  • 独立开发
    • 产运
      • 01.没钱推广?这忘了这100美元
      • 02.在个人站点配置app-ads
      • 03.应用图标圆角
      • 04.iOS独立开发者注册公司到App备案上架.md
    • iCloud
      • 01.基于iCloud构建用户体系
      • 02.基于iCloud构建游戏内排行榜
  • Swift
    • 01.纯Swift路由方案探究
    • 02.使用Carthage替代CocoaPods
    • 03.逃逸闭包和非逃逸闭包
    • 04.向下向上取整
    • 05.Copy-on-write
    • 06.OC老项目Swift混编的一些坑
    • 07.OC项目中加入Swift混编
    • 08.Optional实质
    • 09.R-Swift-安全的资源组织方案forSwift
    • 10.Struct与Class
    • 11.Swift5新特性
    • 12.Swift性能分析
    • 13.SwiftPackage使用
    • 14.String与Substring
    • 15.Array,Set,Dictionary
    • 16.For-in跳跃遍历
    • 17.Switch元祖
    • 18.循环的标签控制
    • 19.Protocol与静态派发、动态派发
    • 20.Swift位移枚举
    • 21.Swift轻量级网络封装:SwiftyServiceProtocol(适用于混编或纯Swift项目)
    • 22.open与public
    • 23.Swift项目编译速度优化
    • 24.[译]编写高性能Swift代码-Writing High-Performance Swift Code(2022.8.25版)
    • 25.Swift编译流程
    • 26.Swift方法调度
  • SwiftUI
    • 01.Form
    • 02.Navigation
    • 03.ViewBuilder参数10个限制
    • 04.UIKit混编时Dismiss掉HostController
    • 05.如何在SwiftUI中使用ImagePicker?
    • 06.从some看Swift不透明类型
    • 07.TabView使用
    • 08.openURL
    • 09.Search
    • 10.SwifUI中使用WKWebView
  • DeepLearning
    • 基础知识
      • 01.感知机与神经网络
      • 02.线性可分
    • TensorFlow
      • 01.Anaconda
      • 02.JupyterNotebook
      • 03.安装TensorFlow
  • iOS
    • 底层
      • 01.alloc与字节对齐
      • 02.结构体内存对齐
      • 03.对象本质探究与isa
      • 04.ISA与Class
      • 05.深入探索Class的结构
      • 06.WWDC20-runtime优化
      • 07.深入探究属性
      • 08.isKindOfClass的底层实现
      • 09.slowpath和fastpath
      • 10.Class-cache_t
      • 11.源码解读objc_msgSend
      • 12.类的实现与初始化源码解读
      • 13.动态决议与消息转发
      • 14.iOS应用启动(一):dyld与main函数
      • 15.iOS应用启动(二):环境配置与runtime初始化
      • 16.iOS应用启动(三):镜像文件的读取和加载
      • 17.iOS应用启动(四):分类的加载
      • 18.关联对象源码解析
      • 19.MethodSwizzing方法交换的坑
      • 20.详解KVC
      • 21.KVO几个被忽视的细节
      • 22.KVO底层原理
      • 23.多线程原理与atomic
      • 24.任务与队列的几个面试题
      • 25.dispatch_once单例实现原理
      • 26.栅栏函数
      • 27.信号量
      • 28.锁|性能分析
      • 29.锁|@synchronized
      • 30.锁|递归锁
      • 31.锁|NSConditionLock
      • 32.关于Block你所该知道的一切
    • 内存管理
      • 01.从一个面试题看TaggedPointer
      • 02.Retain&Release
      • 03.SideTable和weak底层实现
      • 04.Timer优化
      • 05.自动释放池与Runloop
      • 06.dealloc
    • 编译器
      • 01.LLVM
    • 杂项
      • 01.堆栈的深度问题
      • 02.使用TTF字体
      • 03.为什么选VIPER
      • 04.项目路由方案
      • 05.隐藏导航栏下面的线
      • 06.源代码到IPA
      • 07.iOS重签名调研
      • 08.load与-initialize
      • 09.NSTimer与GCD
      • 10.NSURLConnection-和-NSURLSession
      • 11.Storyboard中UnwindSegue的使用
      • 12.UI调试-UIDebuggingInformationOverlay
      • 13.UIWebView和WKWebView
      • 14.UIWebView自适应高度
      • 15.weak实现原理
    • Runloop
      • 01.RunLoop
      • 02.autoreleasepool
    • Runtime
      • 01.基本操作
      • 02.实现NSCoding的自动归档和自动解档
      • 03.消息机制
      • 04.重写description打印对象信息
      • 05.MethodSwizzling的问题
    • 优化
      • 01.Apple官方资源瘦身方案ODR(一):初见
      • 02.Apple官方资源瘦身方案ODR(二):践行|换肤系统改造
      • 03.二进制重排实践
      • 04.iOS截屏防护方案
      • 05.提高编译速度
      • 06.图片格式-WebP
      • 07.App启动速度优化
      • 08.IDL自动化埋点
      • 09.渲染原理及优化
      • 10.「利用 Metrics 和 Diagnostics 提高性能」网络研讨活动
      • 11.离屏渲染
      • 12.一键搞定iOS16横竖屏切换
    • 多线程
      • 01.合适的线程数量
      • 02.死锁
      • 03.为什么用dispatch-once实现单例
      • 04.iOS多线程方案
      • 05.iOS多线程技术对比
    • Database
      • 01.数据库主键和外键
      • 02.FMDB-死锁问题
      • 03.FMDB与WCDB
      • 04.SQLite数据库修复
    • 架构
      • 01.组件化
  • 逆向
    • 01.寄存器
    • 03.iOS应用签名原理
    • 04.利用Xcode进行重签名与调试
    • 05.dylib注入
    • 06.MachO文件
    • 07.dyld
    • 08.Hook
    • 09.深入理解动态库与静态库
    • 10.通过符号表找到符号
    • 11.fishhook原理
    • 12.去符号与恢复符号
    • 13.反HOOK防护(一):基于Fishhook
    • 14.反HOOK防护(二):Monkey
    • 15.Inlinehook:Dobby
    • 16.LLDB
    • 17.虚拟内存
    • 18.Chisel工具
    • 19.DS.LLDB工具
    • 20.Cycript工具
    • 21.Cycrupt用法
    • 22.Logos
    • 23.应用砸壳
    • 24.实战人人视频破解
    • 25.解密被加密的数据库文件
  • Flutter
    • 01.初见Flutter
    • 02.Layout
    • 03.状态管理
    • 04.BottomNavigationBar
    • 05.MaterialApp
    • 06.android资源配置
    • 07.Positioned与Container嵌套无法充满容器
    • 08.Cell点击跳转
    • 09.代码规范
    • 10.通过联系人Cell看断言
    • 11.有状态Widget初始化重写&链式调用&排序
    • 12.索引条:手势及clamp函数
    • 13.ListView滑动到指定位置
    • 14.悬浮菜单列表
    • 15.Mock数据小技巧
    • 16.第三方库导入与网络数据异步请求与展示
    • 17.请求数据保留
    • 18.异步编程之Future
    • 19.Future&Microtask
    • 20.Dart异步编程:Isolates和事件循环
    • 21.Widget的生命周期
    • 22.Widget树&Render树&Element树
    • 23.Key
    • 24.调用原生相册
    • 25.iOS原生嵌入FlutterModule
  • 网络
    • 01 网络分层的优点
    • 02 网络理解
    • 03 iOS-网络安全之HTTPS
    • 04 POST和GET
    • 05 SSL-TLS四次握手
  • 直播技术
    • 01 直播技术相关
    • Socket-Little-Endian-Big-Endian
  • 知识点梳理
    • 01 面试算法题记录01
    • 02 面试题记录-C语言
    • 08 一套iOS底层试卷
    • 03 知识点梳理:iOS底层
    • 04 知识点梳理:网络
    • 05 知识点梳理:多线程
    • 06 知识点梳理:计算机基础
    • 07 知识点梳理:算法数据结构
    • 09 知识点梳理:HTML和浏览器
    • 10 知识点梳理:JavaSctipt
  • Framework
    • 01 CodeReading-01-YYModel
    • 02 RYImagePicker-iOS图片视频选择器
    • 03 RYImagesScroller-iOS高度自定义的图片轮播器
    • 04 RYPhotosBrowser
  • Issue
    • 01 使用KVC设置UIAlertAction按钮颜色的Crash
    • 02 iOS-常见崩溃分析
    • 03 UICollectionView的一些问题
  • OpenGL ES
    • 01.顶点着色器与片元着色器
  • 数据结构与算法
    • 剑指Offer-Swift
      • 03.找出数组中重复的数字
      • 04.二维数组中的查找
      • 05.替换空格
      • 06.从尾到头打印链表
      • 07.重建二叉树
      • 12.矩阵中的路径(回溯法)
      • 13.机器人的运动范围
      • 14.I.剪绳子
      • 14.II.剪绳子
      • 15.二进制中1的个数(含一个拓展问题)
      • 16.数值的整数次方
      • 18.删除链表的节点
      • 21.调整数组顺序使奇数位于偶数前面
      • 22.链表中倒数第k个节点
      • 24.反转链表
      • 25.合并两个排序的链表
      • 26.树的子结构
      • 27.二叉树的镜像
      • 28.对称的二叉树
      • 29.顺时针打印矩阵
      • 30.包含min函数的栈(容易被误导的一题)
      • 31.栈的压入、弹出序列
      • 32.I.从上到下打印二叉树
      • 32.II.从上到下打印二叉树II
      • 32.III.从上到下打印二叉树III
      • 32.从上到下花式打印二叉树
      • 33.二叉搜索树的后序遍历序列
      • 34.二叉树中和为某一值的路径
      • 35.复杂链表的复制(无Swift用例)
      • 36.二叉搜索树与双向链表
      • 37.序列化二叉树
      • 39.数组中出现次数超过一半的数字
      • 40.最小的k个数
      • 41.数据流中的中位数
      • 42.连续子数组的最大和
      • 43.1~n整数中1出现的次数
      • 44.数字序列中某一位的数字
      • 45.把数组排成最小的数
      • 46.把数字翻译成字符串
      • 47.礼物的最大价值
      • 48.最长不含重复字符的子字符串
      • 50.第一个只出现一次的字符
      • 52.两个链表的第一个公共节点
      • 53-I.在排序数组中查找数字
      • 53-II.0~n-1中缺失的数字
      • 54.二叉搜索树的第k大节点
      • 55-I.二叉树的深度
      • 55-II.平衡二叉树
      • 56-I.数组中数字出现的次数
      • 56-II.数组中数字出现的次数II
      • 57.和为s的两个数字
      • 58-I.翻转单词顺序
      • 58-II.左旋转字符串
      • 59-I.滑动窗口的最大值
      • 59-II.队列的最大值
      • 60.n个骰子的点数
      • 61.扑克牌中的顺子
      • 62.圆圈中最后剩下的数字
      • 63.股票的最大利润
      • 64.求1+2+…+n
      • 65.不用加减乘除做加法
      • 66.构建乘积数组
      • 67.把字符串转换成整数
      • 68-I.二叉搜索树的最近公共祖先
      • 68-II.二叉树的最近公共祖先
    • 技巧
      • 01.前缀和
      • 02.同余性质
      • 03.快速幂
      • 04.快速排序
      • 05.深度优先&广度优先
      • 06.冒泡排序
      • 07.摩尔投票
      • 08.优先队列
    • 数据结构
Powered by GitBook
On this page
  • 一、 什么是优先队列
  • 二、 最大堆 & 最小堆
  • 三、 插入元素
  • 四、 移除元素
  • Swift 完整实现

Was this helpful?

  1. 数据结构与算法
  2. 技巧

08.优先队列

一、 什么是优先队列

如果有这样一个数据流 1,2,3,4,5,6,7,8 我们需要按照一定的优先级找到满足条件(最大或者最小)的元素,并且每次取出最高优先级的元素后,内部元素依旧能够按照既定优先级保证最高优先级的元素在顶端。

二、 最大堆 & 最小堆

  • 堆 分为 最大堆 和 最小堆 ,其实就是 完全二叉树

    • 最大堆

      • 要求节点的元素都要大于等于其孩子

    • 最小堆

      • 要求节点元素都小于等于其左右孩子

  • 两者对左右孩子的大小关系不做任何要求

为什么用 二叉树 来实现呢?

如果使用数组复杂度会更高

三、 插入元素

如下数据流,我们按照顺序插入数据,并且每次返回最大的元素,我们就可以使用优先队列(最大堆)。

步骤1

  • 插入 1 和 5 ,如图二叉树结构

  • 叶子节点 5 > 1 ,不符合优先级规则,需要交换位置

  • 等价数组为

    • [5, 1]

步骤2

  • 插入 6

    • 每次插入都插入到当前最深层从左往右的位置,或者创建下一层

  • 6 大于父节点 5,需要调整位置

  • 交换 5 6

  • 等价数组为

    • [6, 1, 5]

步骤3

  • 插入 2

    • 这一层满了,下一层最左边

  • 2 大于父节点 1,需要调整

  • 交换 2 1

  • 等价数组为

    • [6, 2, 5, 1]

步骤4

  • 插入 7

  • 7 大于父节点 2,需要调整

  • 交换 7 2

    • 7 的父节点变为 6,还需要调整

    • 交换 7 6

  • 等价数组为

    • [7, 6, 5, 1, 2]

步骤5

  • 插入 4,父节点为 5,无需调整

  • 等价数组为

    • [7, 6, 5, 1, 2, 4]

步骤6

  • 插入 3,父节点为 5,无需调整

  • 等价数组为

    • [7, 6, 5, 1, 2, 4, 3]

步骤7

  • 插入 8

    • 下一层

  • 大于父节点 1,交换

  • 大于父节点 6,交换

  • 大于父节点 7,交换

  • 等价数组为

    • [8, 7, 5, 6, 2, 4, 3, 1]

插入代码实现

基础数据结构

public struct SwiftPriorityQueue<Element> {
    private let _hasHigherPriority: (Element, Element) -> Bool
    private let _isEqual: (Element, Element) -> Bool

    private var _elements = [Element]()

    public init(hasHigherPriority: @escaping (Element, Element) -> Bool, isEqual: @escaping (Element, Element) -> Bool) {
        _hasHigherPriority = hasHigherPriority
        _isEqual = isEqual
    }

    public func peek() -> Element? {
        return _elements.first
    }
    
    public func array() -> [Element] {
        return _elements
    }

    public var isEmpty: Bool {
        return _elements.count == 0
    }
    
    public var count: Int {
        return _elements.count
    }
}

插入逻辑

// 插入
public mutating func enqueue(_ element: Element) {
    _elements.append(element)
    bubbleToHigherPriority(_elements.count - 1)
}

// 爬升
private mutating func bubbleToHigherPriority(_ initialUnbalancedIndex: Int) {
    precondition(initialUnbalancedIndex >= 0)
    precondition(initialUnbalancedIndex < _elements.count)

    var unbalancedIndex = initialUnbalancedIndex

    while unbalancedIndex > 0 {
        let parentIndex = (unbalancedIndex - 1) / 2
        guard _hasHigherPriority(_elements[unbalancedIndex], _elements[parentIndex]) else { break }
        _elements.swapAt(unbalancedIndex, parentIndex)
        unbalancedIndex = parentIndex
    }
}

四、 移除元素

我们还以上面完成的 优先队列 数据结构为例,继续对移除元素的操作进行研究。

  • 这里我们计划移除 5 元素(当前下表为A)

  • 现将其和尾部元素交换

  • 移除尾部元素

  • 检查 A 处元素是否需要爬升

    • 是

      • 将其上浮

        • 此处 A 元素为 1,小于父节点 8,无需处理

  • 检查 A 处元素是否需要下沉

    • 是

      • 将其下降

        • 此处 A 元素为 1,小于子节点,进行下沉处理

移除与下沉逻辑实现

private mutating func removeAt(_ index: Int) {
    // 是否是最后一个元素
    let removingLast = index == _elements.count - 1
    if !removingLast {
        _elements.swapAt(index, _elements.count - 1)
    }

    _ = _elements.popLast()

    if !removingLast {
        // 检查并保持优先队列的元素
        bubbleToHigherPriority(index)
        bubbleToLowerPriority(index)
    }
}

private mutating func bubbleToLowerPriority(_ initialUnbalancedIndex: Int) {
    precondition(initialUnbalancedIndex >= 0)
    precondition(initialUnbalancedIndex < _elements.count)

    var unbalancedIndex = initialUnbalancedIndex
    while true {
        // 根据二叉树的结构,当前节点左叶子节点的下标为 unbalancedIndex * 2 + 1
        let leftChildIndex = unbalancedIndex * 2 + 1
        // 根据二叉树的结构,当前节点右叶子节点的的下标为 unbalancedIndex * 2 + 2
        let rightChildIndex = unbalancedIndex * 2 + 2

        var highestPriorityIndex = unbalancedIndex

        // 左叶子更高
        if leftChildIndex < _elements.count && _hasHigherPriority(_elements[leftChildIndex], _elements[highestPriorityIndex]) {
            highestPriorityIndex = leftChildIndex
        }

        // 右叶子更高
        if rightChildIndex < _elements.count && _hasHigherPriority(_elements[rightChildIndex], _elements[highestPriorityIndex]) {
            highestPriorityIndex = rightChildIndex
        }

        guard highestPriorityIndex != unbalancedIndex else { 
            break // 不用调整优先级
        }

        // 交换元素
        _elements.swapAt(highestPriorityIndex, unbalancedIndex)

        // 保存更高优先级的下标,继续进行对比
        unbalancedIndex = highestPriorityIndex
    }
}

Swift 完整实现

下面的优先队列实现是参考 RxSwift 中的

public struct SwiftPriorityQueue<Element> {
    private let _hasHigherPriority: (Element, Element) -> Bool
    private let _isEqual: (Element, Element) -> Bool

    private var _elements = [Element]()

    public init(hasHigherPriority: @escaping (Element, Element) -> Bool, isEqual: @escaping (Element, Element) -> Bool) {
        _hasHigherPriority = hasHigherPriority
        _isEqual = isEqual
    }

    public mutating func enqueue(_ element: Element) {
        _elements.append(element)
        bubbleToHigherPriority(_elements.count - 1)
    }

    public func peek() -> Element? {
        return _elements.first
    }
    
    public func array() -> [Element] {
        return _elements
    }

    public var isEmpty: Bool {
        return _elements.count == 0
    }
    
    public var count: Int {
        return _elements.count
    }

    public mutating func dequeue() -> Element? {
        guard let front = peek() else {
            return nil
        }

        removeAt(0)

        return front
    }

    public mutating func remove(_ element: Element) {
        for i in 0 ..< _elements.count {
            if _isEqual(_elements[i], element) {
                removeAt(i)
                return
            }
        }
    }

    private mutating func removeAt(_ index: Int) {
        let removingLast = index == _elements.count - 1
        if !removingLast {
            _elements.swapAt(index, _elements.count - 1)
        }

        _ = _elements.popLast()

        if !removingLast {
            bubbleToHigherPriority(index)
            bubbleToLowerPriority(index)
        }
    }

    private mutating func bubbleToHigherPriority(_ initialUnbalancedIndex: Int) {
        precondition(initialUnbalancedIndex >= 0)
        precondition(initialUnbalancedIndex < _elements.count)

        var unbalancedIndex = initialUnbalancedIndex

        while unbalancedIndex > 0 {
            let parentIndex = (unbalancedIndex - 1) / 2
            guard _hasHigherPriority(_elements[unbalancedIndex], _elements[parentIndex]) else { break }
            _elements.swapAt(unbalancedIndex, parentIndex)
            unbalancedIndex = parentIndex
        }
    }

    private mutating func bubbleToLowerPriority(_ initialUnbalancedIndex: Int) {
        precondition(initialUnbalancedIndex >= 0)
        precondition(initialUnbalancedIndex < _elements.count)

        var unbalancedIndex = initialUnbalancedIndex
        while true {
            let leftChildIndex = unbalancedIndex * 2 + 1
            let rightChildIndex = unbalancedIndex * 2 + 2

            var highestPriorityIndex = unbalancedIndex

            if leftChildIndex < _elements.count && _hasHigherPriority(_elements[leftChildIndex], _elements[highestPriorityIndex]) {
                highestPriorityIndex = leftChildIndex
            }

            if rightChildIndex < _elements.count && _hasHigherPriority(_elements[rightChildIndex], _elements[highestPriorityIndex]) {
                highestPriorityIndex = rightChildIndex
            }

            guard highestPriorityIndex != unbalancedIndex else { break }
            _elements.swapAt(highestPriorityIndex, unbalancedIndex)

            unbalancedIndex = highestPriorityIndex
        }
    }
}

extension SwiftPriorityQueue : CustomDebugStringConvertible {
    public var debugDescription: String {
        return _elements.debugDescription
    }
}
Previous07.摩尔投票Next数据结构

Last updated 3 years ago

Was this helpful?

1
2
3
4
5
6
7
8