首页 > 代码库 > 最小堆

最小堆

堆的定义是:n个元素的序列{k1,k2,…,kn},当且仅当满足如下关系时被成为堆 《

    (1)Ki <= k2i 且 ki <= k2i+1        

  或 (2) Ki >= k2i 且 ki >= k2i+1 

          (i = 1,2,…[n/2])

当满足(1)时,为最小堆,当满足(2)时,为最大堆。

 

最小堆的特点:其根基点小于或者等于其左右子节点的完全二叉树。

push插入算法的原理:插入到最后一个节点,然后shift_up上移进行调整;

pop删除算法的原理:删除根节点,然后shift_down下移进行调整。

 

shift_up的原理:

1.找到父节点

2.比较父节点和当前节点的大小

3.如果父节点大,则交换

4.一直递归到根节点

 

shift_down的原理:

1.找到左节点、右节点

2.取左右节点的小值的节点

3.比较最后一个节点和上面节点,如果最后一个节点小,break

4.否则把该节点当作父节点,从1再开始

5.结束后,

 

最小堆