堆排序模板题
堆是一颗完全二叉树, 根节点小于等于左右两个子节点的值, 然后递归定义.
这个题考察堆的下沉操作.
注意, 把一个元素个数是$n$的数组变成堆的时间复杂度是$O(n)$, 直接从$\frac{n}{2}$下沉到1即可.
- 完全二叉树除了最后一层, 上面所有层的元素个数是$\frac{n}{2}$, 那么根据这个关系, 倒数第二层的元素个数是$\frac{n}{4}$.
- 倒数第二层元素个数是$\frac{n}{4}$, 需要下沉1层.
- 倒数第三层的元素个数是$\frac{n}{8}$, 需要下沉2层
- 倒数第四层元素个数是$\frac{n}{16}$, 需要下沉3层…
把这些加起来, 会发现它们其实和$O(n)$一个级别.
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
/* s是堆中的元素个数 */
int heap[N], s;
/* 下沉操作 */
void down(int u)
{
int t = u;
if (2 * u <= s && heap[2 * u] < heap[t]) t = 2 * u;
if (2 * u + 1 <= s && heap[2 * u + 1] < heap[t]) t = 2 * u + 1;
if (t != u)
{
swap(heap[t], heap[u]);
down(t);
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> heap[i];
s = n;
/* O(n)建堆 */
for (int i = n / 2; i >= 1; i --) down(i);
while (m --)
{
cout << heap[1] << ' ';
heap[1] = heap[s --];
down(1);
}
return 0;
}
索引优先队列模板题
堆的一些操作的实现方式:
- 插入: 插入到最后然后上浮.
- 删除最小值: 让最后一个元素和第一个元素交换, 然后
size --, 然后让第一个元素下沉.
索引优先队列可以让堆支持以$O(1)$的时间复杂度修改第$k$个插入的数这种操作, 本质上是用空间换时间.
维护两个数组:
ph[i] = k: 第$i$个插入的点, 在堆中的下标是$k$.hp[k] = i: 在堆中下标是$k$的点, 是第$i$个插入的点.
#include <iostream>
using namespace std;
const int N = 100010;
/* idx为插入次序 */
int n, s, idx;
int h[N], hp[N], ph[N];
/* a, b是元素在堆中的下标 */
void heap_swap(int a, int b)
{
swap(ph[hp[a]], ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}
/* 下沉 */
void down(int u)
{
int t = u;
if (2 * u <= s && h[2 * u] < h[t]) t = 2 * u;
if (2 * u + 1 <= s && h[2 * u + 1] < h[t]) t = 2 * u + 1;
if (t != u)
{
heap_swap(t, u);
down(t);
}
}
/* 上浮 */
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u >>= 1;
}
}
int main()
{
cin >> n;
string op;
int k, x;
while (n --)
{
cin >> op;
if (op == "I")
{
cin >> x;
s ++;
idx ++;
h[s] = x;
ph[idx] = s;
hp[s] = idx;
up(s);
}
else if (op == "PM") cout << h[1] << endl;
else if (op == "DM")
{
heap_swap(1, s);
s --;
down(1);
}
else if (op == "D")
{
cin >> k;
k = ph[k];
heap_swap(k, s);
s --;
up(k);
down(k);
}
else if (op == "C")
{
cin >> k >> x;
k = ph[k];
h[k] = x;
up(k);
down(k);
}
}
return 0;
}
最小的k个数
直接用一个大根堆动态维护即可.
class Solution {
public:
vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
priority_queue<int> heap;
for (auto x : input)
{
if (heap.size() < k || heap.top() > x) heap.push(x);
if (heap.size() > k) heap.pop();
}
vector<int> res;
while (heap.size()) res.push_back(heap.top()), heap.pop();
reverse(res.begin(), res.end());
return res;
}
};