大顶堆MaxHeap（原理与Java实现）

1. 为什么要引入堆？

1.1 堆的应用场景

有时候我们面临一种实际应用场景需要根据任务的重要程度而划分优先级，对优先级高的任务提供优先服务。

优先级队列(Priority Queue)：取出元素的顺序是依据优先级大小，而不是元素进入队列的先后顺序。

优先级队列实现要求：维护这样一种结构，取出数据时总是取出集合中的最值(可以是最大值，也可以是最小值)

1.2 堆的引入

🤔 什么样的结构可以高效地存储和维护集合使其满足优先级队列的特点呢？

✏️数组：不排序

1. 插入——元素总是插入尾部(维护一个size字段) ——O(1)
2. 删除——查找最值——O(n)，从数组中删去需要移动元素——O(n)

✏️链表：不排序

1. 插入——元素总是插入头部或者尾部 ——O(1)
2. 删除——查找最值——O(n)，从数组中删去最值结点——O(1)

✏️有序数组

1. 插入——找到合适位置 ——O(n)或者二分法 O(logn)；移动元素并插入 O(n)
2. 删除——删去最后一个元素——O(1)

✏️有序链表

1. 插入——找到合适位置 ——O(n)；插入 O(1)
2. 删除——删去首元素或者最后一个元素——O(1)

结果发现，总有一个操作的时间复杂度让人不满意💢

👍 是否可以采用二叉树存储结构？

二叉搜索树的查找和插入，较好的时间复杂度都是 O(logn)的，是树的高度。但是如果删除不当，会导致树退化成线性表。

如果采用树结构，更应该关注删除，最好是将树根作为最值存储点，父结点的值比子结点的值大。采用完全二叉树的结构最好。

堆
➡️结构性：用数组表示的完全二叉树
➡️有序性：任一结点的关键字是其子树所有结点的最大值(或最小值)
MaxHeap大顶堆
MinHeap小顶堆

用数组表示堆：图中圆内值为下标

求父节点下标需要向下取整

⚠️注意：0的父节点 (0-1)/2 = 0

2. 堆的描述

类型名称：最大堆(MaxHeap)

数据对象集: 完全二叉树，每个结点的元素值都不小于其子结点的元素值

操作集:
public MaxHeap(int maxSize): 创建一个空的最大堆
public boolean isFull(): 判断最大堆是否已满
public boolean isEmpty(): 判断最大堆是否为空
public int peek(): 查看堆顶元素值
public void push(int value): 将元素插入最大堆
public int pop(): 返回最大堆中的最大元素
private void heapInsert(int[] arr, int index): 实际插入元素的封装操作
private void heapify(int[] arr, int index, int heapSize): 删除元素后维护堆特性的封装
private void swap(int[] arr, int i, int j): 交换元素的封装
public List getAllElements(): 获取堆全部有效元素

3. 图解原理

整个堆结构中，最复杂的两个操作一个是插入元素保持堆特性，一个是删除最大元素保持堆特性。本节主要从这两方面的重点📦函数进行举例讲解。

3.1 heapInsert

插入元素之后要保持堆的特性(本例取大根堆特性)

