数据结构与算法完整教程

// O(n) — 循环一次
for (int i = 0; i < n; i++) {
    printf("%d\n", i);
}

// O(n²) — 嵌套循环
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        printf("%d %d\n", i, j);
    }
}

// O(log n) — 每次砍一半
int i = n;
while (i > 1) {
    i = i / 2;       // 比如二分查找
}

// O(1) — 管你 n 多大，我一步完事
int x = arr[5];      // 数组下标访问

// O(1) 空间 — 只用了几个变量
int sum(int arr[], int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += arr[i];
    }
    return total;
}

// O(n) 空间 — 新建了一个等长数组
int* double_arr(int arr[], int n) {
    int* result = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        result[i] = arr[i] * 2;
    }
    return result;  // 调用者负责 free
}

T(n) = a × T(n/b) + f(n)

情况1：f(n) = O(n^(log_b(a) - ε))   →  T(n) = Θ(n^(log_b(a)))
情况2：f(n) = Θ(n^(log_b(a)))       →  T(n) = Θ(n^(log_b(a)) × log n)
情况3：f(n) = Ω(n^(log_b(a) + ε))   →  T(n) = Θ(f(n))

         A           ← 根节点 (root)
        / \
       B   C         ← 内部节点 (internal node)
      / \   \
     D   E   F       ← 叶节点 (leaf node)

// ===== C 版 =====
typedef struct TreeNode {
    int val;
    struct TreeNode* first_child;   // 第一个孩子
    struct TreeNode* next_sibling;  // 下一个兄弟
} TreeNode;

// ===== C++ 版 =====
struct TreeNode {
    int val;
    TreeNode* first_child = nullptr;
    TreeNode* next_sibling = nullptr;
};

// C++ 推荐
#include <vector>
struct TreeNode {
    int val;
    std::vector<TreeNode*> children;
};

// ===== C 版 =====
typedef struct BinTreeNode {
    int val;
    struct BinTreeNode* left;
    struct BinTreeNode* right;
} BinTreeNode;

