Acwing算法基础篇（二） 堆排序

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

输入格式
第一行包含整数 n 和 m。

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

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

数据范围
1≤m≤n≤105，
1≤数列中元素≤109
输入样例：
5 3
4 5 1 3 2
输出样例：
1 2 3

 堆的定义：一颗完全二叉树：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。  而堆又有大根堆小根堆之分，若子节点的值小于等于父节点，则为小根堆，反之为大根堆。  介绍了堆的概念后，我们渴望手写出一个堆，它具有以下功能。

插入一个数 求最小值 删除最小值 删除任意一个元素 修改任意一个元素  具体实现时我们选用一维数组实现。

 首先是编号问题。

 根节点编号为1，对于编号为x的元素，它的左儿子为2x，右儿子为2x+1。  堆功能的实现主要由两个操作达成，它们为up()与down(),它们的功能是维持堆的有序性。下面先通过小根堆解释down()操作。  如图，此时堆并不满足小根堆性质，因此我们需要对破坏了性质的“6”元素进行down操作，把它放至它的正确位置。  首先根据小根堆的性质，我们选择3来与6进行交换，因为对于6，3，4来说，3是最小的元素，将它上调并不会影响堆的有序性。  移动过后发现6仍处于错误的位置，因此再执行一次上述操作。  同理，up操作就是处于底层的数需要不断的上移，来寻找自己合适的位置。例子如下  显然2的位置是错误的。因此我们让2与自己的兄弟结点进行比较，并从中挑出较小的元素与父节点进行交换，完成up操作。  现在我们使用这两个操作来完成目标的5个操作，我们令heap为堆数组，size为当前堆大小

插入一个数：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);  在这里比较需要注意的就是删除最小值这个操作。因为我们使用一维数组实现堆，所以想要删除第一个元素对我们来说是比较困难的，删除后的down操作也不方便。因此我们选择对最容易操作的末尾元素进行一个down操作，通过它完成整个堆的重排列过程。  除此之外就是删除任意一个元素，再用末尾元素替换原元素之后，我们为了避免分支判断直接对它进行两次操作。down和up操作不会都执行。

 建堆时为了达到O(N)的时间复杂度，我们从2/n开始往上进行down操作。n/2代表最后一个非叶子结点的编号，n/4就是该层的元素个数。假设每个元素都需要（最坏情况下）down至叶子层。那么这一层的操作数就是n/4(元素个数)1(down的层数)。  同理，对于倒数第二个非叶子层，它的元素个数是n/8,最坏情况下它需要down两层，因此未n/82。  最终算出来总的时间复杂度都就是O（N）