我们用heapSize标识待插入元素的位置，每次插入元素就知道其下标，因为只有父结点值大，所以新插入元素不停地与父节点PK大小，如果新插入元素更大，那就与父结点交换，之后继续PK，直到无法PK胜出或者已经到达堆顶0位置为止。

    private void heapInsert(int[] arr, int index) {
        // 注意假如最后能比到0，此时下一次比较会跟自己比，必不可能大，所以会退出
        while (arr[index] > arr[(index - 1) / 2]) {  // index 比 父 大
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

3.2 heapify

假设堆不为空，取出堆顶元素，并将其从堆中删掉。

若此时堆为下图所示，圆中为实际结点值，右侧为数组内存存储值:

将8保存给变量ans,然后交换8和6(最后一个结点)，然后heapSize–，将8逻辑删除。最后对堆顶元素6进行heapify，使heapify后的数组保持堆特性。

    // 返回最大值
    public int pop() {
        int ans = heap[0];
        swap(heap, 0, --heapSize);
        heapify(heap, 0, heapSize);
        return ans;
    }

堆顶的6与自己的左右孩子PK(因为左孩子下标为1小于heapSize=4，所以是合法的，且右孩子也合法)，与较大孩子且能PK赢6的进行交换，即6与7进行交换。

随后重复上述过程，发现6无需移动，此时完成heapify

    // heapSize管着不会越界找孩子，左孩子若越界则右孩子必越界
    private void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;
        while ( left < heapSize) { // 如果有左孩子
            int right = left + 1;
            // 如果有右孩子,且右孩子值比左孩子值大
            // 选出较大孩子
            int largest = (right < heapSize && arr[right] > arr[left]) ? right : left;
            // 孩子和index对应的值PK，谁大谁给largest
            largest = arr[largest] > arr[index] ? largest : index;
            // 不必下沉
            if (largest == index) {
                break;
            }
            // index 和 较大孩子 largest要互换
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;  // 继续考察左孩子
        }
    }

4. 完整代码

AlgoUtils代码参考之前的文章

package com.ravi.datastructure.heap;

import com.ravi.algorithm.util.AlgoUtils;

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

/**
 * @author ravilian
 * max Heap
 */
public class MaxHeap {
    private int[] heap;
    private final int maxSize;
    private int heapSize;

    public MaxHeap(int maxSize) {
        heap = new int[maxSize];
        this.maxSize = maxSize;
        heapSize = 0;
    }

    public boolean isEmpty() {
        // 逻辑大小
        return heapSize == 0;
    }

    public boolean isFull() {
        return heapSize == maxSize;
    }

    public int peek() {
        if (heapSize == 0) {
            throw new RuntimeException("堆为空!");
        }
        return heap[0];
    }

    public void push(int value) {
        if (heapSize == maxSize) {
            throw new RuntimeException("heap is full");
        }
        heap[heapSize] = value;
        heapInsert(heap, heapSize++);
    }

    // 返回最大值
    public int pop() {
        int ans = heap[0];
        swap(heap, 0, --heapSize);
        heapify(heap, 0, heapSize);
        return ans;
    }

    /**
     * 新加进来的数，停在index位置，依次往上移动
     * 移动到0位置，或者PK不过父，停
     * @param arr
     * @param index
     */
    private void heapInsert(int[] arr, int index) {

        while (arr[index] > arr[(index - 1) / 2]) {  // index 比 父 大
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    /**
     * 从index位置往下看，不断下沉
     * 停：较大的孩子不再比index位置的数大; 没有孩子
     * @param arr
     * @param index
     * @param heapSize
     */
    private void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;
        while ( left < heapSize) { // 如果有左孩子
            int right = left + 1;
            // 如果有右孩子,且右孩子值比左孩子值大
            // 选出较大孩子
            int largest = (right < heapSize && arr[right] > arr[left]) ? right : left;
            // 孩子和index对应的值PK，谁大谁给largest
            largest = arr[largest] > arr[index] ? largest : index;
            // 不必下沉
            if (largest == index) {
                break;
            }
            // index 和 较大孩子 largest要互换
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;  // 继续考察左孩子
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public List getAllElements() {
        List ans = new ArrayList<>();
        for (int i = 0; i < heapSize; i++) {
            ans.add(heap[i]);
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] detector = AlgoUtils.LogarithmicDetector(10, 200);
        AlgoUtils.printArray(detector);
        MaxHeap maxHeap = new MaxHeap(20);
        for (int i = 0; i < detector.length; i++) {
            maxHeap.push(detector[i]);
        }
        List elements = maxHeap.getAllElements();
        System.out.println(elements);
    }
}

/*
[ 72, 12, 193, 197, 44, 5, 96, 156 ]
[197, 193, 96, 156, 44, 5, 72, 12]

                    197
                   /   \
                 193   96
                 / \   / \
               156 44  5  72
               /
              12
*/

5.参考

1. 浙大数据结构
2. 左程云算法体系班
3. 掘金

Original: https://www.cnblogs.com/ceeSomething8/p/16185599.html
Author: cee_nil
Title: 大顶堆MaxHeap（原理与Java实现）