堆(Heap)数据结构详解

1. 基本概念

堆是一种特殊的树形数据结构，它满足以下两个关键性质：

1. 结构性质：堆是一棵完全二叉树（Complete Binary Tree），这意味着除了最后一层外，其他层都是满的，且最后一层的节点都尽可能靠左排列。

2. 堆序性质：对于堆中的任意节点，其值必须满足特定的顺序关系：

   • 最大堆（Max Heap）：父节点的值大于或等于其所有子节点的值
   • 最小堆（Min Heap）：父节点的值小于或等于其所有子节点的值

2. 堆的类型

2.1 最大堆（Max Heap）

在最大堆中，根节点是堆中最大的元素。对于任意节点i，其父节点的值大于或等于i的值。

2.2 最小堆（Min Heap）

在最小堆中，根节点是堆中最小的元素。对于任意节点i，其父节点的值小于或等于i的值。

3. 堆的性质和特点

3.1 完全二叉树性质

• 堆总是保持完全二叉树的结构
• 这使得堆可以用数组来高效表示
• 插入和删除操作都能保持这个性质

3.2 堆序性质

• 最大堆保证父节点值 ≥ 子节点值
• 最小堆保证父节点值 ≤ 子节点值
• 这个性质保证了堆顶元素总是最大或最小值

3.3 高效性

• 插入操作：O(log n)
• 删除操作：O(log n)
• 查找最大/最小值：O(1)

4. 堆的数组表示

由于堆是完全二叉树，我们可以用数组来表示它，而不需要显式地存储树结构。这种表示方法非常高效：

• 对于索引为i的节点：
  • 左子节点索引：2i + 1
  • 右子节点索引：2i + 2
  • 父节点索引：(i - 1) // 2

4.1 数组表示示例

索引： 0  1  2  3  4  5  6  7  8
值：   100 19 36 17 3 25 1 2 7

5. 堆的基本操作

5.1 插入操作（Insert）

插入操作需要保持堆的性质：

1. 将新元素添加到堆的末尾
2. 向上调整（Heapify Up/Sift Up）：将新元素与其父节点比较，如果违反堆序性质则交换
3. 重复步骤2直到堆序性质满足

5.2 删除操作（Delete）

通常删除操作是指删除堆顶元素：

1. 将堆顶元素与最后一个元素交换
2. 删除最后一个元素
3. 向下调整（Heapify Down/Sift Down）：将新的堆顶元素与其子节点比较，如果违反堆序性质则交换
4. 重复步骤3直到堆序性质满足

5.3 建堆操作（Build Heap）

从无序数组构建堆：

1. 从最后一个非叶子节点开始
2. 对每个节点执行向下调整
3. 逐步向前处理所有节点

6. 代码实现

6.1 Python实现

class MaxHeap:
    def __init__(self):
        self.heap = []
    
    def parent(self, i):
        return (i - 1) // 2
    
    def left_child(self, i):
        return 2 * i + 1
    
    def right_child(self, i):
        return 2 * i + 2
    
    def insert(self, key):
        self.heap.append(key)
        self._heapify_up(len(self.heap) - 1)
    
    def _heapify_up(self, i):
        while i > 0 and self.heap[self.parent(i)] < self.heap[i]:
            self.heap[self.parent(i)], self.heap[i] = self.heap[i], self.heap[self.parent(i)]
            i = self.parent(i)
    
    def extract_max(self):
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
        
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        return root
    
    def _heapify_down(self, i):
        max_index = i
        left = self.left_child(i)
        right = self.right_child(i)
        
        if left < len(self.heap) and self.heap[left] > self.heap[max_index]:
            max_index = left
        
        if right < len(self.heap) and self.heap[right] > self.heap[max_index]:
            max_index = right
        
        if max_index != i:
            self.heap[i], self.heap[max_index] = self.heap[max_index], self.heap[i]
            self._heapify_down(max_index)
    
    def get_max(self):
        return self.heap[0] if self.heap else None
    
    def size(self):
        return len(self.heap)

