算法:通过堆排序,获取前N个最大数
发布日期:2021-08-14 18:04:35 浏览次数:4 分类:技术文章

本文共 2432 字,大约阅读时间需要 8 分钟。

算法:通过堆排序,获取前N个最大数

在一组无序数组中,比如{1,9,8,2,7,3,6,4,5}

将数组看做是一个,也可以用二叉树来表示

 

但是这个堆现在还不是大顶堆,大顶堆的特点是父节点永远大于左右子节点

第一步需要将这个堆构建成大顶堆

构建前需要知道的几点:

  • 二叉树的最后一个非叶子节点,计算公式是:array.length / 2 - 1

  • 非叶子节点都是相邻的,这就是为什么buildMaxHeap方法中的i的步进方式是减1

  • 父节点左子节点的计算公式是:2 * i + 1

  • 父节点右子节点的计算公式是:2 * i + 2

  • buildMaxHeap方法的length参数意义:因为构建大顶堆后,根节点就成了最大值,此时将根节点数组尾元素交换,就能将最大值移动到数组末尾,那么第一大的值已经确定,现在需要确定第二大的值,那么就需要在剩下的元素当中再次构建大顶堆,所以就需要控制后续构建大顶堆时的数组长度,也就是length

/*** 构建大顶堆** @param array  原始数组* @param length 需要构建的长度*/private static void buildMaxHeap(int[] array, int length) {    //从最后一个非叶子节点开始    for (int i = length / 2 - 1; i >= 0; i--) {        adjustHeap(array, i, length);    }}​/*** 调整大顶堆** @param array  被调整数组* @param i      非叶子节点* @param length 需要调整的长度*/private static void adjustHeap(int[] array, int i, int length) {    //获取当前非叶子节点的值    int temp = array[i];    //依次遍历非叶子节点的左子节点    for (int j = 2 * i + 1; j < length; j = 2 * j + 1) {        //让j指向左右子节点较大的哪个        if (j + 1 < length && array[j] < array[j + 1]) {            j++;        }        //如果子节点>父节点        if (array[j] > temp) {            //让当前非叶子节点的值等于子节点的值            array[i] = array[j];            //让当前非叶子节点的下标指向当前字节点的下标            i = j;        } else {            //因为大顶堆是从下到上构建的,所以如果父节点是最大的那个的话就可以直接退出循环            break;        }        //让大的子节点等于之前非叶子节点的值        array[j] = temp;    }}

 

当无序数组第一次执行完buildMaxHeap方法后,已经可以确定根节点就是最大值,然后将根节点的值与元素末尾的值交换

然后循环这个过程

/*** 获取前n个最大的数** @param array 原始数组* @param n     前n个*/public static int[] heapSort(int[] array, int n) {    int size = n;    //第一次构建大顶堆    int length = array.length;    buildMaxHeap(array, length);    //此时顶端是数组中最大的节点,将顶端与数组末尾交换,然后在剩下的数组中再次构建大顶堆    while (n > 0 && n <= length) {        // 交换首尾元素        int temp = array[0];        array[0] = array[length - 1];        array[length - 1] = temp;        n--;        length--;        buildMaxHeap(array, length);    }    int[] result = new int[size];    System.arraycopy(array, array.length - size, result, 0, size);    return result;}

 

重点看这个地方

while (n > 0 && n <= length) {        // 交换首尾元素        int temp = array[0];        array[0] = array[length - 1];        array[length - 1] = temp;        n--;        length--;        buildMaxHeap(array, length);    }
  1. 交换根节点和数组末尾元素后,意思就是已经确定最大值,然后将n减1,length减1,n用来控制构建大顶堆的次数,构建n次,就能确定前n个最大值

  2. 然后再次构建大顶堆,直到n=0跳出循环

while循环结束,那么数组的后n项,已经是排序好了的

假如n=3那么结果就是{7,8,9}

假如n=9那么结果就是{1,2,3,4,5,6,7,8,9},也就是最终堆排序的结果

 

转载于:https://www.cnblogs.com/lezon1995/p/11235329.html

转载地址:https://blog.csdn.net/weixin_30731305/article/details/101226998 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:c#/netcore/mvc视图中调用控制器方法
下一篇:Redis中3种特殊的数据类型

发表评论

最新留言

能坚持,总会有不一样的收获!
[***.219.124.196]2024年12月03日 11时54分21秒