最大堆（Max Heap）是一种特殊的完全二叉树，其中每个节点的值都不小于其子节点的值。最大堆通常用于实现优先队列，因为可以在 (O(\log n)) 时间内完成插入和删除最大元素的操作。

基本性质

1. 完全二叉树：最大堆是一个完全二叉树，这意味着除了最后一层外，其他每一层都被完全填满，并且最后一层的所有节点都尽可能靠左。
2. 堆属性：对于任意节点 (i)，其父节点的值大于或等于其子节点的值。用公式表示为：
   • ( \text{parent}(i) = \left\lfloor \frac{i-1}{2} \right\rfloor )
   • ( \text{left}(i) = 2i + 1 )
   • ( \text{right}(i) = 2i + 2 )
   • ( \text{heap}[i] \geq \text{heap}[\text{left}(i)] ) 且 ( \text{heap}[i] \geq \text{heap}[\text{right}(i)] )

常见操作

1. 插入元素：将新元素添加到堆的末尾，然后通过上滤（heapify up 或 bubble up）操作将其调整到正确的位置。
2. 删除最大元素：移除堆顶元素（最大值），将最后一个元素移到堆顶，然后通过下滤（heapify down 或 sink）操作将其调整到正确的位置。
3. 构建堆：从数组构建最大堆的过程称为堆化（heapify）。

示例代码

以下是使用 Java 实现的最大堆的示例代码：

public class MaxHeap<T extends Comparable<T>> {
    private T[] heap;
    private int size;

    public MaxHeap(int capacity) {
        this.heap = (T[]) new Comparable[capacity];
        this.size = 0;
    }

    // 插入元素
    public void insert(T value) {
        if (size == heap.length) {
            throw new IllegalStateException("Heap is full");
        }
        heap[size] = value;
        siftUp(size);
        size++;
    }

    // 上滤操作
    private void siftUp(int index) {
        while (index > 0 && heap[index].compareTo(heap[parent(index)]) > 0) {
            swap(index, parent(index));
            index = parent(index);
        }
    }

    // 删除最大元素
    public T extractMax() {
        if (size == 0) {
            throw new NoSuchElementException("Heap is empty");
        }
        T max = heap[0];
        heap[0] = heap[--size];
        heap[size] = null;
        siftDown(0);
        return max;
    }

    // 下滤操作
    private void siftDown(int index) {
        while (left(index) < size) {
            int maxChildIndex = getMaxChildIndex(index);
            if (heap[index].compareTo(heap[maxChildIndex]) >= 0) {
                break;
            }
            swap(index, maxChildIndex);
            index = maxChildIndex;
        }
    }

    // 获取左右子节点中较大的子节点索引
    private int getMaxChildIndex(int index) {
        int leftChildIndex = left(index);
        int rightChildIndex = right(index);
        if (rightChildIndex < size && heap[rightChildIndex].compareTo(heap[leftChildIndex]) > 0) {
            return rightChildIndex;
        }
        return leftChildIndex;
    }

