堆排序
学习目标
1.堆结构
2.堆排序思想
3.代码实现
4.复杂度分析
1.堆结构
定义
符合以下两个条件之一的完全二叉树
- 根节点的值 >= 子节点的值，称为最大堆，或大顶堆
- 根节点的值 <= 子节点的值，称为最小堆，或小顶堆
2.堆排序思想
(1)用数列构建出一个大顶堆，取出堆顶的数字
将数组看作一颗完全二叉树
补充：完全二叉树的性质：
- 将根节点的下标视为0，则第 i 个数的左子节点下表为 2i + 1 ，右子节点下标为 2i + 2
- 对于有n个元素的完全二叉树(n>=2)，它的最后一个非叶子节点的下标：n/2 - 1
初始化堆
初赛：最后一个非叶子节点与其子节点 先进行比较，初赛冠军站到三人组的根节点位置，并进行复赛
9 与 6 交换
复赛：循环，与其父节点再进行比较 直到根节点
决赛：与根节点比较
9 与 4 交换
9 与 4 发生交换 并不意味 4 就该处在这个位置 它只是生来就处在上层
下沉与 9 之前的“对手”比较
只要当三人组中，父节点与子节点发生了交换，都需要下沉比较，直到找到了自己的真正位置
(2)取出堆顶数字，调整剩余数字，构建出新的大顶堆，再次取出堆顶的数字
取出堆顶数字
将堆顶数字与最后一个叶节点交换
也就是将数组末尾的数字交换到堆顶，该数字一定是个叶子节点，使得完全二叉树的结果不会被破坏
记录从堆顶交换下来的数字总数，节省空间
调整剩余数字
因为其他三人组结构没有被破坏，此时只需从根节点 4 开始向下进行三人组比较
(3)循环往复，完成整个排序
取8
下沉
取6
下沉
取5
4无法下沉 排序完成
3.代码实现
/** * 堆排序 * @param arr */publicstaticvoidheapSort(int[]arr){//堆排序第一步：初始化堆//这里选择构建大顶堆：从小到大排序buildMaxHeap(arr);//取数字,调整 循环//取出堆顶数字：与数组末尾元素交换//数组长度-1for(inti=arr.length-1;i>0;i--){swap(arr,0,i);//i也可以代表数组中可用的数字maxHeapify(arr,0,i);}}/** * 初始化堆(大顶堆) * @param arr */privatestaticvoidbuildMaxHeap(int[]arr){//构建堆第一步：从最后一个非叶子节点开始进行三人组比赛//也可以从arr.length - 1 开始,但它没有左右子节点，也会运算到arr.length / 2 - 1for(inti=arr.length/2-1;i>=0;i--){//大顶堆化maxHeapify(arr,i,arr.length);}}/** * 大顶堆化 * @param arr * @param i * @param heapSize */privatestaticvoidmaxHeapify(int[]arr,inti,intheapSize){//找到左右子节点intl=2*i+1;intr=2*i+2;intlargest=i;//不能越界if(l<heapSize&&arr[l]>arr[largest]){largest=l;}if(r<heapSize&&arr[r]>arr[largest]){largest=r;}if(largest!=i){//需要发生交换swap(arr,i,largest);//发生了交换 则交换下来的元素需要继续下沉maxHeapify(arr,largest,heapSize);}}privatestaticvoidswap(int[]arr,inta,intb){inttemp=arr[a];arr[a]=arr[b];arr[b]=temp;}4.复杂度分析
时间复杂度：O(nlogn)
初始化建堆：O(n)
重建堆：O(nlogn)
空间复杂度：O(1)
215. 数组中的第K个最大元素 - 力扣（LeetCode）
