堆排序--自学笔记-育师

堆排序

学习目标

1.堆结构

2.堆排序思想

3.代码实现

4.复杂度分析

1.堆结构

定义

符合以下两个条件之一的完全二叉树

根节点的值 >= 子节点的值，称为最大堆，或大顶堆
根节点的值 <= 子节点的值，称为最小堆，或小顶堆

2.堆排序思想

(1)用数列构建出一个大顶堆，取出堆顶的数字
将数组看作一颗完全二叉树
补充：完全二叉树的性质：
- 将根节点的下标视为0，则第 i 个数的左子节点下表为 2i + 1 ，右子节点下标为 2i + 2
- 对于有n个元素的完全二叉树(n>=2)，它的最后一个非叶子节点的下标：n/2 - 1
初始化堆
(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;}