最新公告
  • 新注册用户请前往个人中心绑定邮箱以便接收相关凭证邮件!!!点击前往个人中心
  • 数据结构笔记总结(7.4)从堆中取出元素和Sift Down

    从堆中取出元素

    我们之所以管它叫“最大堆”就是因为我们从堆中只取出堆顶的元素,也就是二叉树根节点所在的元素,这个元素也是堆中最大的元素,取出操作只能取出这个元素而不能取出其他的元素。

    那么这个过程怎么实现呢?将索引为0的元素拿出去之后,现在对于整个堆可以看成有两棵子树。

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

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

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

    这个过程其实也很简单,每次要下沉的元素都去和它的两个孩子去比较,选择两个孩子中最大的元素,如果两个孩子中最大的元素比自己还要大的话,那自己就和两个孩子中最大的元素交换位置,这个例子中16就和52交换位置,交换完位置之后,对于52这个元素就一定比左右两个孩子节点要大了。

    交换完后,对于16这个元素新的位置依然可能不满足堆的性质,依然要继续下沉下去,16再和41交换位置。

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

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

    代码演示

    // 看堆中的最大元素
    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.");
        }
    }
    

    运行程序,结果正确

    堆的时间复杂度分析

    这两个操作时间复杂度都是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

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    参与讨论

    • 192会员总数(位)
    • 3737资源总数(个)
    • 0本周发布(个)
    • 0 今日发布(个)
    • 614稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级