数据结构--堆排序 - scratch吧

level 3

堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆的操作编辑：
在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：
最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
初始化数组，加入时间复杂度变量，观察其运行时间，记得在加速模式下运行。

构建二叉树堆

堆内元素调整

大顶堆排序

堆得时间复杂度分析：
堆排序分为两步，即初始化堆、调整堆。
两个步骤都要调用一个调整结点顺序的函数堆调整Heapify，以大根堆为例，操作为：
1：如果父亲结点“大顶堆[a]”和它的两个孩子结点“大顶堆[2a]”],“大顶堆[2a+1”满足大顶堆[[a] > max{大顶堆[[2a+1], 大顶堆[[2a]}，那么返回；因为，scratch的数组下标是从1开始的。所以叶子结点为“大顶堆[[2a+1], 大顶堆[[2a]”
2：如果不满足堆的性质，那么将父亲结点大顶堆[a]和较大孩子结点max{大顶堆[2a+1], 大顶堆[2a]}交换，
3：将原来较大的孩子结点作为父亲结点，重复上述操作，直到孩子结点是叶子结点为止
初始化堆的时间复杂度分析
初始化堆的时候，对于每个非叶子结点，都要调用上述函数，将它与它的孩子结点进行比较和交换，顺序是从后向前。
以操作2作为基本操作，对每一层都完全铺满的堆进行分析，
设元素个数为n，则堆的高度k=log（n+1）≈log n，非叶子结点的个数为2^（k-1）-1
假设每个非叶子结点都需要进行调整，则第i层的非叶子结点需要的操作次数为k-i，
第i层共有2^（i-1）个结点，则第i层的所有结点所做的操作为k*2^（i-1）- i*2^（i-1），
共k-1层非叶子结点，总的操作次数为
　　　　

化简可得，上式=2^k-k+1，将k=log（n+1）≈log n代入，得n - log n +1，
所以，初始化堆的复杂度为O(n)
调整堆的时间复杂度分析
调整堆的复杂度计算和初始化堆差不多，
假设根节点和排在最后的序号为m的叶子结点交换，并进行调整，那么调整的操作次数 = 原来m结点所在的层数 = 堆的高度（因为m结点在堆的最后）= log m
共n个结点，调整的总操作次数为
　　　　　