堆的功能

• 插入一个数 \(O(log_2n)\)
  • heap[++size] = x 然后不断往上移 up(size)
• 求集合当中的最小值 \(O(1)\)
  • heap[1]
• 删除最小值 \(O(log_2n)\)
  • heap[1] = heap[size--] 堆最后一个元素覆盖堆顶元素，然后 down(1)
  • 因为删除头结点非常困难，删除尾结点很easy
• 删除任意一个元素（STL没直接实现，优先队列） \(O(log_2n)\)
  • heap[k] = heap[size--] 有三种情况，可直接 down(k) 再 up(k)，只会执行一个
• 修改任意一个元素（STL没直接实现，优先队列） \(O(log_2n)\)
  • heap[k] = x 再 down(k) 、up(k)

838 ?

838. 堆排序 - AcWing题库

一个一个往里插是 \(O(nlog_2n)\) 。可以采用 \(O(n)\) 的方式，先全部读入，除最后一层外反着down操作（倒第2层，倒第3层...第1层）（可用数列推导出，每个节点down的次数总和 < n）（记忆）

    for (int i = n / 2; i; i--) {
        down(i);
    }

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int h[N], idx;

void down(int u) {
    int t = u;
    if (u * 2 <= idx && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= idx && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t) {
        swap(h[t], h[u]);
        down(t);
    }
}

int main() {
    cin.tie(0);
    cin >> n >> m;
    int x;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }
    idx = n;

    for (int i = n / 2; i; i--) {
        down(i);
    }

    while (m--) {
        cout << h[1] << " ";
        h[1] = h[idx--];
        down(1);
    }

    return 0;
}

839 ??

839. 模拟堆 - AcWing题库

存储映射：ph 存第k个插入的点在堆里的下标，hp 存堆里点的坐标是第k个插入的，两者互为相反关系。

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int h[N], hp[N], ph[N], idx;

void new_swap(int a, int b) {
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void up(int x) {
    while (x / 2 && h[x / 2] > h[x]) {
        new_swap(x / 2, x);
        x /= 2;
    }
}

void down(int x) {
    int t = x;
    if (2 * x <= idx && h[2 * x] < h[t]) t = 2 * x;
    if (2 * x + 1 <= idx && h[2 * x + 1] < h[t]) t = 2 * x + 1;
    if (t != x) {
        new_swap(x, t);
        down(t);
    }
}

int main() {
    cin.tie(0);
    int n;
    cin >> n;
    int count = 0;
    while (n--) {
        string s;
        int k, x;
        cin >> s;
        if (s == "I") {
            cin >> x;
            idx++;
            count++;
            h[idx] = x;
            hp[idx] = count;
            ph[count] = idx;
            up(idx);
        } else if (s == "PM") {
            cout << h[1] << endl;
        } else if (s == "DM") {
            // ^ h[1] = h[idx--];  // 这样只交换点,没交换ph hp
            new_swap(1, idx--);
            down(1);
        } else if (s == "D") {
            cin >> k;
            // ^ h[ph[k]] = h[idx--]; // 这样只交换点,没交换ph hp
            k = ph[k];  // 获取第k个插入的数在堆中的坐标
            new_swap(k, idx--);
            down(k), up(k);  // 只会执行其中一个
        } else if (s == "C") {
            cin >> k >> x;
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
    }

    return 0;
}

哈希表

情景

• 把 1e5 个值域 -1e9~1e9 的数（值域大，个数少）映射到 1e5 的范围的哈希函数
• \(h(x) \in (0,1e5) = x\ mod\ 1e5\) 模数一般要取质数，离2的整数幂尽可能远
• 发生冲突：两个不同值域的数映射成了同一个数

存储结构-解决冲突的方式 ?

算法题99%一般只有添加、查找，若要实现删除不会真删掉，开一个bool数组标记删除

• 开放寻址法（常用）
  • 开一个一维数组，范围是题目数据范围的2~3倍，即 2e5 ~ 3e5 区间的质数，该数组存储实际的 x 值
  • 计算哈希值，如果哈希值已被占用，则移动到下一个位置，从前往后找
  • h(11) = 3 在 数组[3] 存入 11，h(4) = 3 在数组[4] 存入 4
  • 与拉链法不同，查询函数返回 x 所在的位置，如果 x 不存在返回应该存储的位置
  • 需要约定一个标志，不在 x 的值域范围内，表示当前位置为空，如 0x3f3f3f3f
• 拉链法
  • 开一个一维数组 \([0,大于1e5的最小质数]\) 存储所有哈希值对应的链表
  • h(11) = 3 在 数组[3] 开一条链，插入 11
  • 若 h(4) = 3 在 数组[3] 已开的链插入 4
  • 期望情况下，每条链长度 1，时间复杂度 \(O(1)\)

字符串哈希-字符串前缀哈希法（特殊）

应用：可以快速判断一个字符串某两段是否相同。KMP望而却步（KMP擅长循环节），极困难题可用这种方法

• 先预处理所有前缀的哈希，h[0] = 0, h[1] = "A" 的hash，h[2] = "AB" 的hash...

  • 把字符串看成 P 进制的数，然后模 Q
  

• **某个字符不能映射成 0，否则 AA 跟 A 两个哈希都是 0 **

• 该哈希法假定人品足够好，不考虑冲突

• 经验值：当 p = 131 或 13331，Q 取 \(2^{64}\) (用 unsinged long long可以不取模，溢出相当于取模)