首页 > 代码库 > 【笔记】【数据结构】二叉堆

【笔记】【数据结构】二叉堆

作用:

插入元素,O(lgN)

修改元素,O(lgN)

删除元素,O(lgN)

查询元素,O(1)

动态查询最值,O(NlgN)-O(lgN)-O(1)

核心操作:

上浮与下沉

最小堆:上浮是指较小值上浮,下沉是指较大值下沉。

最大堆:上浮是指较大值上浮,下沉是指较小值下沉。

具体操作:

  1. 预处理中,对所有的根节点下沉操作,即交换根节点与一个较小的子节点,然后接着将子节点作为根节点,进行下一次下沉操作。
  2. 插入元素时,将它放入最底层,并不断地上浮。
  3. 删除堆顶元素时,将堆顶元素与最后一个元素交换,然后下沉。
  4. 修改元素时,首先查询元素的地址,随后修改值,接着上浮下沉各一次以保持堆的性质。
  5. 删除元素时,先修改为负无穷大,然后上浮到堆顶,删除堆顶。