// 创建节点
BinTreeNode* create_node(int val) {
    BinTreeNode* node = (BinTreeNode*)malloc(sizeof(BinTreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// ===== C++ 版 =====
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

      1
     / \
    2   3
   / \   \
  4   5   6

前序 (根左右): 1 2 4 5 3 6
中序 (左根右): 4 2 5 1 3 6
后序 (左右根): 4 5 2 6 3 1
层序 (bfs):   1 2 3 4 5 6

// ===== C 版：递归 =====
void preorder(BinTreeNode* root) {
    if (!root) return;
    printf("%d ", root->val);
    preorder(root->left);
    preorder(root->right);
}

void inorder(BinTreeNode* root) {
    if (!root) return;
    inorder(root->left);
    printf("%d ", root->val);
    inorder(root->right);
}

void postorder(BinTreeNode* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->val);
}

// ===== C++ 版：递归 =====
void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

// ===== C 版：迭代前序 =====
// 栈：先压右再压左，弹出时先左后右
void preorder_iter(BinTreeNode* root) {
    if (!root) return;
    BinTreeNode** stack = (BinTreeNode**)malloc(100 * sizeof(BinTreeNode*));
    int top = -1;
    stack[++top] = root;
    while (top >= 0) {
        BinTreeNode* node = stack[top--];
        printf("%d ", node->val);
        if (node->right) stack[++top] = node->right;
        if (node->left)  stack[++top] = node->left;
    }
    free(stack);
}

// ===== C 版：迭代中序（一路往左走）=====
void inorder_iter(BinTreeNode* root) {
    BinTreeNode** stack = (BinTreeNode**)malloc(100 * sizeof(BinTreeNode*));
    int top = -1;
    BinTreeNode* cur = root;
    while (cur || top >= 0) {
        while (cur) {                    // 一路走到最左
            stack[++top] = cur;
            cur = cur->left;
        }
        cur = stack[top--];              // 弹出最左
        printf("%d ", cur->val);
        cur = cur->right;                // 转向右子树
    }
    free(stack);
}

// ===== C 版：迭代后序（前序(根右左) 反转）=====
void postorder_iter(BinTreeNode* root) {
    if (!root) return;
    int* result = (int*)malloc(100 * sizeof(int));  // 存结果
    int idx = 0;
    BinTreeNode** stack = (BinTreeNode**)malloc(100 * sizeof(BinTreeNode*));
    int top = -1;
    stack[++top] = root;
    while (top >= 0) {
        BinTreeNode* node = stack[top--];
        result[idx++] = node->val;       // 存放（根右左顺序）
        if (node->left)  stack[++top] = node->left;
        if (node->right) stack[++top] = node->right;
    }
    // 反转输出
    for (int i = idx - 1; i >= 0; i--) {
        printf("%d ", result[i]);
    }
    free(result);
    free(stack);
}

// ===== C++ 版：迭代（用 STL stack）=====
#include <stack>
#include <vector>

void preorder_iter(TreeNode* root) {
    if (!root) return;
    std::stack<TreeNode*> stk;
    stk.push(root);
    while (!stk.empty()) {
        TreeNode* node = stk.top(); stk.pop();
        cout << node->val << " ";
        if (node->right) stk.push(node->right);
        if (node->left)  stk.push(node->left);
    }
}

void inorder_iter(TreeNode* root) {
    std::stack<TreeNode*> stk;
    TreeNode* cur = root;
    while (cur || !stk.empty()) {
        while (cur) {
            stk.push(cur);
            cur = cur->left;
        }
        cur = stk.top(); stk.pop();
        cout << cur->val << " ";
        cur = cur->right;
    }
}

void postorder_iter(TreeNode* root) {
    if (!root) return;
    std::vector<int> result;
    std::stack<TreeNode*> stk;
    stk.push(root);
    while (!stk.empty()) {
        TreeNode* node = stk.top(); stk.pop();
        result.push_back(node->val);
        if (node->left)  stk.push(node->left);
        if (node->right) stk.push(node->right);
    }
    for (auto it = result.rbegin(); it != result.rend(); ++it) {
        cout << *it << " ";
    }
}

// ===== 层序遍历 (BFS) =====
// C 版：用数组模拟队列
#include <stdio.h>
#include <stdlib.h>

void level_order(BinTreeNode* root) {
    if (!root) return;
    BinTreeNode** queue = (BinTreeNode**)malloc(100 * sizeof(BinTreeNode*));
    int front = 0, rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        BinTreeNode* node = queue[front++];
        printf("%d ", node->val);
        if (node->left)  queue[rear++] = node->left;
        if (node->right) queue[rear++] = node->right;
    }
    free(queue);
}

// C++ 版：用 std::queue
#include <queue>
void level_order(TreeNode* root) {
    if (!root) return;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front(); q.pop();
        cout << node->val << " ";
        if (node->left)  q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

// ===== C 版 =====
#include <stdio.h>
#include <stdlib.h>

typedef struct BSTNode {
    int val;
    struct BSTNode* left;
    struct BSTNode* right;
} BSTNode;

BSTNode* bst_create(int val) {
    BSTNode* node = (BSTNode*)malloc(sizeof(BSTNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

// 查找：一路比大小
BSTNode* bst_search(BSTNode* root, int val) {
    BSTNode* cur = root;
    while (cur) {
        if (val == cur->val)
            return cur;
        else if (val < cur->val)
            cur = cur->left;
        else
            cur = cur->right;
    }
    return NULL;
}

// 插入
BSTNode* bst_insert(BSTNode* root, int val) {
    if (!root) return bst_create(val);
    BSTNode* cur = root;
    while (1) {
        if (val < cur->val) {
            if (cur->left)
                cur = cur->left;
            else {
                cur->left = bst_create(val);
                break;
            }
        } else {
            if (cur->right)
                cur = cur->right;
            else {
                cur->right = bst_create(val);
                break;
            }
        }
    }
    return root;
}

// 找最小值
BSTNode* bst_min(BSTNode* node) {
    while (node->left) node = node->left;
    return node;
}

// 删除
BSTNode* bst_delete(BSTNode* root, int val) {
    if (!root) return NULL;
    if (val < root->val)
        root->left = bst_delete(root->left, val);
    else if (val > root->val)
        root->right = bst_delete(root->right, val);
    else {
        // 情况1+2：0个或1个孩子
        if (!root->left) {
            BSTNode* tmp = root->right;
            free(root);
            return tmp;
        }
        if (!root->right) {
            BSTNode* tmp = root->left;
            free(root);
            return tmp;
        }
        // 情况3：两个小孩 → 找后继（右子树最小），替换
        BSTNode* successor = bst_min(root->right);
        root->val = successor->val;
        root->right = bst_delete(root->right, successor->val);
    }
    return root;
}

// ===== C++ 版 =====
class BST {
public:
    struct Node {
        int val;
        Node* left;
        Node* right;
        Node(int x) : val(x), left(nullptr), right(nullptr) {}
    };

    Node* root = nullptr;

    Node* search(int val) {
        Node* cur = root;
        while (cur) {
            if (val == cur->val) return cur;
            cur = (val < cur->val) ? cur->left : cur->right;
        }
        return nullptr;
    }

    void insert(int val) {
        if (!root) { root = new Node(val); return; }
        Node* cur = root;
        while (true) {
            if (val < cur->val) {
                if (cur->left) cur = cur->left;
                else { cur->left = new Node(val); break; }
            } else {
                if (cur->right) cur = cur->right;
                else { cur->right = new Node(val); break; }
            }
        }
    }

    Node* _min(Node* node) {
        while (node->left) node = node->left;
        return node;
    }

    Node* _delete(Node* node, int val) {
        if (!node) return nullptr;
        if (val < node->val)
            node->left = _delete(node->left, val);
        else if (val > node->val)
            node->right = _delete(node->right, val);
        else {
            if (!node->left)  { Node* tmp = node->right; delete node; return tmp; }
            if (!node->right) { Node* tmp = node->left;  delete node; return tmp; }
            Node* succ = _min(node->right);
            node->val = succ->val;
            node->right = _delete(node->right, succ->val);
        }
        return node;
    }

    void remove(int val) { root = _delete(root, val); }
};

// ===== C 版 =====
typedef struct AVLNode {
    int val;
    struct AVLNode* left;
    struct AVLNode* right;
    int height;
} AVLNode;

AVLNode* avl_create(int val) {
    AVLNode* node = (AVLNode*)malloc(sizeof(AVLNode));
    node->val = val;
    node->left = node->right = NULL;
    node->height = 1;
    return node;
}

int height(AVLNode* n) { return n ? n->height : 0; }
int max(int a, int b) { return a > b ? a : b; }
int balance_factor(AVLNode* n) { return n ? height(n->left) - height(n->right) : 0; }

void update_height(AVLNode* n) {
    n->height = 1 + max(height(n->left), height(n->right));
}

// 右旋
AVLNode* rotate_right(AVLNode* y) {
    AVLNode* x = y->left;
    AVLNode* T2 = x->right;
    x->right = y;
    y->left = T2;
    update_height(y);
    update_height(x);
    return x;
}

// 左旋
AVLNode* rotate_left(AVLNode* x) {
    AVLNode* y = x->right;
    AVLNode* T2 = y->left;
    y->left = x;
    x->right = T2;
    update_height(x);
    update_height(y);
    return y;
}

AVLNode* avl_insert(AVLNode* node, int val) {
    // 1. 普通 BST 插入
    if (!node) return avl_create(val);
    if (val < node->val)
        node->left = avl_insert(node->left, val);
    else if (val > node->val)
        node->right = avl_insert(node->right, val);
    else
        return node;  // 重复值不管

    // 2. 更新高度
    update_height(node);

    // 3. 检查平衡 + 旋转
    int balance = balance_factor(node);

    // LL
    if (balance > 1 && val < node->left->val)
        return rotate_right(node);
    // RR
    if (balance < -1 && val > node->right->val)
        return rotate_left(node);
    // LR
    if (balance > 1 && val > node->left->val) {
        node->left = rotate_left(node->left);
        return rotate_right(node);
    }
    // RL
    if (balance < -1 && val < node->right->val) {
        node->right = rotate_right(node->right);
        return rotate_left(node);
    }
    return node;
}

// ===== C++ 版 =====
struct AVLNode {
    int val;
    AVLNode* left;
    AVLNode* right;
    int height;
    AVLNode(int x) : val(x), left(nullptr), right(nullptr), height(1) {}
};

int get_height(AVLNode* n) { return n ? n->height : 0; }
int get_balance(AVLNode* n) { return n ? get_height(n->left) - get_height(n->right) : 0; }

AVLNode* rotate_right(AVLNode* y) {
    AVLNode* x = y->left;
    AVLNode* T2 = x->right;
    x->right = y;
    y->left = T2;
    y->height = 1 + std::max(get_height(y->left), get_height(y->right));
    x->height = 1 + std::max(get_height(x->left), get_height(x->right));
    return x;
}

AVLNode* rotate_left(AVLNode* x) {
    AVLNode* y = x->right;
    AVLNode* T2 = y->left;
    y->left = x;
    x->right = T2;
    x->height = 1 + std::max(get_height(x->left), get_height(x->right));
    y->height = 1 + std::max(get_height(y->left), get_height(y->right));
    return y;
}

AVLNode* avl_insert(AVLNode* node, int val) {
    if (!node) return new AVLNode(val);
    if (val < node->val)
        node->left = avl_insert(node->left, val);
    else if (val > node->val)
        node->right = avl_insert(node->right, val);
    else
        return node;

    node->height = 1 + std::max(get_height(node->left), get_height(node->right));
    int balance = get_balance(node);

    if (balance > 1 && val < node->left->val)   // LL
        return rotate_right(node);
    if (balance < -1 && val > node->right->val)  // RR
        return rotate_left(node);
    if (balance > 1 && val > node->left->val) {  // LR
        node->left = rotate_left(node->left);
        return rotate_right(node);
    }
    if (balance < -1 && val < node->right->val) { // RL
        node->right = rotate_right(node->right);
        return rotate_left(node);
    }
    return node;
}

LL:   y             x
     / \           / \
    x   T4   →    T1  y
   / \               / \
  T1 T2             T2 T4

LR:   z             z            x
     / \           / \          / \
    y   T4   →    x   T4   →   y   z
   / \           / \          / \ / \
  T1  x         y  T3       T1 T2 T3 T4
     / \       / \
    T2 T3     T1 T2

RR:   x             y
     / \           / \
   T1   y    →    x  T4
       / \       / \
      T2 T4     T1 T2

RL:   z             z             x
     / \           / \           / \
   T1   y    →   T1   x    →    z   y
       / \           / \       / \ / \
      x  T4         T2  y    T1 T2 T3 T4
     / \               / \
    T2 T3             T3 T4

// ===== C 版 =====
#include <stdio.h>
#include <stdlib.h>

#define RED   1
#define BLACK 0

typedef struct RBNode {
    int val;
    int color;
    struct RBNode* left;
    struct RBNode* right;
    struct RBNode* parent;
} RBNode;

RBNode* NIL;  // 哨兵节点（全局，黑色叶节点）

RBNode* rb_create(int val, int color) {
    RBNode* node = (RBNode*)malloc(sizeof(RBNode));
    node->val = val;
    node->color = color;
    node->left = NIL;
    node->right = NIL;
    node->parent = NULL;
    return node;
}

void rb_init() {
    NIL = (RBNode*)malloc(sizeof(RBNode));
    NIL->color = BLACK;
    NIL->left = NIL->right = NIL->parent = NULL;
}

void rb_left_rotate(RBNode** root, RBNode* x) {
    RBNode* y = x->right;
    x->right = y->left;
    if (y->left != NIL) y->left->parent = x;
    y->parent = x->parent;
    if (!x->parent) *root = y;
    else if (x == x->parent->left) x->parent->left = y;
    else x->parent->right = y;
    y->left = x;
    x->parent = y;
}

void rb_right_rotate(RBNode** root, RBNode* y) {
    RBNode* x = y->left;
    y->left = x->right;
    if (x->right != NIL) x->right->parent = y;
    x->parent = y->parent;
    if (!y->parent) *root = x;
    else if (y == y->parent->right) y->parent->right = x;
    else y->parent->left = x;
    x->right = y;
    y->parent = x;
}

void rb_insert_fixup(RBNode** root, RBNode* z) {
    while (z->parent && z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            RBNode* y = z->parent->parent->right;  // 叔叔
            if (y->color == RED) {                    // 情况1：叔叔红
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->right) {          // 情况2
                    z = z->parent;
                    rb_left_rotate(root, z);
                }
                z->parent->color = BLACK;             // 情况3
                z->parent->parent->color = RED;
                rb_right_rotate(root, z->parent->parent);
            }
        } else {  // 对称
            RBNode* y = z->parent->parent->left;
            if (y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    rb_right_rotate(root, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rb_left_rotate(root, z->parent->parent);
            }
        }
    }
    (*root)->color = BLACK;
}

void rb_insert(RBNode** root, int val) {
    RBNode* z = rb_create(val, RED);
    RBNode* y = NULL;
    RBNode* x = *root;
    while (x != NIL) {
        y = x;
        x = (val < x->val) ? x->left : x->right;
    }
    z->parent = y;
    if (!y) *root = z;
    else if (val < y->val) y->left = z;
    else y->right = z;
    rb_insert_fixup(root, z);
}

// ===== C++ 版 =====
#include <iostream>
enum Color { RED, BLACK };

template<typename T>
struct RBNode {
    T val;
    Color color;
    RBNode *left, *right, *parent;
    RBNode(T x) : val(x), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

template<typename T>
class RedBlackTree {
    RBNode<T>* root;
    RBNode<T>* NIL;  // 哨兵

    void left_rotate(RBNode<T>* x) {
        RBNode<T>* y = x->right;
        x->right = y->left;
        if (y->left != NIL) y->left->parent = x;
        y->parent = x->parent;
        if (!x->parent) root = y;
        else if (x == x->parent->left) x->parent->left = y;
        else x->parent->right = y;
        y->left = x;
        x->parent = y;
    }

    void right_rotate(RBNode<T>* y) {
        RBNode<T>* x = y->left;
        y->left = x->right;
        if (x->right != NIL) x->right->parent = y;
        x->parent = y->parent;
        if (!y->parent) root = x;
        else if (y == y->parent->right) y->parent->right = x;
        else y->parent->left = x;
        x->right = y;
        y->parent = x;
    }

    void insert_fixup(RBNode<T>* z) {
        while (z->parent && z->parent->color == RED) {
            if (z->parent == z->parent->parent->left) {
                RBNode<T>* y = z->parent->parent->right;
                if (y->color == RED) {
                    z->parent->color = BLACK;
                    y->color = BLACK;
                    z->parent->parent->color = RED;
                    z = z->parent->parent;
                } else {
                    if (z == z->parent->right) {
                        z = z->parent;
                        left_rotate(z);
                    }
                    z->parent->color = BLACK;
                    z->parent->parent->color = RED;
                    right_rotate(z->parent->parent);
                }
            } else {
                RBNode<T>* y = z->parent->parent->left;
                if (y->color == RED) {
                    z->parent->color = BLACK;
                    y->color = BLACK;
                    z->parent->parent->color = RED;
                    z = z->parent->parent;
                } else {
                    if (z == z->parent->left) {
                        z = z->parent;
                        right_rotate(z);
                    }
                    z->parent->color = BLACK;
                    z->parent->parent->color = RED;
                    left_rotate(z->parent->parent);
                }
            }
        }
        root->color = BLACK;
    }

public:
    RedBlackTree() {
        NIL = new RBNode<T>(0);
        NIL->color = BLACK;
        NIL->left = NIL->right = NIL->parent = nullptr;
        root = NIL;
    }

    void insert(T val) {
        RBNode<T>* z = new RBNode<T>(val);
        z->left = z->right = NIL;
        RBNode<T>* y = nullptr;
        RBNode<T>* x = root;
        while (x != NIL) {
            y = x;
            x = (val < x->val) ? x->left : x->right;
        }
        z->parent = y;
        if (!y) root = z;
        else if (val < y->val) y->left = z;
        else y->right = z;
        insert_fixup(z);
    }
};

最小堆规则：父 ≤ 子（根最小）
数组：父 (i-1)/2，左子 2i+1，右子 2i+2

        1
       / \
      3   5
     / \ /
    7  9 6

// ===== C 版：最小堆 =====
typedef struct {
    int* data;
    int size;
    int capacity;
} MinHeap;

MinHeap* heap_create(int cap) {
    MinHeap* h = (MinHeap*)malloc(sizeof(MinHeap));
    h->data = (int*)malloc(cap * sizeof(int));
    h->size = 0;
    h->capacity = cap;
    return h;
}

void heap_sift_up(MinHeap* h, int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (h->data[i] < h->data[parent]) {
            int tmp = h->data[i];
            h->data[i] = h->data[parent];
            h->data[parent] = tmp;
            i = parent;
        } else break;
    }
}

void heap_sift_down(MinHeap* h, int i) {
    while (1) {
        int smallest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < h->size && h->data[left] < h->data[smallest])
            smallest = left;
        if (right < h->size && h->data[right] < h->data[smallest])
            smallest = right;
        if (smallest == i) break;
        int tmp = h->data[i];
        h->data[i] = h->data[smallest];
        h->data[smallest] = tmp;
        i = smallest;
    }
}

void heap_push(MinHeap* h, int val) {
    if (h->size >= h->capacity) return;  // 需要扩容，简化处理
    h->data[h->size] = val;
    heap_sift_up(h, h->size);
    h->size++;
}

int heap_pop(MinHeap* h) {
    if (h->size == 0) return -1;
    int val = h->data[0];
    h->data[0] = h->data[--h->size];
    if (h->size > 0) heap_sift_down(h, 0);
    return val;
}

int heap_top(MinHeap* h) { return h->size > 0 ? h->data[0] : -1; }

// O(n) 建堆：从最后一个非叶节点向前 sift_down
void heap_build(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        // sift_down on arr[i]
        int cur = i;
        while (1) {
            int smallest = cur;
            int left = 2 * cur + 1;
            int right = 2 * cur + 2;
            if (left < n && arr[left] < arr[smallest]) smallest = left;
            if (right < n && arr[right] < arr[smallest]) smallest = right;
            if (smallest == cur) break;
            int tmp = arr[cur];
            arr[cur] = arr[smallest];
            arr[smallest] = tmp;
            cur = smallest;
        }
    }
}

// ===== C++ 版 =====
#include <queue>
#include <vector>

// STL 直接调：默认大顶堆
std::priority_queue<int> max_heap;
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

max_heap.push(5);
int top = max_heap.top();
max_heap.pop();

// 手写
class MinHeap {
    std::vector<int> data;
public:
    void push(int val) {
        data.push_back(val);
        int i = data.size() - 1;
        while (i > 0) {
            int p = (i - 1) / 2;
            if (data[i] < data[p]) {
                std::swap(data[i], data[p]);
                i = p;
            } else break;
        }
    }

    int pop() {
        if (data.empty()) return -1;
        int val = data[0];
        data[0] = data.back();
        data.pop_back();
        int i = 0, n = data.size();
        while (true) {
            int smallest = i;
            int l = 2 * i + 1, r = 2 * i + 2;
            if (l < n && data[l] < data[smallest]) smallest = l;
            if (r < n && data[r] < data[smallest]) smallest = r;
            if (smallest == i) break;
            std::swap(data[i], data[smallest]);
            i = smallest;
        }
        return val;
    }

    int top() { return data.empty() ? -1 : data[0]; }
    bool empty() { return data.empty(); }
};

// C 版：哈夫曼编码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct HuffNode {
    char ch;
    int freq;
    struct HuffNode* left;
    struct HuffNode* right;
} HuffNode;

// 用最小堆来构造（简单起见，直接选最小的两个）
HuffNode* build_huffman(char chars[], int freqs[], int n) {
    // 把每个字符做成节点，放到"森林"里
    HuffNode** nodes = (HuffNode**)malloc(n * sizeof(HuffNode*));
    for (int i = 0; i < n; i++) {
        nodes[i] = (HuffNode*)malloc(sizeof(HuffNode));
        nodes[i]->ch = chars[i];
        nodes[i]->freq = freqs[i];
        nodes[i]->left = nodes[i]->right = NULL;
    }

    int size = n;
    while (size > 1) {
        // 找最小和次小的两个
        int min1 = 0, min2 = 1;
        if (nodes[min1]->freq > nodes[min2]->freq) {
            int tmp = min1; min1 = min2; min2 = tmp;
        }
        for (int i = 2; i < size; i++) {
            if (nodes[i]->freq < nodes[min1]->freq) {
                min2 = min1;
                min1 = i;
            } else if (nodes[i]->freq < nodes[min2]->freq) {
                min2 = i;
            }
        }

        // 合并
        HuffNode* parent = (HuffNode*)malloc(sizeof(HuffNode));
        parent->ch = '\0';
        parent->freq = nodes[min1]->freq + nodes[min2]->freq;
        parent->left = nodes[min1];
        parent->right = nodes[min2];

        // 替换掉 min1，删除 min2
        nodes[min1] = parent;
        nodes[min2] = nodes[size - 1];
        size--;
    }

    HuffNode* root = nodes[0];
    free(nodes);
    return root;
}

void print_codes(HuffNode* root, char* code, int depth) {
    if (!root->left && !root->right) {
        code[depth] = '\0';
        printf("  %c : %s\n", root->ch, code);
        return;
    }
    code[depth] = '0';
    print_codes(root->left, code, depth + 1);
    code[depth] = '1';
    print_codes(root->right, code, depth + 1);
}

// 使用示例：
// char chars[] = {'a','b','c','d','e','f'};
// int freqs[]  = {45, 13, 12, 16, 9, 5};
// HuffNode* tree = build_huffman(chars, freqs, 6);
// char code[100];
// print_codes(tree, code, 0);

    0 --- 1
    |  \  |
    |   \ |
    3 --- 2

// ===== 1. 邻接矩阵 — O(V²)，稠密图 =====
#define MAX_V 100
int graph[MAX_V][MAX_V];  // 0=无边, 1=有边 (或存权重)

// 访问: graph[0][1] = 1 表示 0→1 有边

// ===== 2. 邻接表 — O(V+E)，最常用 =====
// C 版
#define MAX_V 100

typedef struct EdgeNode {
    int dest;
    int weight;
    struct EdgeNode* next;
} EdgeNode;

typedef struct {
    EdgeNode* head;
} AdjList[MAX_V];

void add_edge(AdjList graph, int src, int dest) {
    EdgeNode* node = (EdgeNode*)malloc(sizeof(EdgeNode));
    node->dest = dest;
    node->weight = 1;
    node->next = graph[src].head;
    graph[src].head = node;
}

// C++ 版
#include <vector>
#include <utility>
std::vector<std::pair<int, int>> adj[100];  // adj[u] = {(v, w), ...}

void add_edge(int u, int v, int w = 1) {
    adj[u].push_back({v, w});
}

// ===== 3. 边列表 — O(E)，Kruskal 用 =====
struct Edge {
    int u, v, w;
};
std::vector<Edge> edges = {{0,1,4}, {0,2,1}, {1,3,1}, {2,1,2}};

// ===== C 版 =====
#include <stdbool.h>

bool visited[MAX_V];

void dfs_c(AdjList graph, int v) {
    visited[v] = true;
    printf("%d ", v);
    for (EdgeNode* e = graph[v].head; e; e = e->next) {
        if (!visited[e->dest]) {
            dfs_c(graph, e->dest);
        }
    }
}

void dfs_all(AdjList graph, int V) {
    memset(visited, 0, sizeof(visited));
    for (int i = 0; i < V; i++) {
        if (!visited[i]) dfs_c(graph, i);
    }
}

// ===== C++ 版 =====
#include <vector>
using namespace std;

void dfs(vector<int> adj[], int v, bool visited[]) {
    visited[v] = true;
    cout << v << " ";
    for (int neighbor : adj[v]) {
        if (!visited[neighbor]) dfs(adj, neighbor, visited);
    }
}

// 迭代版（栈）
void dfs_iter(vector<int> adj[], int start, int V) {
    bool visited[V] = {false};
    stack<int> stk;
    stk.push(start);
    while (!stk.empty()) {
        int v = stk.top(); stk.pop();
        if (!visited[v]) {
            visited[v] = true;
            cout << v << " ";
            // 倒序压栈，顺序不变
            for (auto it = adj[v].rbegin(); it != adj[v].rend(); ++it) {
                if (!visited[*it]) stk.push(*it);
            }
        }
    }
}