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

向堆中添加元素

这个过程从用户的角度看是添加元素,不过从堆的角度看涉及一个非常基础的内部操作,相应的英文叫Sift up(堆中的元素上浮的过程),下面我们来看一下如果想向堆中添加元素应该怎么做。
数据结构笔记总结(7.3)向堆中添加元素和Sift Up
首先由于我们堆中的数据是使用数组排列的,添加元素相当于是在层序遍历最右端,也就是最下面一层的最后再添加一个元素。

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

从数组的角度来看的话,对我们这个例子来说其实就是在索引为10的位置添加这个52,这样就将这个元素添加进堆中了。
数据结构笔记总结(7.3)向堆中添加元素和Sift Up
不过要注意一下,添加进堆后虽然依然满足完全二叉树这种性质,但是它并不满足每一个节点都大于孩子节点,16的这个节点由于52加入,它就已经小于它的孩子节点了,所以相应的应该进行一些调整。

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

之前我们实现的找一个节点的父亲节点在哪就能发挥作用了,我们就可以直接找到52的父亲节点是16,对于16这个节点来说它小于52,我们只需要交换这两个元素的位置就好了。
数据结构笔记总结(7.3)向堆中添加元素和Sift Up

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

对于52这个节点来说,它现在在索引为4的位置,在这个新的位置上和新的父亲节点去比较52是否还是大于它的父亲节点呢?
数据结构笔记总结(7.3)向堆中添加元素和Sift Up

52依然大于父亲节点,所以二者再次交换位置,现在以52为根的二叉树整体又维持住堆的性质,下面继续看52没有破坏堆的性质,那就可以不用动了。
数据结构笔记总结(7.3)向堆中添加元素和Sift Up

那么这个过程就叫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;
}

源码下载

[dm href='https://www.jikewenku.com/product/1487.html']下载地址[/dm]

导航目录

[dm href='https://www.jikewenku.com/geeknote/2241.html']查看导航[/dm]

本站所有文章均来自互联网,如有侵权,请联系站长删除。极客文库 » 数据结构笔记总结(7.3)向堆中添加元素和Sift Up
分享到:
赞(0)

评论抢沙发

评论前必须登录!