BMK1.5

BMK1.5

BMK1.5树的基本操作是插入节点和删除节点。对小堆而言，为了将一个元素X插入小堆，我们可以在树的下一个空闲位置创建一个空穴。如果X可以放在空穴中而不被破坏堆的序，则插入完成。否则就执行上滤操作，即交换空穴和它的父节点上的元素。不断执行上述过程，直到X可以被放入空穴，则插入操作完成。

因此我们可以知道小堆的插入时间复杂度是O(lgN)。

小堆的删除和插入逻辑基本类似，如果不做优化，时间复杂度也是O(lgN),但是实际实现方案上，做了延迟删除操作，时间复杂度为O(1)。

延迟删除即设置定时器的执行回调函数为空，每次小堆超时，将触发pop_heap，pop会重新调整小堆，终删除的定时器将调整到堆顶，但是回调函数不处理。

可以看到PerTickBookkeeping只处理堆顶定时器，时间复杂度O(1)。

小堆可以使用数组来进行表示，数组中，当前下标n的左子节点为2N + 1，当前下标n的右子节点小标为2N + 2。

BMK1.5