首页 > 代码库 > 【笔记】【数据结构】二叉堆
【笔记】【数据结构】二叉堆
作用:
插入元素,O(lgN)
修改元素,O(lgN)
删除元素,O(lgN)
查询元素,O(1)
动态查询最值,O(NlgN)-O(lgN)-O(1)
核心操作:
上浮与下沉
最小堆:上浮是指较小值上浮,下沉是指较大值下沉。
最大堆:上浮是指较大值上浮,下沉是指较小值下沉。
具体操作:
- 预处理中,对所有的根节点下沉操作,即交换根节点与一个较小的子节点,然后接着将子节点作为根节点,进行下一次下沉操作。
- 插入元素时,将它放入最底层,并不断地上浮。
- 删除堆顶元素时,将堆顶元素与最后一个元素交换,然后下沉。
- 修改元素时,首先查询元素的地址,随后修改值,接着上浮下沉各一次以保持堆的性质。
- 删除元素时,先修改为负无穷大,然后上浮到堆顶,删除堆顶。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。