堆排序

• 一、堆排序
• • • 1、什么是堆结构？
    • 2、堆分类
    • 3、堆排序实现思路（以大根堆为例）
    • 4、实现代码
    • 5、借助对数器测试代码正确性
    • 6、测试结果
    • 7、时间复杂度
• 二、堆排序扩展题目
• • • 1、题目描述
    • 2、解题思路
    • 3、实现代码

一、堆排序

• 在介绍堆排序之前，首先我们需要知道什么是堆结构。

1、什么是堆结构？

• 简单来说，堆结构就是使用数组实现的完全二叉树。
• 完全二叉树在满足二叉树的一些要求后，还需要满足只有最后一层允许孩子不满的情况出现，且孩子必须满足先有左孩子再有右孩子。
• 我们常说的优先级队列，实际上就是堆结构。

2、堆分类

• 大根堆：完全二叉树中每一个子树的 最大值 均是该子树的根节点，满足该要求的称为大根堆。

• 小根堆：与大根堆刚好相反，完全二叉树中每一个子树的 最小值 均是该子树的根节点。

3、堆排序实现思路（以大根堆为例）

• 建堆，先让整个数组呈现出大根堆的结构。
• 将堆的最大值（即完全二叉树的根节点）与堆末尾元素互换，同时将堆元素个数减 1 ，互换之后会打破大根堆结构，调整堆结构使其再次呈现出大根堆结构，再将调整后堆的最大值与堆的末尾元素交换，重复上述操作，直至堆中没有元素，排序完成。

4、实现代码

public class HeapSort {    // 往堆里面添加元素    public static void heapInsert(int[] arr,int index){ // 如果当前元素比其父结点元素值大，将其进行交换，继续向上比较 // 每次都是与父结点比较 while (arr[index] > arr[(index-1) / 2]){     swap(arr,index,(index - 1) / 2);     index = (index - 1) / 2; }    }// 向下调整堆    public static void heapify(int[] arr,int index,int size){ int left = index * 2 + 1;   // 记录当前结点的左孩子的索引下标（下标从0开始） // 判断是否存在左孩子，如果左孩子不存在，则右孩子也一定不会存在 while (left < size){     // left + 1 < size 用于判断是否存在右孩子     // 只有存在右孩子，且值比左孩子大才会将其赋给largest     int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;     // 与左右孩子结点中的较大值比较大小     largest = arr[largest] > arr[index] ? largest : index;     if (largest == index){  // 此时说明该结点的值比任一孩子结点值大，无需向下调整  break;     }     swap(arr,largest,index);     index = largest;     left = (index * 2) + 1; }    }    public static void heapSort(int[] arr){ if (arr == null || arr.length < 2){     return; } for (int i = 0; i < arr.length; i++){     // 建堆过程     heapInsert(arr,i); } int size = arr.length; // 将大根堆中堆顶元素与堆末尾元素交换 swap(arr,0,--size); while (size > 0){     // 交换元素后会破坏大根堆结构，需要将换上去的元素向下调整     heapify(arr,0,size);     swap(arr,0,--size); }    }    public static void swap(int[] arr,int i,int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;    }}

• 在堆排序过程中，存在两个非常重要的操作：建堆和调整堆。

5、借助对数器测试代码正确性

public class HeapSort {    public static void main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++){     int[] arr1 = MyComparator.generateRandomArray(maxSize, maxValue);     int[] arr2 = MyComparator.copyArray(arr1);     heapSort(arr1);     MyComparator.comparator(arr2);     if (!MyComparator.isEqual(arr1,arr2)){  succeed = false;  MyComparator.printArray(arr1);  MyComparator.printArray(arr2);  break;     } } System.out.println(succeed ? "恭喜你，测试成功了！" : "很遗憾，失败了，代码存在问题！");// 随机打印一组数据查看效果 int[] arr = MyComparator.generateRandomArray(maxSize, maxValue); System.out.println("排序前数组："); MyComparator.printArray(arr); heapSort(arr); System.out.println("排序后数组："); MyComparator.printArray(arr);    }}

6、测试结果

7、时间复杂度

• 时间复杂度 O(N*logN)。
• 分析堆排序的时间复杂度，只需要分析建堆和调整堆过程的时间复杂度即可。

二、堆排序扩展题目

1、题目描述

• 已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过 K ，并且 K 相对于数组来说比较小。
• 请选择一个合适的排序算法针对这个数组进行排序。

2、解题思路

• 因为题目说了每个元素移动的距离不超过 K ，那我们就可以取出下标从 0 到 K 的元素，将这些元素建立小根堆，得到的对顶元素即为整个数组的最小值（为什么其就是最小值呢？因为每个元素移动的距离是不超过 K 的，所以，下标为 K + 1 的元素不可能移动到下标为 0 的位置，故前 K 个元素一定能够找到最小值）。
• 寻找到最小值之后，堆顶元素弹出，将 K + 1 后的元素入堆，调整为小根堆，找到当前堆中的最小值，弹出，继续添加后面元素，每次添加进去一个。
• 如果最后没有元素添加，则不添加，堆顶元素弹出后，将末尾元素移至堆顶，继续调整，直至堆中没有元素存在，排序结束。

3、实现代码

public class DistanceLessK {    public static void distanceLessK(int[] arr,int k){ // PriorityQueue优先级队列，实质就是小根堆 PriorityQueue<Integer> heap = new PriorityQueue<>(); int index = 0; // 首先将前 K 个元素放入小根堆中 for (; index < Math.max(arr.length, k); index++){     // add时会对堆结构进行调整，使得添加之后仍然满足小根堆     heap.add(arr[index]); } int i = 0; for (; index < arr.length; i++, index++){     // 不断往堆里添加元素，每次循环添加一个     heap.add(arr[index]);     // 将堆顶元素弹出，因为已经找到了其该在的位置     arr[i] = heap.poll(); } // 将堆中剩余元素按要求弹出 while (!heap.isEmpty()){     arr[i++] = heap.poll(); }    }}

• 当在排序过程中没有特殊要求时，可以使用 Java 提供的 PriorityQueue 类，该类的实质就是小根堆，里面提供了许多封装好的方法，我们可以直接调用使用，如：add 方法，poll 方法，我们我们再手动实现。