数据结构笔记总结(7.4)从堆中取出元素和Sift Down

从堆中取出元素

我们之所以管它叫“最大堆”就是因为我们从堆中只取出堆顶的元素,也就是二叉树根节点所在的元素,这个元素也是堆中最大的元素,取出操作只能取出这个元素而不能取出其他的元素。
数据结构笔记总结(7.4)从堆中取出元素和Sift Down
那么这个过程怎么实现呢?将索引为0的元素拿出去之后,现在对于整个堆可以看成有两棵子树。
数据结构笔记总结(7.4)从堆中取出元素和Sift Down

将这两棵子树再融成堆比较复杂,所以在这里我们使用一个小技巧,小技巧就是我们把堆中的最后那个元素(这个例子中就是16这个元素)顶到堆顶去,这样做完之后,数组表中0这个位置就是16了。
数据结构笔记总结(7.4)从堆中取出元素和Sift Down

不过整个数组中最后一个位置也是16,我们再把最后一个元素给删除掉,这样从元素的个数来说我们成功减少了一个,并且减少的元素就是原来堆顶的元素,此时整个二叉树也是满足完全二叉树形式的。但问题在于现在堆顶的这个元素打破了堆的性质(每个节点大于等于孩子节点的值)。

数据结构笔记总结(7.4)从堆中取出元素和Sift Down

此时我们又要进行调整,这个调整的过程我们是调整堆顶的根节点这个元素,我们需要把这个元素往下调,所以叫做Sift Down(数据的下沉)。

这个过程其实也很简单,每次要下沉的元素都去和它的两个孩子去比较,选择两个孩子中最大的元素,如果两个孩子中最大的元素比自己还要大的话,那自己就和两个孩子中最大的元素交换位置,这个例子中16就和52交换位置,交换完位置之后,对于52这个元素就一定比左右两个孩子节点要大了。
数据结构笔记总结(7.4)从堆中取出元素和Sift Down
交换完后,对于16这个元素新的位置依然可能不满足堆的性质,依然要继续下沉下去,16再和41交换位置。
数据结构笔记总结(7.4)从堆中取出元素和Sift Down

此时16比15大,下沉操作结束。

数据结构笔记总结(7.4)从堆中取出元素和Sift Down

通过下浮操作我们完成了从堆中取出元素,取出元素之后依然维持堆的性质。

代码演示

// 看堆中的最大元素
public E findMax(){
    if(data.getSize() == 0)
        throw new IllegalArgumentException("Can not findMax when heap is empty.");
    return data.get(0);
}

// 取出堆中最大元素
public E extractMax(){

    E ret = findMax();

    data.swap(0, data.getSize() - 1);
    data.removeLast();
    siftDown(0);

    return ret;
}

private void siftDown(int k){

    while(leftChild(k) < data.getSize()){
        int j = leftChild(k); // 在此轮循环中,data[k]和data[j]交换位置
        if( j + 1 < data.getSize() &&
                data.get(j + 1).compareTo(data.get(j)) > 0 )
            j ++;
        // data[j] 是 leftChild 和 rightChild 中的最大值

        if(data.get(k).compareTo(data.get(j)) >= 0 )
            break;

        data.swap(k, j);
        k = j;
    }
}

简单测试一下我们实现的堆这个数据结构,随机一百万个数从大到小排序

import java.util.Random;

public class Main {

    public static void main(String[] args) {

        int n = 1000000;

        MaxHeap maxHeap = new MaxHeap<>();
        Random random = new Random();
        for(int i = 0 ; i < n ; i ++)
            maxHeap.add(random.nextInt(Integer.MAX_VALUE));

        int[] arr = new int[n];
        for(int i = 0 ; i < n ; i ++)
            arr[i] = maxHeap.extractMax();

        for(int i = 1 ; i < n ; i ++)
            if(arr[i-1] < arr[i])
                throw new IllegalArgumentException("Error");

        System.out.println("Test MaxHeap completed.");
    }
}

运行程序,结果正确
数据结构笔记总结(7.4)从堆中取出元素和Sift Down

堆的时间复杂度分析

这两个操作时间复杂度都是O(logn)级别,由于是完全二叉树,所以永远不刽退化成链表。

源码下载

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

导航目录

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

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

评论抢沙发

评论前必须登录!