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