堆.md

堆

操作：

1. 插入一个元素：在最后一个位置插入元素，然后上浮
2. 求取集合中的最小值：输出数组中第一个元素
3. 删除集合中的最小值：用数组中最后一个元素覆盖掉第一个元素，然后下沉
4. 删除任意一个值：用数组最后一个元素覆盖掉需要被删除的元素，然后上浮/下沉
5. 修改任意一个值：修改对应元素的，然后上浮/下沉

堆是一颗完全二叉树

小根堆：每一个点都小于等于左右孩子结点的值

存储方式：一维数组（二叉树的顺序存储），x为该数组（数组从下标为1开始）中的一个元素，如果x有左右孩子，则左孩子为2x，右孩子为2x + 1

//838. 堆排序(ACWing)
//输入一个长度为 n 的整数数列，从小到大输出前 m 小的数
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int tail , h[N];

void down(int x)
{
    int t = x;
    if(x * 2 <= tail && h[t] > h[x * 2])
        t = x * 2;
    if(x * 2 + 1 <= tail && h[t] > h[x * 2 + 1])        //找三个数中最小的并交换
        t = x * 2 + 1;
    if(t != x)
    {
        swap(h[x] , h[t]);
        down(t);
    }
}

int main()
{
    int n , m;
    cin >> n >> m;
    
    tail = n;
    for(int i = 1 ; i <= n ; i ++)
        cin >> h[i];
    
    for(int i = n / 2 ; i >= 1 ; i --)
        down(i);
    
    while(m --)
    {
        cout << h[1] << ' ';
        h[1] = h[tail];
        tail --;
        down(1);
    }
    return 0;
}

1. 需要注意的是在down函数中，不是用 h[x] > h[x * 2] 来进行判断，而是用 h[t] > h[x * 2] 来进行判断，这样做是为了找到三个数中的最小数，使用 h[x] > h[x * 2] 就会有逻辑上的错误

2. for(int i = n / 2 ; i >= 1 ; i --)
   	down(i);

   这个循环是将数组中的元素构造成堆，i从 n / 2开始可以是时间复杂度降到O(n)

---

//模拟堆
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;
int tail , h[N] , p[N] , q[N];      //q存的是第x个位置上的元素是第几个插入的数，p存的是第k个插入的数在第几个位置

void heap_swap(int a , int b)
{
    swap(p[q[a]] , p[q[b]]);
    swap(q[a] , q[b]);
    swap(h[a] , h[b]);
}

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

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

int main()
{
    int n;
    cin >> n;
    
    int m = 0;              //插入的数的次序
    while(n --)
    {
        int k , x; 
        string u;
        cin >> u;
        if(u == "I")
        {
            cin >> x;
            m ++;
            tail ++;
            h[tail] = x;
            p[m] = tail;
            q[tail] = m;
            up(tail);
        }
        else if(u == "PM")
            cout << h[1] << endl;
        else if(u == "DM")
        {
            heap_swap(1 , tail);
            tail --;
            down(1);
        }
        else if(u == "D")
        {
            cin >> k;
            k = p[k];
            heap_swap(k , tail);
            tail --;
            down(k) , up(k);        //最多只执行其中一个函数
        }
        else
        {
            cin >> k >> x;
            k = p[k];
            h[k] = x;
            down(k) , up(k);
        }
    }
    return 0;
}

需要理解的是 p[N] & q[N]:

1. k表示该元素是第几个被插入到数组，p[k] = 该元素在数组中的实际位置
2. i表示该元素在数组中的实际位置，q[i] = 该元素被插入的次序