最大堆、最小堆数据结构详细解读

最大堆、最小堆数据结构详细解读

引用

CSDN

1.

https://blog.csdn.net/m0_61840987/article/details/143624484

堆是一种重要的数据结构，广泛应用于优先队列、排序算法、调度系统等场景。本文将详细介绍最大堆和最小堆的定义、特性、核心操作及其应用场景。

最大堆（Max Heap）与最小堆（Min Heap）

堆（Heap）是一种特殊的完全二叉树，它满足以下两个特性：

1. 结构特性：堆必须是完全二叉树（Complete Binary Tree）。即除了最后一层之外，其他层都必须完全填满，且最后一层的节点从左向右连续排列。
2. 堆特性：

• 最大堆（Max Heap）：每个节点的值都大于或等于其子节点的值。
• 最小堆（Min Heap）：每个节点的值都小于或等于其子节点的值。

堆广泛用于优先队列、排序算法（如堆排序）、调度系统等场景。下面是对最大堆和最小堆的详细介绍。

一、最大堆（Max Heap）

1. 定义

• 最大堆是一种完全二叉树，满足堆特性：每个节点的值都大于或等于其子节点的值。
• 因此，堆顶元素（根节点）是整个堆中的最大值。

2. 结构示意图
   

• 根节点 50 是堆中的最大值。
• 对于任意节点，其值都大于或等于其子节点的值。

3. 核心操作

• 插入（Insert）：

  1. 将新元素插入堆的最后一个位置。
  2. 通过上浮（Percolate Up）调整堆的顺序，直到满足堆特性。

• 删除最大元素（Extract Max）：

  1. 取出堆顶元素（最大值）。
  2. 将堆的最后一个元素移动到堆顶。
  3. 通过下沉（Percolate Down）调整堆的顺序，直到满足堆特性。

4. 代码实现（Java 示例）

import java.util.Arrays;

class MaxHeap {
    private int[] heap;
    private int size;
    private int capacity;

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

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

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

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

    // 上浮操作
    private void percolateUp(int index) {
        while (index > 0 && heap[parent(index)] < heap[index]) {
            swap(index, parent(index));
            index = parent(index);
        }
    }

    // 下沉操作
    private void percolateDown(int index) {
        int largest = index;
        int left = leftChild(index);
        int right = rightChild(index);
        if (left < size && heap[left] > heap[largest]) {
            largest = left;
        }
        if (right < size && heap[right] > heap[largest]) {
            largest = right;
        }
        if (largest != index) {
            swap(index, largest);
            percolateDown(largest);
        }
    }

    // 插入元素
    public void insert(int value) {
        if (size == capacity) throw new RuntimeException("Heap is full");
        heap[size] = value;
        size++;
        percolateUp(size - 1);
    }

    // 删除最大元素
    public int extractMax() {
        if (size == 0) throw new RuntimeException("Heap is empty");
        int max = heap[0];
        heap[0] = heap[size - 1];
        size--;
        percolateDown(0);
        return max;
    }

    // 交换元素
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // 打印堆
    public void printHeap() {
        System.out.println(Arrays.toString(Arrays.copyOfRange(heap, 0, size)));
    }
}

public class MaxHeapTest {
    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);
        maxHeap.insert(50);
        maxHeap.insert(30);
        maxHeap.insert(20);
        maxHeap.insert(15);
        maxHeap.insert(10);
        maxHeap.insert(5);
        maxHeap.insert(8);
        maxHeap.printHeap(); // 输出: [50, 30, 20, 15, 10, 5, 8]
        
        System.out.println("Extract Max: " + maxHeap.extractMax()); // 输出: 50
        maxHeap.printHeap(); // 输出: [30, 15, 20, 8, 10, 5]
    }
}

5. 时间复杂度

• 插入操作：O(log⁡n)
• 删除最大元素：O(log⁡n)
• 查找最大元素：O(1)

二、最小堆（Min Heap）

1. 定义

• 最小堆是一种完全二叉树，满足堆特性：每个节点的值都小于或等于其子节点的值。
• 因此，堆顶元素（根节点）是整个堆中的最小值。

2. 结构示意图

• 根节点 5 是堆中的最小值。
• 对于任意节点，其值都小于或等于其子节点的值。

3. 核心操作

• 插入（Insert）：

  1. 将新元素插入堆的最后一个位置。
  2. 通过上浮（Percolate Up）调整堆的顺序，直到满足堆特性。

• 删除最小元素（Extract Min）：

  1. 取出堆顶元素（最小值）。
  2. 将堆的最后一个元素移动到堆顶。
  3. 通过下沉（Percolate Down）调整堆的顺序，直到满足堆特性。

4. 代码实现（Java 示例）

class MinHeap {
    private int[] heap;
    private int size;
    private int capacity;

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

    private int parent(int index) {
        return (index - 1) / 2;
    }

    private int leftChild(int index) {
        return 2 * index + 1;
    }

    private int rightChild(int index) {
        return 2 * index + 2;
    }

    private void percolateUp(int index) {
        while (index > 0 && heap[parent(index)] > heap[index]) {
            swap(index, parent(index));
            index = parent(index);
        }
    }

    private void percolateDown(int index) {
        int smallest = index;
        int left = leftChild(index);
        int right = rightChild(index);
        if (left < size && heap[left] < heap[smallest]) {
            smallest = left;
        }
        if (right < size && heap[right] < heap[smallest]) {
            smallest = right;
        }
        if (smallest != index) {
            swap(index, smallest);
            percolateDown(smallest);
        }
    }

    public void insert(int value) {
        if (size == capacity) throw new RuntimeException("Heap is full");
        heap[size] = value;
        size++;
        percolateUp(size - 1);
    }

    public int extractMin() {
        if (size == 0) throw new RuntimeException("Heap is empty");
        int min = heap[0];
        heap[0] = heap[size - 1];
        size--;
        percolateDown(0);
        return min;
    }

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

5. 时间复杂度

• 插入操作：O(log⁡n)
• 删除最小元素：O(log⁡n)
• 查找最小元素：O(1)

三、最大堆与最小堆的应用

堆的特性使其在许多场景下非常有用，如调度系统、事件模拟、动态中位数维护等。