1. 当前已经上浮到树根 =》 这个元素一定是最大值
2. 当前元素 <= 父节点对应的元素值，此时元素落到在正确位置

2.2.2 在堆中取出最大值（shiftDown 操作）

在堆顶取得最大值后，如何移动元素可以保证此时还是个最大堆呢？

步骤如下：

1. 最大堆的最大值一定处在树根节点，直接取出树根即可
2. 需要融合左右两个子树，使得取出树根后这棵树仍然是最大堆
3. 将堆中最后一个元素顶到堆顶，然后进行元素的下沉操作。 shifDown后 使其仍然满足最大堆的性质

其实堆排序就是建立最大堆，然后在最大堆的基础上进行调整操作，就可以得到一个升序集合~~

2.2.3 堆化（heapify）

现在给一个任意的整型数组 =》 都可以看作是一个完全二叉树，距离最大堆就差元素调整操作。

方法一：建堆

将这n个元素依次调用add方法添加到一个新的最大堆中，遍历原数组，创建一个新的最大堆，调用最大堆的add方法即可。

时间复杂度为：O( $nlogn$)

空间复杂度为：O( $n$)

方法二：原地heapify（重要）

从最后一个非叶子结点开始进行元素siftDown操作

从当前二叉树中最后一个小子树开始调整，不断向前，直到调整到根节点。

不断将子树调整为最大堆的时，最终走到树根时，左右子树已经全部是最大堆，只需最后下沉根节点就能的到最终的最大堆。

时间复杂度为 Sn = $nlog_2(n+1)$ ，因此最终可得渐进复杂度为O( $n$）

三、代码实现

写一个基于动态数组实现最大堆的实例：

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

public class MaxHeap {
    // 实际存储元素的数组
    private List<Integer> elementData;
    // 当前堆中元素个数
    private int size;

    public MaxHeap() {
        this(10);
    }

    public MaxHeap(int size) {
        elementData = new ArrayList<>(size);
    }

    /**
     * 将任意的整型数组arr调整为堆
     * @param arr
     */
    public MaxHeap(int[] arr) {
        elementData = new ArrayList<>(arr.length);
        // 1.先将所有元素复制到data数组中
        for (int i : arr) {
            elementData.add(i);
            size ++;
        }
        // 2.从最后一个非叶子结点开始进行siftDown操作
        for (int i = parent(size - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

    public void add(int val) {
        // 1.直接向数组末尾添加元素
        elementData.add(val);
        size ++;
        // 2.进行元素的上浮操作
        siftUp(size - 1);
    }

    /**
     * 取出当前最大堆的最大值
     * @return
     */
    public int extractMax() {
        if (size == 0) {
            throw new NoSuchElementException("heap is empty!cannot extract!");
        }
        // 树根就是最大值结点
        int max = elementData.get(0);
        // 将数组的末尾元素顶到堆顶
        elementData.set(0,elementData.get(size - 1));
        // 将数组的最后一个元素从堆中删除
        elementData.remove(size - 1);
        size --;
        // 进行元素的下沉操作，从索引为0开始
        siftDown(0);
        return max;
    }

    public int peekMax() {
        if (isEmpty()) {
            throw new NoSuchElementException("heap is empty!cannot peek!");
        }
        return elementData.get(0);
    }

    /**
     * 从索引k开始进行元素的下沉操作
     * @param k
     */
    private void siftDown(int k) {
        // 还存在子树
        while (leftChild(k) < size) {
            int j = leftChild(k);
            // 此时还存在右子树
            if (j + 1 < size && elementData.get(j + 1) > elementData.get(j)) {
                // 此时还存在右子树且右子树的值还比左子树大
                j ++;
            }
            // 索引j一定对应了左右子树的最大值索引
            if(elementData .get(k) >= elementData.get(j)) {
                // 当前元素 >= 左右子树最大值，下沉结束，元素k落在了最终位置
                break;
            }else {
                swap(k,j);
                k = j;
            }
        }
    }


    private void siftUp(int k) {
        while (k > 0 && elementData.get(k) > elementData.get(parent(k))) {
            swap(k,parent(k));
            k = parent(k);
        }
    }

    private void swap(int k, int parent) {
        int child = elementData.get(k);
        int parentVal = elementData.get(parent);
        elementData.set(k,parentVal);
        elementData.set(parent,child);
    }


    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 找到结点k对应的父节点的索引
     * @param k
     * @return
     */
    private int parent(int k) {
        return (k - 1) >> 1;
    }

    /**
     * 找到结点k对应的左子树的索引
     * @param k
     * @return
     */
    private int leftChild(int k) {
        return (k << 1) + 1;
    }

    /**
     * 找到结点k对应的右子树的索引
     * @param k
     * @return
     */
    private int rightChild(int k) {
        return (k << 1) + 2;
    }

    @Override
    public String toString() {
        return elementData.toString();
    }
}

总结

基于堆的优先级队列可以用于解决Top K问题，博主推荐几道💪扣编程题：

• 面试题17.14 最小K个数
• 347.前k个高频元素
• 373.查找最小的K对数字

后续博主会更新自己的题解以及思路，大家也可以自己做做，看看官方题解~