• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

数据结构笔记总结(7.3)向堆中添加元素和Sift Up

极客笔记 Geekerstar 11个月前 (05-19) 611次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

向堆中添加元素

这个过程从用户的角度看是添加元素,不过从堆的角度看涉及一个非常基础的内部操作,相应的英文叫Sift up(堆中的元素上浮的过程),下面我们来看一下如果想向堆中添加元素应该怎么做。

首先由于我们堆中的数据是使用数组排列的,添加元素相当于是在层序遍历最右端,也就是最下面一层的最后再添加一个元素。

当然如果最下面一层已经没有位置再添加新的元素了就相应的重新加一层。

从数组的角度来看的话,对我们这个例子来说其实就是在索引为10的位置添加这个52,这样就将这个元素添加进堆中了。

不过要注意一下,添加进堆后虽然依然满足完全二叉树这种性质,但是它并不满足每一个节点都大于孩子节点,16的这个节点由于52加入,它就已经小于它的孩子节点了,所以相应的应该进行一些调整。

我们可以想象一下,当前的这个堆不再满足堆的性质就是因为新添加了52这个元素,那么出问题也只有可能出现在52的父亲节点以及52的父亲节点的父亲节点相应的这一路上,所以我们要做的就是从52开始,依次和它的父亲节点作比较。

之前我们实现的找一个节点的父亲节点在哪就能发挥作用了,我们就可以直接找到52的父亲节点是16,对于16这个节点来说它小于52,我们只需要交换这两个元素的位置就好了。

交换了两个元素位置之后,以52为根的这个二叉树就再次满足了堆的性质。

对于52这个节点来说,它现在在索引为4的位置,在这个新的位置上和新的父亲节点去比较52是否还是大于它的父亲节点呢?

52依然大于父亲节点,所以二者再次交换位置,现在以52为根的二叉树整体又维持住堆的性质,下面继续看52没有破坏堆的性质,那就可以不用动了。

那么这个过程就叫Sift Up,也就是在堆中元素的上浮过程

代码演示

// 向堆中添加元素
public void add(E e){
    data.addLast(e);
    siftUp(data.getSize() - 1);
}

private void siftUp(int k){

    while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0 ){
        data.swap(k, parent(k));
        k = parent(k);
    }
}

在Array.java中添加一个新的方法Swap

public void swap(int i, int j){

    if(i < 0 || i >= size || j < 0 || j >= size)
        throw new IllegalArgumentException("Index is illegal.");

    E t = data[i];
    data[i] = data[j];
    data[j] = t;
}

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(7.3)向堆中添加元素和Sift Up
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00