我的编程空间,编程开发者的网络收藏夹
学习永远不晚

GO语言怎么实现支持O(log(n))随机删除元素的堆

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

GO语言怎么实现支持O(log(n))随机删除元素的堆

今天小编给大家分享一下GO语言怎么实现支持O(log(n))随机删除元素的堆的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。

    背景

    堆是一种非常常用的数据结构,它能够支持在O(1)的时间复杂度获取到最大值(或最小值),因此我们经常在需要求最值的场景使用它。

    然而普通堆它有一个缺点,它没办法快速的定位一个元素,因此它也没办法快速删除一个堆中元素,需要遍历整个堆去查询目标元素,时间复杂度是O(n),因为堆的结构在逻辑上是这样的:

    GO语言怎么实现支持O(log(n))随机删除元素的堆

    在实际实现中一般是使用一个数组来模拟:

    GO语言怎么实现支持O(log(n))随机删除元素的堆

    也就是除了最大值(大顶堆)或最小值(小顶堆),其他元素其实是没有排序的,因此没办法通过二分查找的方式快速定位。

    但是我们经常有一种场景,需要堆的快速求最值的性质,又需要能够支持快速的随机访问元素,特别是删除元素。

    比如延迟任务的场景,我们可以使用堆对任务的到期时间戳进行排序,从而实现到期任务自动执行,但是它没办法支持随机删除一个延迟任务的需求。

    下面将介绍一种支持O(log(n))随机删除元素的堆。

    原理

    数据结构

    一种能够快速随机访问元素的数据结构是map,map如果是哈希表实现则能够在O(1)的复杂度下随机访问任何元素,而heap在知道要删除的元素的下标的情况下,也可以在O(log(n))的复杂度删除一个元素。因此我们可以结合这两个数据结构,使用map来记录heap中每个元素的下标,使用heap来获取最值。

    比如对于上面的堆,我们首先给每个元素添加一个Key,这样我们才能够使用map:

    GO语言怎么实现支持O(log(n))随机删除元素的堆

    然后我们使用map记录每个key对应的下标:

    GO语言怎么实现支持O(log(n))随机删除元素的堆

    随机访问

    这时候比如我们最简单的随机访问一个元素C,那么就是从map[C]得到元素在heap里面的index=2,因此可以拿到元素的值。

    index = m[C] // 获取元素C在heap的下标return h[index] // 获取index在heap的值

    删除

    而如果我们要删除元素C,我们也是从map[C]得到元素在heap里面的index=2,然后把index为2的元素和堆最后一个元素交换,然后从index=2向上和向下调整堆,也就是:

    index = m[C] // 获取元素C在heap的下标swap(index, n - 1) // 和最后一个元素交换pop() // 移除最后一个元素,也就是元素Cdown(index) // 从index向下调整堆up(index) // 从index向上调整堆

    map里面的元素index维护

    上面使用的swap(i, j)和pop()操作都会影响到map里面元素的index,其实还有push(k, v)操作也会影响元素的index。

    对于swap(i, j)来说需要交换两个元素的index:

    h[i], h[j] = h[j], h[i] // 交换堆中两个元素m[h[i].Key] = i // 交换map元素索引m[h[j].Key] = j // 交换map元素索引

    pop()需要删除元素的索引:

    elem = h.removeLast() // 移除最后一个元素m.remove(elem.Key) // 移除元素索引

    push(k, v)需要添加元素索引:

    m[key] = n // 添加元素索引h.addLast(Entry(K, V)) // 添加元素到堆

    这样其他操作就不需要维护map里面的索引问题了,保持和正常的堆的实现逻辑基本一致。

    Golang实现

    由于这个数据结构使用到了map和heap,因此起了一个比较短的名字叫meap,也就是m[ap]+[h]eap

    数据结构

    其中主要就是一个heap和一个map,由于我们也需要从heap到map的操作,因此heap里面每个元素Entry都记录了Key,这样就可以从heap快速访问到map里面的元素,实现map里面index的修改。

    LessFunc主要用于比较两个元素大小。

    type Meap[K comparable, V any] struct {h        []Entry[K, V]m        map[K]intlessFunc LessFunc[K, V]}type Entry[K comparable, V any] struct {Key   KValue V}type LessFunc[K comparable, V any] func(e1 Entry[K, V], e2 Entry[K, V]) bool

    移除堆顶元素

    这里和正常的堆的逻辑是一样的,也就是把堆顶元素和最后一个元素交换,然后调整堆,移除堆中最后一个元素。

    func (h *Meap[K, V]) Pop() Entry[K, V] {n := h.Len() - 1h.swap(0, n) // 堆顶和最后一个元素交换h.down(0, n) // 调整堆return h.pop() // 移除堆中最后一个元素}

    添加元素

    这里的参数和普通的堆有一点区别,也就是我们有Key和Value,因为map必须使用一个Key,因此多了一个Key参数。

    由于有map的存在,我们可以先判断元素是否已经存在,如果存在则设置Value然后调整堆即可。

    如果不存在则添加元素到堆的最后,然后调整堆。

    func (h *Meap[K, V]) Push(key K, value V) {// 如果堆中已经包含这个元素// 更新值并调整堆if h.Contains(key) {index := h.m[key] // 元素在堆中下标h.h[index].Value = value // 更新堆中元素值h.fix(index) // 向上向下调整堆return}// 否则添加元素h.push(key, value) // 添加元素到堆的最后面h.up(h.Len() - 1) // 向上调整堆}

    移除元素

    我们首先通过key定位元素在堆中下标,然后把这个下标和堆最后一个元素交换,调整堆,最后把堆最后一个元素移除。

    func (h *Meap[K, V]) Remove(key K) {i, ok := h.m[key] // 获取元素在堆中下标if !ok { // 如果元素不存在则直接返回return}n := h.Len() - 1 // 最后一个元素索引if n != i { // 如果被移除的元素就是堆中最后一个元素,则没必要调整了,直接移除即可h.swap(i, n) // 和最后一个元素交换if !h.down(i, n) { // 向下调整h.up(i) // 向上调整}}h.pop() // 移除堆中最后一个元素}

    push()、pop()和swap()

    涉及到调整map中index的操作都集中到这三个操作之中:

    // swap两个元素的时候// 两个元素在map里的下标也要交换func (h *Meap[K, V]) swap(i, j int) {h.h[i], h.h[j] = h.h[j], h.h[i] // 交换两个元素h.m[h.h[i].Key] = i // 更新索引h.m[h.h[j].Key] = j // 更新索引}// 添加一个元素到堆的末尾func (h *Meap[K, V]) push(key K, value V) {h.m[key] = h.Len() // 添加索引h.h = append(h.h, Entry[K, V]{ // 添加元素到堆尾Key:   key,Value: value,})}// 从堆的末尾移除元素func (h *Meap[K, V]) pop() Entry[K, V] {elem := h.h[h.Len()-1] // 堆尾元素h.h = h.h[:h.Len()-1] // 移除堆尾元素delete(h.m, elem.Key) // 删除堆尾元素索引return elem}

    另外一种实现方式

    其实引入一个map对性能的影响还是比较大的,有些场景我们可能不想提前引入map,是否需要map可以交给用户去决定,这时候可以使用另外一种实现方式。

    这种实现方式的原理是在堆的元素Entry里面设置元素所属下标,然后把这个元素返回给用户,下标的修改和 上面的swap()、pop()、push()类似。其实原理和上面是一样的,只是把更多的控制权交给用户。

    数据结构

    这里Entry里面带上了index和h,index就是元素在堆里的下标,value是元素的值。这里取名叫做reap=r[emovable]+[h]eap

    type Entry[T any] struct {value Tindex int}func (e *Entry[T]) Value() T {return e.value}type LessFunc[T any] func(e1, e2 T) bool// reap=r[emovable]+[h]eap// 可以通过Entry实现log(n)删除任意元素的堆type Reap[T any] struct {h        []*Entry[T]lessFunc LessFunc[T]}

    swap()、pop()、push()

    可以看到和上面的meap是类似的,只是这里改成元素在堆的下标放到元素的index字段里面。

    // swap两个元素的时候func (h *Reap[T]) swap(i, j int) {h.h[i], h.h[j] = h.h[j], h.h[i]h.h[i].index = ih.h[j].index = j}// 添加一个元素到堆的末尾func (h *Reap[T]) push(value T) *Entry[T] {entry := &Entry[T]{value: value,index: h.Len(),}h.h = append(h.h, entry)return entry}// 从堆的末尾移除元素func (h *Reap[T]) pop() T {elem := h.h[h.Len()-1]h.h = h.h[:h.Len()-1]        // 标记元素已经被删除elem.index = -1return elem.value}

    添加元素

    添加元素到堆和普通堆一样,只是我们把Entry返回回去,这样用户才能通过Entry进行删除。

    // 添加元素到堆func (h *Reap[T]) Push(value T) *Entry[T] {entry := h.push(value)h.up(h.Len() - 1)return entry}

    删除元素

    这里首先判断元素是否已经被删除,这里-1是在pop()操作里面设置的。然后删除元素就是正常堆删除元素的流程。

    // 移除堆里对应的元素func (h *Reap[T]) Remove(e *Entry[T]) {// 不能已经被删除if e.index == -1 {return}// 删除元素i := e.indexn := h.Len() - 1if n != i {h.swap(i, n)if !h.down(i, n) {h.up(i)}}h.pop()}

    重新设置值

    我们还可以实现重新设置元素的值的功能,设置完新值之后,元素的优先级可能会改变,因此需要调整一下堆。

    // 设置元素的值,会重新调整堆func (h *Reap[T]) SetValue(e *Entry[T], value T) bool {// 不能已经被删除if e.index == -1 {return false}        // 重新设置值并调整e.value = valueh.fix(e.index)return true}

    时间复杂度

    上面两种Golang实现中关键操作的时间复杂度:

    操作时间复杂度描述
    Push()O(log(n))添加元素
    Pop()O(log(n))移除堆顶元素
    Peek()O(1)获取堆顶元素
    Remove()O(log(n))删除元素

    可以看到是和普通堆是一样的。

    性能测试

    对Heap,Reap和Meap进行简单的性能测试,也就是先全部Push()再全部Pop()。

    可以看到Heap的性能是最好的,Reap比Heap差一些,主要是Reap涉及到index的维护,需要额外的数据结构和操作,而且Push()需要返回一个Entry指针给用户,因此还涉及到一次内存分配。

    Meap因为引入了map,因此功能是最强大的,但是性能也是比较普通,大约只有Heap的1/6,空间消耗大约是Heap的4倍。

    BenchmarkHeapPushAndPop-8        6042358               165.6 ns/op            41 B/op          0 allocs/opBenchmarkReapPushAndPop-8        4114232               329.6 ns/op            64 B/op          1 allocs/opBenchmarkMeapPushAndPop-8        1000000              1563 ns/op             175 B/op          0 allocs/op

    以上就是“GO语言怎么实现支持O(log(n))随机删除元素的堆”这篇文章的所有内容,感谢各位的阅读!相信大家阅读完这篇文章都有很大的收获,小编每天都会为大家更新不同的知识,如果还想学习更多的知识,请关注编程网行业资讯频道。

    免责声明:

    ① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

    ② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

    GO语言怎么实现支持O(log(n))随机删除元素的堆

    下载Word文档到电脑,方便收藏和打印~

    下载Word文档

    猜你喜欢

    GO语言怎么实现支持O(log(n))随机删除元素的堆

    今天小编给大家分享一下GO语言怎么实现支持O(log(n))随机删除元素的堆的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。背
    2023-07-06

    编程热搜

    • Python 学习之路 - Python
      一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
      Python 学习之路 - Python
    • chatgpt的中文全称是什么
      chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
      chatgpt的中文全称是什么
    • C/C++中extern函数使用详解
    • C/C++可变参数的使用
      可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
      C/C++可变参数的使用
    • css样式文件该放在哪里
    • php中数组下标必须是连续的吗
    • Python 3 教程
      Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
      Python 3 教程
    • Python pip包管理
      一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
      Python pip包管理
    • ubuntu如何重新编译内核
    • 改善Java代码之慎用java动态编译

    目录