class MinHeap:
    def __init__(self):
        self.heap = []
    
    def parent(self, i):
        return (i - 1) // 2
    
    def left_child(self, i):
        return 2 * i + 1
    
    def right_child(self, i):
        return 2 * i + 2
    
    def insert(self, key):
        self.heap.append(key)
        self._heapify_up(len(self.heap) - 1)
    
    def _heapify_up(self, i):
        while i > 0 and self.heap[self.parent(i)] > self.heap[i]:
            self.heap[self.parent(i)], self.heap[i] = self.heap[i], self.heap[self.parent(i)]
            i = self.parent(i)
    
    def extract_min(self):
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
        
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        return root
    
    def _heapify_down(self, i):
        min_index = i
        left = self.left_child(i)
        right = self.right_child(i)
        
        if left < len(self.heap) and self.heap[left] < self.heap[min_index]:
            min_index = left
        
        if right < len(self.heap) and self.heap[right] < self.heap[min_index]:
            min_index = right
        
        if min_index != i:
            self.heap[i], self.heap[min_index] = self.heap[min_index], self.heap[i]
            self._heapify_down(min_index)
    
    def get_min(self):
        return self.heap[0] if self.heap else None
    
    def size(self):
        return len(self.heap)

6.2 Java实现

public class MaxHeap {
    private int[] heap;
    private int size;
    private int maxSize;
    
    public MaxHeap(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 boolean isLeaf(int pos) {
        return pos >= (size / 2) && pos <= size;
    }
    
    public void insert(int element) {
        if (size >= maxSize) {
            return;
        }
        
        heap[size] = element;
        int current = size;
        size++;
        
        while (heap[current] > heap[parent(current)]) {
            swap(current, parent(current));
            current = parent(current);
        }
    }
    
    public int extractMax() {
        if (size <= 0) {
            return Integer.MIN_VALUE;
        }
        if (size == 1) {
            size--;
            return heap[0];
        }
        
        int popped = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0);
        
        return popped;
    }
    
    private void heapifyDown(int pos) {
        if (!isLeaf(pos)) {
            int left = leftChild(pos);
            int right = rightChild(pos);
            int largest = pos;
            
            if (left < size && heap[left] > heap[largest]) {
                largest = left;
            }
            
            if (right < size && heap[right] > heap[largest]) {
                largest = right;
            }
            
            if (largest != pos) {
                swap(pos, largest);
                heapifyDown(largest);
            }
        }
    }
    
    private void swap(int fpos, int spos) {
        int tmp = heap[fpos];
        heap[fpos] = heap[spos];
        heap[spos] = tmp;
    }
}

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 boolean isLeaf(int pos) {
        return pos >= (size / 2) && pos <= size;
    }
    
    public void insert(int element) {
        if (size >= maxSize) {
            return;
        }
        
        heap[size] = element;
        int current = size;
        size++;
        
        while (heap[current] < heap[parent(current)]) {
            swap(current, parent(current));
            current = parent(current);
        }
    }
    
    public int extractMin() {
        if (size <= 0) {
            return Integer.MAX_VALUE;
        }
        if (size == 1) {
            size--;
            return heap[0];
        }
        
        int popped = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0);
        
        return popped;
    }
    
    private void heapifyDown(int pos) {
        if (!isLeaf(pos)) {
            int left = leftChild(pos);
            int right = rightChild(pos);
            int smallest = 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);
                heapifyDown(smallest);
            }
        }
    }
    
    private void swap(int fpos, int spos) {
        int tmp = heap[fpos];
        heap[fpos] = heap[spos];
        heap[spos] = tmp;
    }
}

7. 时间复杂度分析

操作	时间复杂度	说明
插入	O(log n)	向上调整的高度为树的高度
删除	O(log n)	向下调整的高度为树的高度
查找最大/最小值	O(1)	堆顶元素
建堆	O(n)	从数组构建堆的优化算法
堆排序	O(n log n)	利用堆进行排序

8. 堆的应用场景

8.1 优先队列

堆是实现优先队列的理想数据结构，可以高效地获取和删除优先级最高的元素。

8.2 堆排序

堆排序算法利用堆的性质，可以在O(n log n)时间内完成排序。

8.3 Top K问题

在大量数据中找到前K个最大或最小元素。

8.4 图算法

• Dijkstra算法中的优先队列
• Prim算法中的最小生成树

8.5 内存管理

操作系统中的内存分配和回收。

8.6 事件调度

按时间顺序处理事件。

9. 堆的变种

9.1 二叉堆

最常用的堆结构，本文讨论的主要类型。

9.2 斐波那契堆

具有更好理论性能的堆结构，适用于某些特定算法。

9.3 二项堆

由二项树组成的堆结构。

9.4 左偏堆

一种自平衡的二叉堆变体。

10. 总结

堆是一种非常重要的数据结构，它结合了数组的连续存储优势和树结构的有序性。通过完全二叉树的性质，堆能够高效地支持插入、删除和查找操作，特别适合需要频繁获取最大或最小值的场景。理解堆的原理和实现对于算法设计和系统优化都具有重要意义。