写完这个手写堆就下班了

本菠萝十分想要拥有一份实习

于是开始学习深奥的数据结构 —— 堆

手写一个堆

堆,完全二叉树也。
主要函数就两个:
一个是push,用来插入一个新元素,如果是小根堆就用来向上调整
一个是pop,用来提取堆顶元素,然后再向下调整

时间复杂度上:
获取堆顶元素是O(1)的
插入一个元素和删除堆顶元素由于需要调整堆是O(logn)的

涉及到的人员有,我和我的爸爸,或者我和我的左儿子与右儿子
调整堆主要分向上调整和向下调整。

以小根堆为例:
向上调整就是,查看自己和爸爸的大小,发现自己比爸爸小,
我就是爸爸,你就是儿子,然后继续向上调整。

向下调整就是,查看自己和左儿子与右儿子的大小,
把最小的提上来,自己再下去,继续向下调整直到走到叶子节点。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> heap;
void push(int x) //up
{
int now = heap.size();
heap.push_back(x);
while(now > 0)
{
int pre = (now-1)/2;
if(heap[pre] <= heap[now])
break;
swap(heap[pre],heap[now]);
now = pre;
}
return ;
}
int top()
{
return heap[0];
}
int pop() //down
{
int ans = heap[0],sz = heap.size();
swap(heap[0],heap[--sz]); //交换堆顶元素与最后一个元素
heap.pop_back();
int index = 0;
while(index*2 + 1 < sz)
{
int right = index*2 + 1,left = index*2 + 2;
int min_i = index;
if(right < sz && heap[right] < heap[min_i])
min_i = right;
if(left < sz && heap[left] < heap[min_i])
min_i = left;
if(min_i == index)
break;
swap(heap[min_i],heap[index]);
index = min_i;
}
return ans;
}
int main()
{
int n;
scanf("%d",&n);
int tmp;
for(int i=0;i<n;i++)
{
scanf("%d",&tmp);
push(tmp);
}
for(int i=0;i<n;i++)
{
tmp = top();
pop();
printf("%d",tmp);
if(i != n-1) printf(" ");
else printf("\n");
}
return 0;
}