数据结构笔记总结（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.geekerstar.com/product/1487.html']下载地址[/dm]

导航目录

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