Java 最大堆

最大堆就是每个节点元素的值都要大于其子节点元素的值。

底层利用数组来实现最大堆：

1.最大堆的基本结构：

public class MaxHeap<E extends Comparable<E>> {

    private Array<E> data;

    //动态数组：用户向堆存放元素
    public MaxHeap(int capacity){
        //初始化动态数组
        data = new Array<>(capacity);
    }

    public MaxHeap(){
        data = new Array<>();
    }

    // 返回堆中的元素个数
    public int size(){
        return data.getSize();
    }

    // 返回一个布尔值, 表示堆中是否为空
    public boolean isEmpty(){
        return data.isEmpty();
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
    private int parent(int index){
        if(index == 0) {
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        }
        return (index - 1) / 2;
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
    private int leftChild(int index){
        return index * 2 + 1;
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
    private int rightChild(int index){
        return index * 2 + 2;
    }
}

2.向最大堆中添加元素(Sift Up)

从堆的角度来看，添加元素，从左到右的顺序添加，如果那一层满了就再往下一层添加，而数组就直接在最后一个位置添加元素，

不过此时堆中添加的元素是52，添加的元素比该元素的父节点元素要大，所以下面需要进一步的分析：

1.此时由于添加的52子节点元素大于父节点元素16，所以对其两者进行交换位置：

2.此时成功换了位置，但是此时的52节点比其父节点41还要大，所以再次进行互换。

3.此时再对其父节点进行比较，发现比父节点小，所以此时完成了添加操作。

    // 向堆中添加元素
    public void add(E e){
        //向数组添加元素
        data.addLast(e);
        //维护堆的性质，添加最后一个元素
        siftUp(data.getSize() - 1);
    }
    //索引k
    private void siftUp(int k){
        //索引不能等于0，并且如果父节点的值小于要添加的节点的值
        while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0 ){
            //则需要进行sift up操作
            data.swap(k, parent(k));
            //值已经进行互换了，所以要对其索引位置进行变化，方便下一次判断
            k = parent(k);
        }
    }

向我们自己实现的Arrays数组添加一个swap方法。

  //索引i,j  
  public void swap(int i, int j){
        //判断i,j是否正常
        if(i < 0 || i >= size || j < 0 || j >= size) {
            throw new IllegalArgumentException("Index is illegal.");
        }
        //临时存放空间，先将要添加的元素存放进去
        E t = data[i];
        //将父节点j的元素换到i位置上
        data[i] = data[j];
        //再将j位置赋值为t里面的值
        data[j] = t;
    }

3.从最大堆中取出元素（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(){
        //向ret存放堆的最大元素
        E ret = findMax();
        //让堆中最大的元素与索引最后的元素交换位置
        data.swap(0, data.getSize() - 1);
        //删除交换后的索引最后的元素
        data.removeLast();
        //对堆顶的元素进行位置调整
        siftDown(0);
        //返回堆最大元素，此时成功取出最大元素
        return ret;
    }
    //下沉
    private void siftDown(int k){
        //k的左孩子索引越界，说明没有该元素，即判断k节点是不是叶子节点
        while(leftChild(k) < data.getSize()){ //k不是叶子节点
            int j = leftChild(k); 
            // 在此轮循环中,data[k]和data[j]交换位置
            //j+1就是k节点的右子节点，比data.getSize小，说明有右子节点
            //并且如果右子节点的元素要大于左子节点的元素的话
            if( j + 1 < data.getSize() &&
                    data.get(j + 1).compareTo(data.get(j)) > 0 ) {
                //即j = rightChild(k); 替换位置，因为此时的j已经存放了leftChild(k)
                //所以j++表示将k索引元素与右子节点元素交换
                j ++;
            }
            //如果上面的判断是左节点比右节点要大的话
            if(data.get(k).compareTo(data.get(j)) >= 0 ) {
                break;
            }
            //让k索引元素与判断得来的右或左节点进行交换
            data.swap(k, j);
            //交换成功，再k的索引进行维护
            k = j;
        }
    }

测试类：

import java.util.Random;

public class Main {

    public static void main(String[] args) {

        int n = 1000000;

        MaxHeap<Integer> 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.");
    }
}

运行结果：Test MaxHeap completed.

4.Heapify和replace

replace:取出最大元素后，放入一个新的元素。

实现：可以先extractMax，再add，两次O(logn)的操作。

实现：可以直接将堆顶元素替换以后Sift Down，一次O(logn)的操作。

    // 取出堆中的最大元素，并且替换成元素e
    public E replace(E e){
        //向ret存放取出的最大值
        E ret = findMax();
        //调用数组的set方法，将堆顶元素替换成e
        data.set(0, e);
        //再进行下沉操作
        siftDown(0);
        return ret;
    }

heapify:将任意数组整理成堆的形状。

1.从最后一个非叶子节点开始计算：

2.也就是图中22这个位置的元素。如果发现该位置上的元素要小于该子节点元素值，则进行sift down操作：此时22为叶子节点，所以此次操作结束。

3.接着对该位置的同级左节点进行判断操作：

4.此时41比13大，所以进行下沉操作，下沉后的13为叶子节点，所以此处交换成功。

 

5.接着对索引为2的位置进行比较：

6.28比19大进行下沉操作：

7.此时的19为叶子节点，所以此次操作结束。

8.接着对索引为1的位置元素进行比较：

9.由于17小于叶子节点元素值，所以17与62进行交换：

10.此时的17并不是叶子节点，所以再对17此时的位置进行比较：

11.发现17比22小，则进行交换：

12.最后对索引为0的元素进行比较：

13.此时的15小于叶子节点，所以62与之交换：

14.由于此时位置的15并不是叶子节点，所以还要对该位置下的15进行比较：依次类推，直到没有叶子节点位置。

 

此时数组的变化成：

 

将n个元素插入到一个空堆中，算法复杂度为O(nlogn);

heapify的算法复杂度：O(n)

Heapify的实现：

    public MaxHeap(E[] arr){
        //用户传进来一个数组，然后传进来再生成一个新的数组
        data = new Array<>(arr);
        //从倒数第一个非叶子节点到根节点开始遍历判断
        for(int i = parent(arr.length - 1) ; i >= 0 ; i --) {
            //对每个节点进行判断下沉操作
            siftDown(i);
        }
    }

对我们自己实现的动态数组Arrays，添加一个构造方法：

    public Array(E[] arr){
        //新建一个数组
        data = (E[])new Object[arr.length];
        for(int i = 0 ; i < arr.length ; i ++) {
            data[i] = arr[i];
        }
        size = arr.length;
    }

测试类：

import java.util.Random;

public class Main {

    private static double testHeap(Integer[] testData, boolean isHeapify){

        long startTime = System.nanoTime();

        MaxHeap<Integer> maxHeap;
        if(isHeapify){
            maxHeap = new MaxHeap<>(testData);
        }else{
            maxHeap = new MaxHeap<>();
            for(int num: testData)
                maxHeap.add(num);
        }

        int[] arr = new int[testData.length];
        for(int i = 0 ; i < testData.length ; i ++){
            arr[i] = maxHeap.extractMax();
        }
        for(int i = 1 ; i < testData.length ; i ++){
            if(arr[i-1] < arr[i]){
                throw new IllegalArgumentException("Error");
            }
        }
        System.out.println("Test MaxHeap completed.");

        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }

    public static void main(String[] args) {

        int n = 1000000;

        Random random = new Random();
        Integer[] testData = new Integer[n];
        for(int i = 0 ; i < n ; i ++) {
            testData[i] = random.nextInt(Integer.MAX_VALUE);
        }
        double time1 = testHeap(testData, false);
        System.out.println("Without heapify: " + time1 + " s");

        double time2 = testHeap(testData, true);
        System.out.println("With heapify: " + time2 + " s");
    }
}

测试结果：

温馨提示

关注我的公众号【Java剑主】，学习更多有深度的技术文章。本博客不在记录原创博文，请移步公众号获取最新内容。

修道注重根基，熟透原理方能看透事物本质，编程亦如此！ Java修炼之道，道心坚不移！踏剑寻梦，不忘初心！