排序

堆排序

1. 什么是堆？
   • 从存储视角来看就是数组，逻辑视角上看是一个顺序存储的"完全二叉树"，大根堆是根>=左右孩子结点，小根堆是根<=左右孩子结点。
2. 什么是堆排序？
3. 如何建堆？
4. 如何基于堆排序？
5. 堆排序算法效率分析
   • 时间复杂度
     • 排序的时间开销花费主要是两方面，一是比较二是交换，堆排序的时间开销在，建堆和排序和调整堆
     • 建堆时，需要比较当前结点(比较一次)和孩子结点中较大(比较一次)的一个，进行下坠，若树高为h，当前结点在第i层，此结点最多下坠2(h - i)层，关键字对比次数不超过2(h - i)，第i层最多有2^i - 1个结点，只有1 ～ h - 1层的结点需要下坠，进行累加的出结果是<= 4n，那么关键字对比次数不超过4n，建堆时间复杂度为O(n)。
     • 排序后并调整堆时，需要将堆顶结点和最后一个结点交换，交换后再进行调整堆，调整堆时根结点进行下坠，最多下坠h - 1层，每下坠一层最多对比两次。因此一趟排序的时间复杂度为O(2h) = O(2logn) =O(logn)，每趟排好序一个元素，最终n个元素有序，则需要排序n - 1趟，则总的时间复杂度为O(nlogn)。
     • 所以建堆+排序+调整堆的总的时间复杂度为O(n) + O(nlogn) = O(nlogn)               
   • 空间复杂度
     • 常数级的空间占用，空间复杂度为O(1)  
6. 堆排序的稳定性
   • 比如像212这种情况，建立完大根堆后进行排序，此时第一个2会跑到最后，此时第一个2和第二个2的相对顺序在排序前后发生了变化，这就是不稳定的体现。