# 12. 堆

## 概念

**堆（Heap）** 是一种特殊的**完全二叉树**，并且满足**堆序性**：

- **最大堆（大顶堆）**：每个结点的值 **不小于** 其孩子的值，因此堆顶（根）是**最大值**。
- **最小堆（小顶堆）**：每个结点的值 **不大于** 其孩子的值，因此堆顶是**最小值**。

**用数组存储**：因为堆是完全二叉树，可以紧凑地用数组存储，无需指针。若数组下标**从 0 开始**，对下标为 `i` 的结点：

- 父结点下标：`(i - 1) / 2`
- 左孩子下标：`2 * i + 1`
- 右孩子下标：`2 * i + 2`

（若下标从 1 开始，则父为 `i/2`，左子 `2i`，右子 `2i+1`。本文统一使用从 0 开始。）

**性质**：堆只保证堆顶是最大/最小值，并不保证整个序列有序；兄弟结点之间没有大小关系约束。堆序性只沿"祖先-子孙"路径成立。

**适用场景**：

- **优先队列（Priority Queue）**：每次取最值，插入任意值，都是 O(log n)。
- **堆排序**：利用堆顶最值，反复取出堆顶排序，O(n log n)。
- **TopK 问题**：如求 n 个数中最大的 k 个，用大小为 k 的最小堆维护，扫描一遍即可。

## 核心操作

- **建堆（自底向上）**：从最后一个非叶结点（下标 `n/2 - 1`）开始，向前对每个结点做"下沉"（sift down），最终整个数组满足堆序。时间复杂度 **O(n)**。
- **插入（上浮，sift up）**：把新元素放到数组末尾，然后不断与父结点比较，若违反堆序则与父交换，向上浮动到合适位置。
- **删除堆顶（下沉）**：把堆顶与最后一个元素交换，删除末尾，然后对新的堆顶做"下沉"（sift down），恢复堆序。通常配合返回被删的最大/最小值。
- **取堆顶**：直接返回数组下标 0 的元素，O(1)。

## 复杂度分析

| 操作             | 时间复杂度 | 空间复杂度   |
| ---------------- | ---------- | ------------ |
| 建堆（自底向上） | O(n)       | O(1)（原地） |
| 插入（上浮）     | O(log n)   | O(1)         |
| 删除堆顶（下沉） | O(log n)   | O(1)         |
| 取堆顶           | O(1)       | O(1)         |

**为什么**：

- 建堆时从最后一个非叶结点自底向上做下沉。每个结点下沉的代价正比于它下降的高度，但大部分结点位于树的下层、下沉次数少，累加起来总和为 O(n)（这是与逐次插入 O(n log n) 的关键区别）。
- 插入上浮、删除下沉都只沿"根到叶子"的一条路径移动，路径长度 = 树高 = O(log n)，每步交换 O(1)，故 O(log n)。
- 取堆顶只读数组首元素，O(1)。所有操作均为原地、无需额外数组，故空间 O(1)（递归下沉栈空间不计入）。

## 语言实现

下面是 4 种语言的完整**最大堆**实现，均演示：建堆、插入、删除最大、取最大。Python 额外提及内置的 `heapq` 模块（其默认实现为最小堆）。

### C

