如何找出一个数列中的最大的N个值?
这是一个在面试中经常遇见的问题,此问题的关键是应尽可能的减少节点的比较次数,从而降低时间复杂度.因此选择小顶堆这个数据结构....节点41,先放入树的最后节点上,即节点42的左叶子节点上,并与父节点(节点42)比较,比父节点值小,交换位置.
3. 节点31,放入树最后节点,并与父节点41比较,比父节点值小,交换位置.
4....节点7,首先放在树最末节点,比父节点42值小,交换位置.在与当前节点位置的父节点31比较,仍小于父节点,再次交换位置.
5....删除节点
小顶堆的删除过程,主要是指删除数组的最小节点,也就是array[0],但通过数据节点交换,是不需要对各元素移位或进行数组复制的....删除根节点7
将原有最后一个节点代替为根节点,并与自己较小的叶子节点(17)比较,并交换位置.再次与自己当前位置的叶子节点(42)比较,小于叶子节点值,不需要再次交换.
3.其他节点的删除过程也类似这样