新竹县网站建设_网站建设公司_需求分析_seo优化

堆排序

学习目标

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）