您现在的位置是:首页 > 正文

[大、小根堆应用总结一]堆排序的应用场景

2024-01-30 21:12:10阅读 0

前言

在整理算法题的时候发现,大根堆(小根堆)这种数据结构在各类算法中应用比较广泛,典型的堆排序,以及利用大小根堆这种数据结构来找出一个解决问题的算法最优解。因此,我打算单独将关于堆的应用独立总结出来,后面每遇到一种跟堆结构相关的应用都放到这个目录下。

堆的定义

n个关键字序列L[1…n]称为堆,当且仅当该序列满足:
1. L(i)<=L(2i)且L(i)<=L(2i+1)或
2. L(i)>=L(2i)且L(i)>=L(2i+1)
满足第一个条件的成为小根堆(即每个结点值小于它的左右孩子结点值),满足第二个添加的成为大根堆(即每个结点值大于它的左右孩子结点值)。

应用一:对一个基本有序的有序数组排序,选择哪种排序算法?

基本有序:指如果把数组排好序的话,每个元素移动的距离不超过K,并且K相对于数组长度很小。

分析

1、对于时间复杂度为O(N)的排序算法:

时间复杂度为O(N)的算法主要有基数排序、计数排序,但是这两种算法都需要提前知道数组中元素的范围,以此来建立桶的数量,因此并不合适来解决这个问题。排除!

2、对于时间复杂度为O(N2)的排序算法:

时间复杂度O(N2)常用的主要有冒泡、选择、插入,联系到题目所说的基本有序,插入排序是首选,每个元素移动的距离不超过K,因此插入排序中每个元素向前移动的距离也不会超过K,故此时插入排序的时间复杂度为O(N*K),所以插入排序可以列入考虑。

3、对于时间复杂度为O(N*logN)的排序算法

时间复杂度O(N2)常用的主要有快速排序、归并排序、堆排序,因为这两种排序方法跟数组元素的初始顺序无关,因此这两种方法也是比较好的一种。而堆排序在最好、最坏、平均情况下时间复杂度都为O(N*logN)。

较优方案

根据上面的分析,我们初步锁定在时间复杂度为O(N*logN)的排序算法。
1. 再根据题意,每个元素移动的距离不会超过k,说明前k个元素中一定有数组中最小的一个元素,即array[0]~array[k-1]中存在一个最小的元素,从这里面拿出最小的一个元素后,再往后移动一步,即数组array[1]~array[k]中存在一个次小的元素,以此下去…就可以得到n-k个排好序的元素,最后再对最后的k个元素排序即可。
2. 因此,我们可以先建立一个k个元素的小根堆,每次拿出堆顶元素,再后移一位重新调整小根堆,循环下去…最后k个元素再因此缩小调整的范围。代码如下:

public static int[] heapSort(int[] A, int n, int k) {  
        if(A == null || A.length == 0 || n < k){  
            return null;  
        }  
        int[] heap = new int[k];  
        for(int i = 0; i < k; i++){  
            heap[i] = A[i];  
        }  
        buildMinHeap(heap,k);//先建立一个小堆  
        for(int i = k; i < n; i++){  
            A[i-k] = heap[0];//难处堆顶最小元素  
            heap[0] = A[i];  
            adjust(heap,0,k);  
        }  
        for(int i = n-k;i < n; i++){  
            A[i] = heap[0];  
            heap[0] = heap[k-1];  
            adjust(heap,0,--k);//缩小调整的范围  
        }  
        return A;  
    }  
    //建立一个小根堆  
    private static void buildMinHeap(int[] a, int len) {  
        for(int i = (len-1) / 2; i >= 0; i--){  
            adjust(a,i,len);  
        }  
    }  
    //往下调整,使得重新复合小根堆的性质  
    private static void adjust(int[] a, int k, int len) {  
        int temp = a[k];  
        for(int i = 2 * k + 1; i < len; i = i * 2 + 1){  
            if(i < len - 1 && a[i+1] < a[i])//如果有右孩子结点,并且右孩子结点值小于左海子结点值  
                i++;//取K较小的子节点的下标  
            if(temp <= a[i]) break;//筛选结束,不用往下调整了  
            else{//需要往下调整  
                a[k] = a[i];  
                k = i;//k指向需要调整的新的结点  
            }  
        }  
        a[k] = temp;//本趟需要调整的值最终放到最后一个需要调整的结点处  
    }  

时间复杂度分析

每次调整heap中k个元素重新建立堆的时间复杂度与堆的高度有关,为O(logk),又需要对n个元素进行调整,时间复杂度为O(n),因此总的时间复杂度为O(nlogk),由于k相对于数组长度n来说较小,因此这种利用小根堆来进行排序的方法相对于O(nlogn)的快速排序、归并排序来说相对较优。

应用二:判断数组中是否有重复值,要求空间复杂度为O(1)?

思路一

如果没有空间复杂度限制,可以用哈希表实现。比如使用HashMap,将数据元素保存到key值当中,每次保存前判断是否存在该key值,如果存在说明有重复值。此时,时间复杂度为O(N),空间复杂度为O(N)。代码如下:

/**
     * 利用HashMap实现
     * @param a
     * @param n
     * @return
     */
    public static boolean checker2(int[] a ,int n){
        if(a == null || a.length == 0 || a.length == 1)
            return false;
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i = 0; i < n; i++){
            if(map.containsKey(a[i]))
                return true;
            map.put(a[i], 1);
        }
        return false;
    }

