算法

排序

1.堆排序

手写一个堆

假设size表示堆的大小，heap表示当前堆

①插入一个数：heap[++size]=x;up(size);

②求集合中的最小值:heap[1];

③删除最小值:heap[1]=heap[size];size–;down(1);

④删除任意一个元素:heap[k]=heap[size];size–;down(k);up(k);

⑤修改任意一个元素heap[k]=x;down(k);up(k);

堆

一棵完全二叉树，除了最后一层一层结点，上面所有结点都是满的且不存在空的情况，最后一层结点从左到右排列。

小根堆

每个点的值都是小于等于左右儿子的值，因此根节点一定是最小值

存储

用一维数组存，一号点为根节点，结点x的左儿子的下标是2x，右儿子的下标是2x+1

操作

down(x):如果一个值变大则下移

up(x)：如果一个值变小则上移

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
#创建堆，时间复杂度为O(n)
for(int i=n/2;i;i--)down(i);
#down操作
void down(int u){
    int t=u;#最小值的下标
    if(u*2<=size&&h[u*2]<h[t])t=u*2
    if(u*2+1<=size&&h[u*2+1]<h[t])t=u*2+1
    #此时t是最小值的下标
    if(u!=t){#根节点不是最小值
        swap(h[u],h[t]);
        down(t)
	}    
}