Topk问题与堆排序(Java数据结构)

前言：

        接触完堆之后，也逐渐对堆了如指掌，最后再来讨论一下两个问题。

        有如下场景：

        1、全国有几千所大学，我如何能够快速找出排名前10的大学？

        2、我如何对这10所大学排好序？

        为了用堆解决问题，接下来我们就来一起学习Topk问题的解法与堆排序！

TopK问题：

        我们需要借助堆完成找到最大或最小的集合。

        现在我们开始思考一个问题，假如我这会有20个数据，我如何才能找到最大或最下的三个数据？

        第一步：要创建大小为3的堆。

        那么这个堆应该创建成大堆还是小堆呢？

        答案是：如果要找最大的3个，就创建大小为3的小堆。

                       如果要找最小的3个，及创建大小为3的大堆。

        很多人此时就很难想，本能地以为我找小就要创建小堆，找大就要创建大堆，这个观点是不对的，为什么？

        可以画图解释：

此时自然而然该堆中存放的就是最大的3个元素！！

如果换做是大堆，存放的除了堆顶是最大的元素之外其他的不符合条件！！！

找到最大的三个元素：

建小堆：

接下来就来尝试自己写写代码：

    public static void main(String[] args) {
        int arr[] = {12,1,3,32,13,16,17,18,10,44};
        PriorityQueue<Integer> q = new PriorityQueue<>();
        //找到最大的3个元素
        for(int i = 0;i<3;i++) {
            //插入3个元素默认建小堆
            q.offer(arr[i]);
        }
        for(int i = 3;i<arr.length;i++) {
            if(arr[i] >q.peek()) {
                q.poll();
                q.offer(arr[i]);
            }
        }
        for(int i = 0;i<3;i++) {
            System.out.print(q.poll()+" ");
        }
    }

结果如下：

找到最小的三个元素：

        建大堆：

        自己写一个比较器，并传入参数。

class IntCom implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}
public class Test1 {
    public static void main(String[] args) {
        int arr[] = {12,1,3,32,13,16,17,18,10,44};
        PriorityQueue<Integer> q = new PriorityQueue<>(new IntCom());
        //找到最大的3个元素
        for(int i = 0;i<3;i++) {
            //插入3个元素默认建小堆
            q.offer(arr[i]);
        }
        for(int i = 3;i<arr.length;i++) {
            //注意修改大于号
            if(arr[i] <q.peek()) {
                q.poll();
                q.offer(arr[i]);
            }
        }
        for(int i = 0;i<3;i++) {
            System.out.print(q.poll()+" ");
        }
    }
}

堆排序：

        有人说，大堆一定是从大到小分布的，小堆一定是从小到大排布的吗？

        答案肯定不是，大堆你只能确定每棵子树的根节点一定大于孩子节点，小堆也一样，没棵子树的根节点一定小于孩子节点，但是不能确定左孩子和右孩子的大小关系。

        此时要想实现堆排序，有以下几个步骤：

        1、要想排升序，得是大堆。(把最大的数逐渐沉底)

        2、要想排降序，得是小堆。(把最小的数逐渐沉底)

        3、每次找到将堆顶和堆底的元素进行交换，之后对剩下的元素继续向下调整为大(小)堆。

了解了理论，接下来就来实践一下：

将数组{12,1,3,32,13,16,17,18,10,4}排成降序：

代码如下：

    public static void sitfDown(int[] arr,int parent,int len) {
        int child = parent*2+1;
        while(child < len) {
            if(child+1<len && arr[child+1]<arr[child]) {
                child++;
            }
            if(arr[child]<arr[parent]) {
                swap(arr, child, parent);
                parent = child;
                child = parent * 2 + 1;
            }else {
                break;
            }
        }
    }
    public static void swap(int[] arr,int child, int parent) {
        int tmp = arr[parent];
        arr[parent] = arr[child];
        arr[child] = tmp;
    }
    public static void main(String[] args) {
        int arr[] = {12,1,3,32,13,16,17,18,10,44};
        //重新组成小堆
        for(int i = (arr.length-1-1)/2;i>=0;i--) {
            sitfDown(arr,i,arr.length);
        }
        //进行排序
        for(int i = 0;i< arr.length;i++) {
            swap(arr,0,arr.length-1-i);
            sitfDown(arr,0, arr.length-1-i);
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }

升序大家可以自己可以尝试尝试！！