```c
#include <stdio.h>
#include <stdlib.h>

// 最大堆结构体
typedef struct {
    int *arr;    // 数组
    int size;    // 当前元素个数
    int cap;     // 容量
} MaxHeap;

// 从 0 开始的父子下标
int parent(int i)  { return (i - 1) / 2; }
int left(int i)    { return 2 * i + 1; }
int right(int i)   { return 2 * i + 2; }

MaxHeap *createHeap(int cap) {
    MaxHeap *h = (MaxHeap *)malloc(sizeof(MaxHeap));
    h->arr = (int *)malloc(sizeof(int) * cap);
    h->size = 0;
    h->cap = cap;
    return h;
}

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

// 下沉：把下标 i 的元素下移到合适位置
void siftDown(MaxHeap *h, int i) {
    int largest = i;
    int l = left(i), r = right(i);
    if (l < h->size && h->arr[l] > h->arr[largest]) largest = l;
    if (r < h->size && h->arr[r] > h->arr[largest]) largest = r;
    if (largest != i) {
        swap(&h->arr[i], &h->arr[largest]);
        siftDown(h, largest);
    }
}

// 上浮：把下标 i 的元素上移到合适位置
void siftUp(MaxHeap *h, int i) {
    while (i > 0 && h->arr[parent(i)] < h->arr[i]) {
        swap(&h->arr[parent(i)], &h->arr[i]);
        i = parent(i);
    }
}

// 建堆：从最后一个非叶结点开始自底向上下沉
void buildHeap(MaxHeap *h, int *a, int n) {
    for (int i = 0; i < n; i++) h->arr[i] = a[i];
    h->size = n;
    for (int i = n / 2 - 1; i >= 0; i--)
        siftDown(h, i);
}

// 插入
void insert(MaxHeap *h, int val) {
    if (h->size >= h->cap) return;
    h->arr[h->size] = val;
    siftUp(h, h->size);
    h->size++;
}

// 取最大（堆顶）
int peek(MaxHeap *h) {
    return h->arr[0];
}

// 删除最大并返回
int extractMax(MaxHeap *h) {
    int max = h->arr[0];
    h->arr[0] = h->arr[h->size - 1];
    h->size--;
    siftDown(h, 0);
    return max;
}

void printHeap(MaxHeap *h) {
    for (int i = 0; i < h->size; i++) printf("%d ", h->arr[i]);
    printf("\n");
}

int main() {
    int a[] = {3, 1, 6, 5, 2, 4};
    int n = 6;
    MaxHeap *h = createHeap(20);
    buildHeap(h, a, n);            // 建堆
    printf("建堆后: ");
    printHeap(h);

    insert(h, 10);                 // 插入
    printf("插入 10 后: ");
    printHeap(h);

    printf("堆顶(最大): %d\n", peek(h));

    printf("删除最大 %d 后: ", extractMax(h));
    printHeap(h);
    printf("再次删除最大 %d 后: ", extractMax(h));
    printHeap(h);
    return 0;
}
```

### C++

```C++
#include <iostream>
#include <vector>
using namespace std;

// 最大堆（基于 vector）
class MaxHeap {
private:
    vector<int> arr;
    int parent(int i) { return (i - 1) / 2; }
    int left(int i)   { return 2 * i + 1; }
    int right(int i)  { return 2 * i + 2; }

    // 下沉
    void siftDown(int i) {
        int n = arr.size();
        int largest = i;
        int l = left(i), r = right(i);
        if (l < n && arr[l] > arr[largest]) largest = l;
        if (r < n && arr[r] > arr[largest]) largest = r;
        if (largest != i) {
            swap(arr[i], arr[largest]);
            siftDown(largest);
        }
    }

    // 上浮
    void siftUp(int i) {
        while (i > 0 && arr[parent(i)] < arr[i]) {
            swap(arr[parent(i)], arr[i]);
            i = parent(i);
        }
    }

public:
    MaxHeap() {}
    // 用数组建堆
    MaxHeap(const vector<int>& a) {
        arr = a;
        for (int i = (int)arr.size() / 2 - 1; i >= 0; i--)
            siftDown(i);
    }
    void insert(int val) {
        arr.push_back(val);
        siftUp(arr.size() - 1);
    }
    int peek() const { return arr[0]; }
    int extractMax() {
        int maxv = arr[0];
        arr[0] = arr.back();
        arr.pop_back();
        siftDown(0);
        return maxv;
    }
    void print() const {
        for (int x : arr) cout << x << " ";
        cout << endl;
    }
};

int main() {
    MaxHeap h({3, 1, 6, 5, 2, 4});   // 建堆
    cout << "建堆后: ";
    h.print();

    h.insert(10);                     // 插入
    cout << "插入 10 后: ";
    h.print();

    cout << "堆顶(最大): " << h.peek() << endl;

    cout << "删除最大 " << h.extractMax() << " 后: ";
    h.print();
    cout << "再次删除最大 " << h.extractMax() << " 后: ";
    h.print();
    return 0;
}
```

### Java

