用完全二叉树实现堆
Willem Zhang Lv6

最小堆的情况
二叉树顶部为最小值
sink方法:
值sink的时候要将值放到最小索引的位置,默认要sink的节点的索引是最小值所在的索引(这样防止了子节点不存在的情况),然后节点和它的左右节点比大小,然后得到最小索引的位置,最后值会和最小索引位置的值进行交换,于是这个值就sink到了最小索引的位置,当这个值比他左右都小的时候,这个值所在的位置就是最小索引的位置,不用交换。

ref

https://coffe1891.gitbook.io/frontend-hard-mode-interview/2/2.1.1

  • Post title:用完全二叉树实现堆
  • Post author:Willem Zhang
  • Create time:2021-11-28 12:47:39
  • Post link:https://ataraxia.top/2021/11/28/用完全二叉树实现堆/
  • Copyright Notice:All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments