堆排序（838，839）（堆中的元素编号与插入堆的插入序号相映射）

838. 堆排序

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

输入一个长度为 n

的整数数列，从小到大输出前 m

小的数。

输入格式

第一行包含整数 n

和 m

。

第二行包含 n

个整数，表示整数数列。

输出格式

共一行，包含 m

个整数，表示整数数列中前 m

小的数。

数据范围

1≤m≤n≤105

，
1≤数列中元素≤109

输入样例：

5 3
4 5 1 3 2

输出样例：

1 2 3

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int maxn = 1e5+10;
int heap[maxn],sz;
 
void down(int l,int h)
{
    int par=l,chi=2*par;
    while(chi<=sz)
    {
        if(chi < sz && heap[chi+1]<heap[chi])
            ++chi;
        if(heap[chi] < heap[par])
        {
            swap(heap[chi],heap[par]);
            par=chi;
            chi=2*par;
        }
        else
            break;
    }
}
 
void create()
{
    for(int i=sz/2;i>0;--i)
        down(i,sz);
}
 
 
int top()
{
    return heap[1];
}
 
void pop()
{
    swap(heap[1],heap[sz]);
    --sz;
    down(1,sz);
}
 
 
int main()
{
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;++i)   cin >> heap[i];
    sz=n;
    
    create();
    
    for(int i=0;i<m;++i)
    {
        cout << top() << ' ';
        pop();
    }
    
    return 0;
}

839. 模拟堆

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

维护一个集合，初始时集合为空，支持如下几种操作：

1. I x，插入一个数 x

• ；
• PM，输出当前集合中的最小值；
• DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
• D k，删除第 k
• 个插入的数；
• C k x，修改第 k
• 个插入的数，将其变为 x
  1. ；

  现在要进行 N

  次操作，对于所有第 2

  个操作，输出当前集合的最小值。

  输入格式

  第一行包含整数 N

  。

  接下来 N

  行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。

  输出格式

  对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。

  每个结果占一行。

  数据范围

  1≤N≤105

  
  −109≤x≤109

  
  数据保证合法。

  输入样例：

  8
  I -10
  PM
  I -10
  D 1
  C 2 8
  I 6
  PM
  DM
  

  输出样例：

  -10
  6
  

 

* I x，插入一个数 x ： heap[++sz]=x,up(1,sz);
 * PM，输出当前集合中的最小值: heap[1];
 * DM，删除当前集合中的最小值 ： swap(heap[1],heap[sz])，--sz；
 * D k，删除第 k个插入的数：swap(heap[k],heap[sz]),--sz; 但此时要注意，第k个
 * 插入的数并不是堆中第k号位的元素；
 * C k x，修改第 k个插入的数，将其变为 x；heap[k]=x; 此时第k个插入的数也不是
 * 堆中第k号位的元素；
 *
 * 在插入元素或者删除元素或者修改元素的值，都需要调整堆的元素位置，以满足
 * 堆的特性；
 *
 * 因此需要找出第k个插入的数在堆中的位置编号；同时也要反映出堆中第u号位的数
 * 是第几个插进来的数；所以我们需要开两个映射数组来反映出这两种信息；
 *
 * 在进行堆的元素交换的时候，我们需要把映射数组的信息也进行交换，即：
 *   void heap_swap(int u,int v)
     {
        swap(ph[hp[u]],ph[hp[v]]);
        swap(hp[u],hp[v]);
        swap(heap[u],heap[v]);
     }
 
 画一根二叉树模拟一下就能理解了；

/**
 * I x，插入一个数 x ： heap[++sz]=x,up(1,sz);
 * PM，输出当前集合中的最小值: heap[1];
 * DM，删除当前集合中的最小值 ： swap(heap[1],heap[sz])，--sz；
 * D k，删除第 k个插入的数：swap(heap[k],heap[sz]),--sz; 但此时要注意，第k个
 * 插入的数并不是堆中第k号位的元素；
 * C k x，修改第 k个插入的数，将其变为 x；heap[k]=x; 此时第k个插入的数也不是
 * 堆中第k号位的元素；
 * 
 * 在插入元素或者删除元素或者修改元素的值，都需要调整堆的元素位置，以满足
 * 堆的特性；
 * 
 * 因此需要找出第k个插入的数在堆中的位置编号；同时也要反映出堆中第u号位的数
 * 是第几个插进来的数；所以我们需要开两个映射数组来反映出这两种信息；
 * 
 * 在进行堆的元素交换的时候，我们需要把映射数组的信息也进行交换，即：
 *   void heap_swap(int u,int v)
     {
        swap(ph[hp[u]],ph[hp[v]]); 
        swap(hp[u],hp[v]);
        swap(heap[u],heap[v]);
     }
 
 画一根二叉树模拟一下就能理解了；
*/
 
#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int maxn = 1e5+10;
int heap[maxn],sz;
int ph[maxn],hp[maxn];
 
//堆的第u号和第v号元素进行交换，要把ph数组和hp数组对应的元素也进行交换，
//以能够为后续的删除或者修改操作找到正确的修改位置；
void heap_swap(int u,int v) 
{
    swap(ph[hp[u]],ph[hp[v]]);
    swap(hp[u],hp[v]);
    swap(heap[u],heap[v]);
}
 
void down(int l,int r)  //对[l,r]内的值进行向下调整
{
    int par=l,chi=2*par;
    while(chi<=r)
    {
        if(chi<r && heap[chi+1]<heap[chi])
            ++chi;
        if(heap[chi] < heap[par])
        {
            heap_swap(chi,par);
            par=chi;
            chi=2*par;
        }
        else
            break;
    }
}
 
void up(int l,int r)//对[l,r]内的值进行向上调整
{
    int chi=r,par=chi/2;
    while(par>=l && heap[chi]<heap[par])
    {
        heap_swap(chi,par);
        chi=par;
        par=chi/2;
    }
}
 
int main()
{
    int n,idx=0;
    cin >> n;
    
    while (n -- )
    {
        string op;
        int k,x;
        
        cin >> op;
        if(op == "I")
        {
            cin >> x;
            heap[++sz]=x;
            ++idx;
            ph[idx]=sz;
            hp[sz]=idx;
            up(1,sz);
        }
        else if(op == "PM")
            cout << heap[1] << endl;
        else if(op == "DM")
        {
            heap_swap(1,sz);
            --sz;
            down(1,sz);
        }
        else if(op == "D")
        {
            cin >> k;
            k=ph[k];
            heap_swap(k,sz);
            --sz;
            down(k,sz);
            up(1,k);
        }
        else
        {
            cin >> k >> x;
            k=ph[k];
            heap[k]=x;
            down(k,sz);
            up(1,k);
        }
    }
    
    return 0;
}