思路二

  1. 对于有空间复杂度限制,我们可以先排序,再判断的思路。因为排好序后,重复值排在了相邻位置。此时,问题就转化为了,空间复杂度限制为O(1)的情况下,考察经典排序算法,怎么实现一个最快的算法。
  2. 空间复杂度为O(1)的有冒泡、选择、插入、希尔排序以及非递归形式的堆排序,再根据时间复杂度判断,堆排序为O(NlogN),可以知道使用非递归实现的堆排序最快。
    此时的步骤就是,先通过堆排序将数组排好序,然后在遍历一遍数组,比较相邻两元素值是否相等。代码如下:
public static boolean checkDuplicate(int[] a, int n) {
        if(a == null || a.length == 0 || a.length == 1)
            return false;
        heapSort(a,n);
        for(int i = 1; i < n; i++){
            if(a[i] == a[i-1]){
                return true;
            }
        }
        return false;
    }

    private static void heapSort(int[] a,int n){
        for(int i = (n-1) / 2; i >= 0; i--){
            adjustDown(a,i,n);
        }
        int temp;
        for(int i = n-1; i > 0; i--){//只需要n-1趟
            temp = a[0];//交换堆顶元素
            a[0] = a[i];
            a[i] = temp;
            adjustDown(a,0,i);
        }
    }

    private static void adjustDown(int[] a , int k,int n){
        int temp = a[k];
        for(int i = 2 * k + 1; i < n; i = i * 2 + 1){
            if(i < n-1 && a[i] < a[i+1])//有右孩子结点,并且有孩子结点值大于左海子结点值,将i指向右孩子
                i++;
            if(temp >= a[i]) 
                break;
            else{//需要向下调整
                a[k] = a[i];
                k = i;//指向新的可能需要调整的结点
            }
        }
        a[k] = temp;
    }

时间复杂度分析:

堆排序的时间复杂度为O(NlogN),后面只有一次遍历过程,因此总的时间复杂度还是O(NlogN)。

以上就是堆应用的两个场景,后面碰到了,继续总结。。。

网站文章

  • Luogu-P1941 飞扬的小鸟

    Luogu-P1941 飞扬的小鸟

    题目题目链接测试得分:  100主要算法:  DP(零一背包,完全背包)题干:   背包组合问题应试策略:每一个点都是由前面的状态转移的,并且对后面的状态没有影响,满足最优化原理与无后效性原则,选择算法DP对于图上的每一个点都是由前一列降下来或者是前面升上来的,对于降下来的情况是...

    2024-01-30 21:12:02
  • Windows内核和Linux内核比较

    Windows内核和Linux内核比较

    Windows内核和Linux内核比较

    2024-01-30 21:11:25
  • 关于C语言自定义函数浅谈

    关于C语言自定义函数浅谈

    如果函数不接收用户传递的数据,那么定义时可以不带参数。如下所示:123//bodydataType 是返回值类型,它可以是C语言中的任意数据类型,例如 int、float、char 等。functio...

    2024-01-30 21:11:18
  • [MySQL]聚合函数与分组

    [MySQL]聚合函数与分组

    1. 聚合函数介绍 1.1 什么是聚合函数 1.2 常用的聚合函数 2. 常用的聚合函数 2.1 AVG() 2.2 SUM() 2.3 MAX() 2.4 MIN() 2.5 COUNT() 2.6 补充 3. GROUP BY 3.1 分组的基本使用 3.2 使用多个列分组 3.3 结论 3.4 WITH ROLLUP 4. HAVING

    2024-01-30 21:10:43
  • 二分图相关

    二分图相关一、染色法判定二分图二分图要求边的两端点处于不同的集合,那么将两端点分别染成不同的颜色,如果没有冲突,则说明是二分图。首先是dfs函数,深搜进行染色:bool dfs(int u,int c...

    2024-01-30 21:10:36
  • 在ML中缺乏数据可是个大问题,亲测有效的5种方法帮您解决

    在ML中缺乏数据可是个大问题,亲测有效的5种方法帮您解决

    https://www.toutiao.com/a6701193162699833859/ 在我做过的很多项目中,公司虽然有非常棒的AI商业创意,但当他们意识到自己没有足够的数据时,却会慢慢的变得沮丧起来。然而,确实有解决的方案。本文的目的是简要地向你介绍其中的一些在我的实践中已经证明有效的方法,而不是列出所有现有的解决方案。 数据稀缺问题非常重要,因为数据是任何人工智能项目的...

    2024-01-30 21:10:30
  • JavaWeb学习笔记——jQuery动画、事件

    jQuery-3动画方法练习:品牌显示事件文档加载事件绑定事件移除事件冒泡事件对象练习:图片跟随 动画 方法 基本: show([speed,[easing],[fn]]) 显示 hide([spee...

    2024-01-30 21:10:01
  • 结构体变量

    在C语言中,可以使用结构体(Struct)来存放一组不同类型的数据。结构体的定义形式为: struct 结构体名{ 结构体所包含的变量或数组 }; 结构体是一种集合,它里面包含了多个变量或数组,它们的...

    2024-01-30 21:09:56
  • Java面试注意

    3125

    2024-01-30 21:09:48
  • python 依赖下载

    https://www.lfd.uci.edu/~gohlke/pythonlibs/#scipy

    2024-01-30 21:09:20