深入理解堆(Heap)数据结构

1. 堆的基本概念

堆是一种特殊的完全二叉树，分为大根堆（大顶堆）和小根堆（小顶堆）：

• 大根堆（大顶堆）：父节点的值总是大于或等于子节点的值
• 小根堆（小顶堆）：父节点的值总是小于或等于子节点的值

堆通常用数组实现，对于数组中的第i个节点：

• 其左子节点的位置：2i + 1
• 其右子节点的位置：2i + 2
• 其父节点的位置：(i - 1) / 2

2. 堆的基本实现

下面是一个小根堆的Java实现：

public class MinHeap {
    private int[] heap;
    private int size;
    private int maxSize;

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

    private int parent(int pos) { return (pos - 1) / 2; }
    private int leftChild(int pos) { return (2 * pos) + 1; }
    private int rightChild(int pos) { return (2 * pos) + 2; }

    private void swap(int pos1, int pos2) {
        int temp = heap[pos1];
        heap[pos1] = heap[pos2];
        heap[pos2] = temp;
    }

    public void insert(int element) {
        if (size >= maxSize) {
            throw new IllegalStateException("Heap is full");
        }

        heap[size] = element;
        int current = size;
        
        while (heap[current] < heap[parent(current)]) {
            swap(current, parent(current));
            current = parent(current);
        }
        size++;
    }

    public int extractMin() {
        if (size <= 0) {
            throw new IllegalStateException("Heap is empty");
        }

        int min = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapify(0);

        return min;
    }

    private void heapify(int pos) {
        int smallest = pos;
        int left = leftChild(pos);
        int right = rightChild(pos);

        if (left < size && heap[left] < heap[smallest])
            smallest = left;

        if (right < size && heap[right] < heap[smallest])
            smallest = right;

        if (smallest != pos) {
            swap(pos, smallest);
            heapify(smallest);
        }
    }
}

3. 堆的常见应用场景

3.1 TopK问题

问题描述：从一组数中找出最大/最小的k个数。

解决思路：

1. 对于找最大的k个数，我们使用小根堆
2. 维护一个大小为k的小根堆
3. 遍历数组，当堆的大小小于k时，直接插入；当堆的大小等于k时，将当前元素与堆顶比较，如果大于堆顶则替换

public static int[] findTopK(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
    for (int num : nums) {
        if (minHeap.size() < k) {
            minHeap.offer(num);
        } else if (num > minHeap.peek()) {
            minHeap.poll();
            minHeap.offer(num);
        }
    }
    
    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) {
        result[i] = minHeap.poll();
    }
    return result;
}

3.2 数据流中的中位数

问题描述：设计一个数据结构，支持动态添加整数，并能随时获取当前所有数据的中位数。

解决思路：

1. 使用两个堆：大根堆存储较小的一半数，小根堆存储较大的一半数
2. 保持两个堆的大小差不超过1
3. 中位数即为：当总数为奇数时，多的那个堆的堆顶；当总数为偶数时，两个堆顶的平均值

public class MedianFinder {
    private PriorityQueue<Integer> maxHeap; // 存储较小的一半
    private PriorityQueue<Integer> minHeap; // 存储较大的一半
    
    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a, b) -> b - a);
        minHeap = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        if (maxHeap.size() >= minHeap.size()) {
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        } else {
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        }
    }
    
    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        } else if (minHeap.size() > maxHeap.size()) {
            return minHeap.peek();
        }
        return (maxHeap.peek() + minHeap.peek()) / 2.0;
    }
}

3.3 合并K个有序链表

问题描述：给定k个有序链表，将它们合并成一个有序链表。

解决思路：

1. 创建一个小根堆，存储每个链表的头节点
2. 每次从堆中取出最小的节点加入结果链表
3. 如果被取出的节点还有下一个节点，将下一个节点加入堆中

public class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
    
    // 将所有链表的头节点加入堆
    for (ListNode list : lists) {
        if (list != null) {
            minHeap.offer(list);
        }
    }
    
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    
    while (!minHeap.isEmpty()) {
        ListNode node = minHeap.poll();
        tail.next = node;
        tail = tail.next;
        
        if (node.next != null) {
            minHeap.offer(node.next);
        }
    }
    
    return dummy.next;
}

4. 堆的性能分析

• 插入操作：O(log n)
• 删除堆顶操作：O(log n)
• 获取堆顶元素：O(1)
• 建堆操作：O(n)

5. 堆的优化技巧

1. 延迟删除：在需要频繁删除的场景中，可以使用标记删除而不是真正删除，等到必要时再进行实际的删除操作。

2. 索引堆：在需要修改堆中元素值的场景，可以使用索引堆，避免查找元素的O(n)开销。

3. 批量建堆：当需要插入多个元素时，可以先将所有元素放入数组，然后自底向上建堆，这样比一个个插入更快。

6. 总结

堆是一种极其重要的数据结构，尤其在需要维护动态有序集合时非常有用。它的主要优势在于：

1. 能在O(1)时间内获取最值
2. 能在O(log n)时间内动态维护有序性
3. 空间效率高，使用数组即可实现

在实际应用中，Java的PriorityQueue就是用堆实现的，它提供了一个完整且高效的优先队列实现。在解决TopK、数据流处理、贪心算法等问题时，堆常常是最优的选择。