堆排序和Top-K问题

不念不忘少年蓝@ 2024-04-03 11:55 86阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：渴望力量的土狗
> 
> 博客主页：[渴望力量的土狗的博客主页][Link 1]
> 
> 专栏：[数据结构与算法][Link 2]
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击免费注册和我一起刷题吧][Link 3]

**目录**

堆排序：

步骤总结：

建立思想：（以升序为例）

Top-K问题

问题描述：

基本思路： 利用分布式思想处理海量数据

拓展：

--------------------

## 堆排序： ##

### 步骤总结： ###

堆排序即利用堆的思想来进行排序，总共分为两个步骤

1、建堆（如果升序就建大根堆，降序就建小根堆）

2、利用堆删除的思想来进行排序

前面我们说到了建堆和堆删除的操作都是需要用到向下调整的思想的，所以当我们掌握了向下调整的思想就可以完成堆排序。

ps：不了解这部分知识的可以看一下博主的这篇博客内容：

[【Java数据结构】集合PriorityQueue及其背后的数据结构堆（优先级队列）![icon-default.png_t_M85B][]https://blog.csdn.net/m0\_67995737/article/details/127246172?spm=1001.2014.3001.5502][Java_PriorityQueue_icon-default.png_t_M85B_https_blog.csdn.net_m0_67995737_article_details_127246172_spm_1001.2014.3001.5502]

![ac226cca7b5a48cb909a7bc2bbc91d55.png][]

### 建立思想：（以升序为例） ###

首先我们以大根堆的形式建堆，建堆完毕后堆顶元素为当前数组中的最大值，（注意说的是当前数组，因为我们的size一直在减小，这也是为了把最大的值放到原始数组的后面服务）将堆顶元素与堆尾元素进行互换，并向下调整，使其依然为大根堆，这样最大的值就放到了末尾，调整后的堆顶为原数组中的第二大的元素，经过上述过程，放到原数组的倒数第二个位置，依次类推，直至堆中只留一个元素，即可得到数组的升序排列。

**特别注意**：在进行这些操作的时候，我们只是定义了临时的变量来保存数组的长度，切不可改变原数组的长度！

import java.util.Arrays;
    
    public class Test {
        public static void main(String[] args) {
            int []arr={27,15,19,18,28,34,65,49,25,37};
            heapSort(arr);
            System.out.println(Arrays.toString(arr));
    
        }
    
        public static void heapSort(int[]arr){
            creatHeap(arr);
            int length= arr.length-1;
            while (length>=0){
                int temp=arr[0];
                arr[0]=arr[length];
                arr[length]=temp;
                shiftDown(arr,0,length);
                length--;
            }
    
        }
    
        public static void creatHeap(int[]arr){
            int size= arr.length;
            for(int parent=(size-1-1)/2;parent>=0;parent--){
    
                shiftDown(arr,parent,size);
    
            }
        }
    
    
        public static void shiftDown(int[]arr,int parent,int len){
    
            int child=2*parent+1;
    
            while(child<len){
                if(child+1<len&&arr[child]<arr[child+1]){
                    child++;
                }
    
                if(arr[child]>arr[parent]){
                    int temp=arr[child];
                    arr[child]=arr[parent];
                    arr[parent]=temp;
                    parent=child;
                    child=2*parent+1;
    
                }else {
                    break;
                }
            }
    
        }
    }

![3e9929956c8c4335b600e69e1a06a6cd.png][]

我们在使用堆排序的时候，其默认排序方式就是**升序排序。**

## Top-K问题 ##

Top-K问题是堆应用的一个非常经典的问题

![8407782aefa749308e01451cfb5b3528.png][]

### 问题描述： ###

TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下**数据量都比较大（注意：切不可用简单的排序后取前k个值这种做法，**这种方式在数据量不大的时候简单可行，但固然不是最优的方法。**）**

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。  
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下

### 基本思路： 利用分布式思想处理海量数据 ###

1. 用数据集合中前K个元素来建堆  
前k个最大的元素，则建小堆  
前k个最小的元素，则建大堆  
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素  
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素

![91982f86456b41859da2fb1750a57a91.png][]

class Solution {
        public int[] smallestK(int[] arr, int k) {
            if(k==0||arr==null){
                return new int[0];
            }
            //1、建大根堆
            PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2.compareTo(o1);
                }
            });
            //2、将前k个元素放到大根堆当中
            for(int i=0;i<k;i++){
                minHeap.offer(arr[i]);
            }
            //3、对从k+1个元素开始的数字与堆顶元素比较，如果比堆顶元素小就把堆顶弹出，让该小的元素作为新
            //的堆顶，并进行向下调整使之依然为大根堆
            for(int j=k;j<arr.length;j++){
    
                if(arr[j]<minHeap.peek()){
                    minHeap.poll();
                    minHeap.offer(arr[j]);
                }
            }
            //4、把大根堆中的k个元素放到数组中（此时已经为前k个最小的数）
            int[]temp=new int[k];
            for(int i=0;i<k;i++){
                temp[i]=minHeap.poll();
            }
    
            return temp;
    
    
        }
    }

![f8049efd1c1443d496d9e09b4a03221e.png][]

Top-K问题与堆排序有类似之处，我们需要注意的是：

1、当k为0或者数组为空时什么都不返回，即返回\[\],就是return int\[0\];这个操作！

2、由于我们在建大根堆时用到的优先级队列其底层是一个小根堆（默认），所以我们要重写comparator（比较器）接口中的compar方法，使之变成大根堆。这里我们可以用到几种方法：

（1）匿名内部类（我就是采用的这种方法）

（2）直接自己实现一个比较器重写comparator（比较器）接口中的compar方法

![cd2f75697dbd49b2a7e46c8de6bf109a.png][]

这两种都是可以的。

### 拓展： ###

那如果是要获取第k小的或者第k大的数（这里以第k小的数为例），我们已经求得了最小的k个数，那么我们只需要在这里面找到最大的那个数（也就是第k小的数即可)。

[ced485cbb11e458d81a746890b32cf3f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/463daa7da1084721ab03b4508cb10577.gif
[Link 1]: https://blog.csdn.net/m0_67995737?type=blog
[Link 2]: https://blog.csdn.net/m0_67995737/category_12000344.html
[Link 3]: https://www.nowcoder.com/link/pc_csdncpt_ylcxx_c
[icon-default.png_t_M85B]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/39e8fbd184174b419e31b11c5dcc07c7.png
[Java_PriorityQueue_icon-default.png_t_M85B_https_blog.csdn.net_m0_67995737_article_details_127246172_spm_1001.2014.3001.5502]: https://blog.csdn.net/m0_67995737/article/details/127246172?spm=1001.2014.3001.5502
[ac226cca7b5a48cb909a7bc2bbc91d55.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/698f54d0286347e8aaaa371ff493cada.png
[3e9929956c8c4335b600e69e1a06a6cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/0cacab5fb0ad4f61a003e65780b8e1e1.png
[8407782aefa749308e01451cfb5b3528.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/5db39586970f4a8ebbbf9f23e35a3250.png
[91982f86456b41859da2fb1750a57a91.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/8a360797a7ce43d580d3c04d7dafd7e5.png
[f8049efd1c1443d496d9e09b4a03221e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/0d288512cfe1425c9c7db693080fb3b2.png
[cd2f75697dbd49b2a7e46c8de6bf109a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/8d0a75c6a50b44d28f71e98d48300b36.png