堆排序

输入一个长度为n的整数数列，从小到大输出前m小的数。

输入格式

第一行包含整数n和m。

第二行包含n个整数，表示整数数列。

输出格式

共一行，包含m个整数，表示整数数列中前m小的数。

数据范围

输入样例：

5 3
4 5 1 3 2

输出样例：

1 2 3

##############################################################

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 1e5+10;
 5 int arr[N], cnt;
 6 int n, m;
 7 //O(lgn)
 8 void down(int index){
 9     int tmp = index;
10     //在父节点和孩子节点中找到最小的那个节点
11     if(index*2 <= cnt && arr[index*2] < arr[tmp]) tmp = index*2;
12     if(index*2+1 <= cnt && arr[index*2+1] < arr[tmp]) tmp = index*2+1;
13     if(tmp != index){
14         swap(arr[tmp],arr[index]);
15         down(tmp);
16     }
17 }
18 
19 int main(){
20     cin >> n >> m;
21     cnt = n;
22     for(int i = 1; i<= n;++i)cin >> arr[i];
23     for(int i = n >> 1;i;--i)down(i);//建堆,从最底层之上的一层开始down,因为最底层的没有意义，此处复杂度O(n)
24     while(m--){
25         cout << arr[1] << " ";
26         arr[1] = arr[cnt--];
27         down(1);
28     }
29     return 0;
30 }

View Code

模拟堆：

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

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

现在要进行N次操作，对于所有第2个操作，输出当前集合的最小值。

输入格式

第一行包含整数N。

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

输出格式

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

每个结果占一行。

数据范围

输入样例：

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

输出样例：

-10
6

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <string.h>
 4 using namespace std;
 5 
 6 const int N = 1e5+10;
 7 
 8 int arr[N];
 9 int Size;
10 int m;
11 int k_index[N];//表示第k个插入到堆数组中的下标的映射
12 int index_k[N];//表示堆数组中下标到第k个插入的映射
13 
14 void heap_swap(int x, int y){
15     swap(k_index[index_k[x]], k_index[index_k[y]]);            
16     swap(index_k[x], index_k[y]);
17     swap(arr[x], arr[y]);
18 }
19 
20 void down(int p){
21     int t = p;
22     if(p*2 <= Size && arr[p*2] < arr[t]) t = p*2;
23     if(p*2+1 <= Size && arr[p*2+1] < arr[t]) t = p*2 + 1;
24     if(t != p){
25         heap_swap(p,t);
26         down(t);
27     }
28 }
29 /*void up(int u)
30 {
31     while (u / 2 && arr[u] < arr[u / 2])
32     {
33         heap_swap(u, u / 2);
34         u >>= 1;
35     }
36 }
37 */
38 void up(int p){
39     if(p <= Size && p / 2 > 0 && arr[p>>1] > arr[p]){
40         heap_swap(p / 2,p);    
41         up(p / 2); 
42     }  
43 }
44 
45 int main(){
46     int n;
47     cin >> n;
48     while(n--){
49         string op;
50         int k, x;
51         cin >> op;
52         if(op == "I"){
53             cin >> x;
54             ++Size;
55             ++m;
56             k_index[m] = Size;
57             index_k[Size] = m;
58             arr[Size] = x;
59             up(Size);
60         }
61         if(op == "PM")cout << arr[1] << endl;
62         if(op == "DM"){
63             heap_swap(1,Size);
64             --Size;
65             down(1);
66         }
67         if(op == "D"){
68             cin >> k;
69             int t = k_index[k];
70             heap_swap(t,Size);
71             --Size;
72             up(t);
73             down(t);
74         }
75         if(op == "C"){
76             cin >> k >> x;
77             arr[k_index[k]] = x;
78             up(k_index[k]);
79             down(k_index[k]);
80         }
81     }
82     return 0;
83 }

View Code

end