带你读《图解算法小抄》十四、排序（12）

带你读《图解算法小抄》十四、排序（11）https://developer.aliyun.com/article/1348139?groupCode=tech_library

6.堆排序

堆排序整个流程可以总结为：上浮下沉

1）为什么解决本题需要用到堆？

很多同学可能会想到这样一种解决，我把数组全部排序好，这样就可以拿到第k大的元素，这样是一种解法，但是我们是需要第K大的元素，不一定要全部排序好再去拿，只针对部分元素进行排序，这样的复杂度显然可以降低的。

也就是可以转化为：使用堆排序来解决这个问题——建立一个大顶堆，做k−1 次删除操作后,堆顶元素就是我们要找的答案（堆排序过程中，不全部下沉，下沉nums.length-k+1,然后堆顶可以拿到我们top k答案了）

2）基本介绍

堆排序是利用 堆 这种 数据结构 而设计的一种排序算法，它是一种选择排序，最坏 、最好、平均时间复杂度均为 O(nlogn)，它是不稳定排序。

注意因为完全二叉树的性质，可以用数组表示对应的树结构（所以，堆排序过程中，你是看不到树这数据结构的，用数组进行映射了），这叫顺序存储

3）顺序存储二叉树

特点

• 第 n 个元素的 左子节点 为 2*n+1
  
• 第 n 个元素的 右子节点 为 2*n+2
  
• 第 n 个元素的 父节点 为 (n-1)/2
  
• 最后一个非叶子节点为 Math.floor(arr.length/2)-1
  

堆是具有以下性质的完全二叉树：

• 大顶堆：每个节点的值都 大于或等于 其左右孩子节点的值
  

注：没有要求左右值的大小关系

• 小顶堆：每个节点的值都 小于或等于 其左右孩子节点的值
  

带你读《图解算法小抄》十四、排序（13）https://developer.aliyun.com/article/1348137?groupCode=tech_library