基本概念

底层是二叉树,根节点最小(或最大),除最后一分支其他的都满了,数组实现的堆不要求左边的比右边的小。

用数组来维护,索引从1开始,2n 是左节点,2n + 1是右节点

实现功能

插入一个数: 插在数组最后,再往上查找位置

求最小: 根(头)节点

删除最小值: 将最后一个点覆盖到头节点,删掉最后一个,然后往下找自己的位置

为什么呢?因为数组存储很难删掉头元素,但是删掉最后一个很简单,所以通过覆盖掉头元素,直接去掉最后一个元素,再往下down操作找正确位置

删除任意元素: 用最后一个覆盖,再往下找再往上找,其实是此时覆盖之后最后一个元素可能有三种情况(最后一个不一定是最大值):

  • 如果大,就往下
  • 小就往上 所以直接down一次,up一次

修改元素 直接改,往上找也往下找

具体使用