零基础数据结构与算法——第三章：高级数据结构-堆-EW帮帮网

3.1 树（上）

3.1 树（下）

3.2 堆（Heap）

3.2.1 堆的基本概念

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

结构性：堆是一个完全二叉树，即除了最底层外，其他层的节点都是满的，且最底层的节点都靠左排列。
堆序性：根据堆的类型，节点之间存在特定的大小关系。

堆主要分为两种类型：

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

堆的生活例子

最大堆的例子：想象一个公司的组织结构，CEO在顶部，拥有最高的权力和薪水，下面是各级管理者，权力和薪水依次减少。

最小堆的例子：想象一个任务优先级系统，最紧急的任务（优先级最低的数字）在顶部，随时可以被处理，而不那么紧急的任务在下面等待。

在这里插入图片描述
上图左侧是一个最大堆，右侧是一个最小堆。

堆的特点

高效的最值查找：无论堆的大小如何，获取最大值（最大堆）或最小值（最小堆）的时间复杂度都是O(1)。
高效的插入和删除：插入新元素和删除堆顶元素的时间复杂度都是O(log n)。
完全二叉树结构：可以使用数组高效地存储，不需要使用指针。
自平衡：堆操作会自动维护堆的性质，不需要额外的平衡操作。

3.2.2 堆的操作

堆支持以下基本操作：

插入元素（Insert）：将新元素添加到堆中，并保持堆的性质。
- 时间复杂度：O(log n)
删除堆顶元素（Extract-Min/Extract-Max）：移除并返回堆顶元素（最小值或最大值）。
- 时间复杂度：O(log n)
获取堆顶元素（Get-Min/Get-Max）：返回但不移除堆顶元素。
- 时间复杂度：O(1)
构建堆（Build-Heap）：从一个无序数组构建一个堆。
- 时间复杂度：O(n)

堆操作的生活例子

插入元素：想象一个排队系统，当一个新人到来时，他首先站在队伍的末尾，然后根据他的优先级（例如，老人、孕妇可能有更高的优先级）可能会被移到队伍的前面。

删除堆顶元素：在任务管理系统中，当最紧急的任务被处理完成后，系统会从剩余任务中找出新的最紧急任务放到顶部。

3.2.3 堆的实现（最小堆）

堆通常使用数组来实现，这是因为完全二叉树的结构特性使得数组表示非常高效。对于数组中索引为i的节点：

父节点的索引：(i-1)/2（整数除法）
左子节点的索引：2*i + 1
右子节点的索引：2*i + 2

// 基于数组实现的最小堆
class MinHeap {
    private int[] heap;
    private int size;
    private int capacity;
    
    public MinHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.heap = new int[capacity];
    }
    
    private int parent(int i) {
        return (i - 1) / 2;
    }
    
    private int leftChild(int i) {
        return 2 * i + 1;
    }
    
    private int rightChild(int i) {
        return 2 * i + 2;
    }
    
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
    
    // 向上调整
    private void heapifyUp(int i) {
        while (i > 0 && heap[parent(i)] > heap[i]) {
            swap(parent(i), i);
            i = parent(i);
        }
    }
    
    // 向下调整
    private void heapifyDown(int i) {
        int minIndex = i;
        int left = leftChild(i);
        int right = rightChild(i);
        
        if (left < size && heap[left] < heap[minIndex]) {
            minIndex = left;
        }
        
        if (right < size && heap[right] < heap[minIndex]) {
            minIndex = right;
        }
        
        if (i != minIndex) {
            swap(i, minIndex);
            heapifyDown(minIndex);
        }
    }
    
    // 插入元素
    public void insert(int key) {
        if (size == capacity) {
            System.out.println("Heap is full");
            return;
        }
        
        // 在末尾插入新元素
        heap[size] = key;
        size++;
        
        // 向上调整以维护堆性质
        heapifyUp(size - 1);
    }
    
    // 获取并删除最小元素
    public int extractMin() {
        if (size <= 0) {
            System.out.println("Heap is empty");
            return Integer.MAX_VALUE;
        }
        
        if (size == 1) {
            size--;
            return heap[0];
        }
        
        int root = heap[0];
        heap[0] = heap[size - 1];
        size--;
        
        // 向下调整以维护堆性质
        heapifyDown(0);
        
        return root;
    }
    
    // 获取最小元素但不删除
    public int getMin() {
        if (size <= 0) {
            System.out.println("Heap is empty");
            return Integer.MAX_VALUE;
        }
        return heap[0];
    }
}

3.2.4 堆的应用场景

优先队列的实现
堆排序
图算法（如Dijkstra算法、Prim算法）
中位数和百分位数计算
任务调度

堆的应用场景详解

优先级队列：堆是实现优先级队列的理想数据结构，可以高效地获取最高或最低优先级的元素。
- 例如：操作系统的任务调度、网络路由中的数据包优先级处理。
堆排序：使用堆可以实现时间复杂度为O(n log n)的排序算法。
- 例如：对大量数据进行排序，如数据库查询结果的排序。
图算法：在Dijkstra最短路径算法和Prim最小生成树算法中，堆用于高效地选择下一个要处理的节点。
- 例如：GPS导航系统中的路径规划。
中位数和百分位数计算：使用一个最大堆和一个最小堆可以高效地维护一组动态数据的中位数。
- 例如：数据流的实时统计分析。
内存管理：操作系统中的内存分配器可以使用堆来跟踪可用内存块。
- 例如：垃圾收集器中的内存管理。

零基础数据结构与算法——第三章：高级数据结构-堆