```java
import java.util.*;

public class MaxHeap {
    private int[] arr;
    private int size;

    public MaxHeap(int cap) { arr = new int[cap]; size = 0; }

    // 从数组建堆
    public MaxHeap(int[] a) {
        arr = Arrays.copyOf(a, Math.max(a.length, 16));
        size = a.length;
        for (int i = size / 2 - 1; i >= 0; i--) siftDown(i);
    }

    private int parent(int i) { return (i - 1) / 2; }
    private int left(int i)   { return 2 * i + 1; }
    private int right(int i)  { return 2 * i + 2; }

    // 下沉
    private void siftDown(int i) {
        int largest = i;
        int l = left(i), r = right(i);
        if (l < size && arr[l] > arr[largest]) largest = l;
        if (r < size && arr[r] > arr[largest]) largest = r;
        if (largest != i) {
            int t = arr[i]; arr[i] = arr[largest]; arr[largest] = t;
            siftDown(largest);
        }
    }

    // 上浮
    private void siftUp(int i) {
        while (i > 0 && arr[parent(i)] < arr[i]) {
            int t = arr[parent(i)]; arr[parent(i)] = arr[i]; arr[i] = t;
            i = parent(i);
        }
    }

    public void insert(int val) {
        if (size == arr.length) arr = Arrays.copyOf(arr, arr.length * 2);
        arr[size] = val;
        siftUp(size);
        size++;
    }

    public int peek() { return arr[0]; }

    public int extractMax() {
        int max = arr[0];
        arr[0] = arr[size - 1];
        size--;
        siftDown(0);
        return max;
    }

    public void print() {
        for (int i = 0; i < size; i++) System.out.print(arr[i] + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        MaxHeap h = new MaxHeap(new int[]{3, 1, 6, 5, 2, 4}); // 建堆
        System.out.print("建堆后: ");
        h.print();

        h.insert(10);                                          // 插入
        System.out.print("插入 10 后: ");
        h.print();

        System.out.println("堆顶(最大): " + h.peek());

        System.out.print("删除最大 " + h.extractMax() + " 后: ");
        h.print();
        System.out.print("再次删除最大 " + h.extractMax() + " 后: ");
        h.print();
    }
}
```

### Python

```python
class MaxHeap:
    """最大堆（基于列表实现）"""

    def __init__(self, a=None):
        self.arr = list(a) if a else []
        if a:
            self._build()

    @staticmethod
    def _parent(i): return (i - 1) // 2
    @staticmethod
    def _left(i):   return 2 * i + 1
    @staticmethod
    def _right(i):  return 2 * i + 2

    def _sift_down(self, i):
        """下沉"""
        n = len(self.arr)
        while True:
            largest = i
            l, r = self._left(i), self._right(i)
            if l < n and self.arr[l] > self.arr[largest]:
                largest = l
            if r < n and self.arr[r] > self.arr[largest]:
                largest = r
            if largest == i:
                break
            self.arr[i], self.arr[largest] = self.arr[largest], self.arr[i]
            i = largest

    def _sift_up(self, i):
        """上浮"""
        while i > 0 and self.arr[self._parent(i)] < self.arr[i]:
            self.arr[self._parent(i)], self.arr[i] = self.arr[i], self.arr[self._parent(i)]
            i = self._parent(i)

    def _build(self):
        """自底向上建堆"""
        for i in range(len(self.arr) // 2 - 1, -1, -1):
            self._sift_down(i)

    def insert(self, val):
        self.arr.append(val)
        self._sift_up(len(self.arr) - 1)

    def peek(self):
        return self.arr[0]

    def extract_max(self):
        """删除并返回最大元素"""
        maxv = self.arr[0]
        self.arr[0] = self.arr[-1]
        self.arr.pop()
        self._sift_down(0)
        return maxv

    def __repr__(self):
        return " ".join(map(str, self.arr))


if __name__ == "__main__":
    h = MaxHeap([3, 1, 6, 5, 2, 4])     # 建堆
    print("建堆后:", h)

    h.insert(10)                         # 插入
    print("插入 10 后:", h)

    print("堆顶(最大):", h.peek())
    print("删除最大", h.extract_max(), "后:", h)
    print("再次删除最大", h.extract_max(), "后:", h)

    # Python 内置 heapq 模块：默认是最小堆
    import heapq
    data = [3, 1, 6, 5, 2, 4]
    heapq.heapify(data)                 # 原地建最小堆
    print("heapq 建堆:", data)
    heapq.heappush(data, 0)             # 插入
    print("heapq 插入 0 后:", data)
    print("heapq 弹出最小:", heapq.heappop(data))
    # 如需最大堆，可把元素取负存入
```