堆排序
- 一、堆排序
- 1、什么是堆结构?
- 2、堆分类
- 3、堆排序实现思路(以大根堆为例)
- 4、实现代码
- 5、借助对数器测试代码正确性
- 6、测试结果
- 7、时间复杂度
- 二、堆排序扩展题目
-
一、堆排序
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 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 方法,我们我们再手动实现。