    // 交换两个节点的值
    private void swap(int i, int j) {
        T temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // 获取父节点索引
    private int parent(int index) {
        return (index - 1) / 2;
    }

    // 获取左子节点索引
    private int left(int index) {
        return 2 * index + 1;
    }

    // 获取右子节点索引
    private int right(int index) {
        return 2 * index + 2;
    }

    // 构建堆
    public void buildHeap(T[] array) {
        for (int i = 0; i < array.length; i++) {
            heap[i] = array[i];
            size++;
        }
        for (int i = parent(size - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

    // 打印堆
    public void printHeap() {
        for (int i = 0; i < size; i++) {
            System.out.print(heap[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        MaxHeap<Integer> maxHeap = new MaxHeap<>(10);

        maxHeap.insert(3);
        maxHeap.insert(1);
        maxHeap.insert(4);
        maxHeap.insert(1);
        maxHeap.insert(5);
        maxHeap.insert(9);
        maxHeap.insert(2);
        maxHeap.insert(6);
        maxHeap.insert(5);
        maxHeap.insert(3);

        System.out.println("Initial Max Heap:");
        maxHeap.printHeap();

        System.out.println("Extracted Max: " + maxHeap.extractMax());
        System.out.println("Max Heap after extraction:");
        maxHeap.printHeap();

        Integer[] array = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
        MaxHeap<Integer> maxHeap2 = new MaxHeap<>(array.length);
        maxHeap2.buildHeap(array);

        System.out.println("Built Max Heap from array:");
        maxHeap2.printHeap();
    }
}

解释

1. 插入元素：

   • 将新元素添加到堆的末尾。
   • 通过 siftUp 操作将新元素向上调整到正确的位置，以保持堆的性质。

2. 删除最大元素：

   • 移除堆顶元素（最大值）。
   • 将最后一个元素移到堆顶。
   • 通过 siftDown 操作将堆顶元素向下调整到正确的位置，以保持堆的性质。

3. 构建堆：

   • 从数组构建最大堆。
   • 从最后一个非叶子节点开始，逐个进行 siftDown 操作，以确保整个数组满足最大堆的性质。

应用场景

最大堆在以下场景中非常有用：

1. 优先队列：最大堆可以高效地实现优先队列，其中插入和删除最大元素的时间复杂度为 (O(\log n))。
2. 选择算法：最大堆可以用于选择算法，例如找到数组中的第 k 大元素。
3. 堆排序：最大堆可以用于实现堆排序算法，时间复杂度为 (O(n \log n))。

当然，下面是最大堆在不同应用场景中的示例代码和解释。

1. 优先队列

优先队列是一种特殊的数据结构，其中每个元素都有一个优先级，优先级最高的元素最先被取出。最大堆非常适合实现优先队列。

import java.util.NoSuchElementException;

public class PriorityQueue<T extends Comparable<T>> {
    private MaxHeap<T> heap;

    public PriorityQueue(int capacity) {
        heap = new MaxHeap<>(capacity);
    }

    // 插入元素
    public void enqueue(T value) {
        heap.insert(value);
    }

    // 删除并返回优先级最高的元素
    public T dequeue() {
        return heap.extractMax();
    }

    // 检查优先队列是否为空
    public boolean isEmpty() {
        return heap.size == 0;
    }

    // 获取优先队列的大小
    public int size() {
        return heap.size;
    }

    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(10);

        pq.enqueue(3);
        pq.enqueue(1);
        pq.enqueue(4);
        pq.enqueue(1);
        pq.enqueue(5);
        pq.enqueue(9);
        pq.enqueue(2);
        pq.enqueue(6);
        pq.enqueue(5);
        pq.enqueue(3);

        System.out.println("Initial Priority Queue:");
        while (!pq.isEmpty()) {
            System.out.print(pq.dequeue() + " ");
        }
        System.out.println();
    }
}

• 使用最大堆实现优先队列，通过 enqueue 方法插入元素，通过 dequeue 方法删除并返回优先级最高的元素。
• 示例代码展示了如何使用优先队列处理一组整数，并按优先级顺序输出。

2. 选择算法

最大堆可以用于选择算法，例如找到数组中的第 k 大元素。

public class SelectionAlgorithm {
    public static int findKthLargest(int[] nums, int k) {
        MaxHeap<Integer> maxHeap = new MaxHeap<>(nums.length);
        for (int num : nums) {
            maxHeap.insert(num);
        }

        for (int i = 0; i < k - 1; i++) {
            maxHeap.extractMax();
        }

        return maxHeap.extractMax();
    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
        int k = 3;
        int kthLargest = findKthLargest(nums, k);
        System.out.println("The " + k + "rd largest element is: " + kthLargest);
    }
}

• 使用最大堆找到数组中的第 k 大元素。
• 先将所有元素插入最大堆，然后连续提取 k-1 次最大元素，最后提取的元素即为第 k 大元素。
• 示例代码展示了如何找到数组中的第 3 大元素。

3. 堆排序

堆排序是一种基于最大堆的排序算法，时间复杂度为 (O(n \log n))。

public class HeapSort {
    public static void sort(int[] arr) {
        MaxHeap<Integer> maxHeap = new MaxHeap<>(arr.length);
        maxHeap.buildHeap(arr);

        for (int i = 0; i < arr.length; i++) {
            arr[arr.length - 1 - i] = maxHeap.extractMax();
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
        System.out.println("Original array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();

        sort(arr);

        System.out.println("Sorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

• 使用最大堆对数组进行排序。
• 先构建最大堆，然后依次提取最大元素并放入数组的末尾，直到所有元素都被提取。
• 示例代码展示了如何对一组整数进行堆排序。