首页 > 代码库 > 最小堆
最小堆
堆的定义是: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.结束后,
最小堆
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。