栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

堆排序算法

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

堆排序算法

堆排序
  • 一、堆排序
      • 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 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 方法,我们我们再手动实现。
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/946155.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号