优先级队列(堆)及其背后的数据结构

转x33g5p2x  于2022-02-07 转载在 其他  
字(8.2k)|赞(0)|评价(0)|浏览(261)

认识堆前的基本概念：
1、完全二叉树：若二叉树的深度为h，则除第h层外，其他层的结点全部达到最大值，且第h层的所有结点都集中在左子树。

2、满二叉树：满二叉树是一种特殊的的完全二叉树，所有层的结点都是最大值。
3、已知树的其中一个孩子结点下标为i，则它的父亲结点的下标为(i-1)/2
4、已知树的其中一个父亲结点下标为i，则它的孩子结点的下标为i*2+1

一、堆

1.堆的概念

  1. 堆逻辑上是一棵完全二叉树
  2. 堆物理上是保存在数组中
  3. 满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆；反之，则是小堆，或者小根堆，或者最小堆。当一个堆为大堆时，它的每一棵子树都是大堆。
  4. 堆的基本作用是，快速找集合中的最值

二、堆的基本操作

1.创建堆与向下调整

创建堆只有两种堆可以创建，要不就是大根堆，要不就是小根堆。而要满足大根堆还是小根堆的逻辑，要向下调整的操作才能实现。

要想自己实现堆，堆本身就是一个数组，因此创建一个数组来创建堆。（此处以创建大根堆为例）

创建堆思路：首先i从最后一个父亲结点开始，向下调整为大根堆。当调整完其中每一个堆时，将父亲结点的值移到孩子结点的值，而孩子结点的值设置为2*parent+1。当然，如果孩子结点的值一旦大于整个堆的结点数，则在i-1的结点处去调整堆。每一个子树都是按照相同的情况去调整为大堆。

注意的是，算出一个孩子结点可能是其中一个二叉子树的左节点，当然它也有可能有右节点。因此首先判断它有没有右节点，即child+1<len，并且如果有右节点的话要比较右节点和它的值哪一个大，如果右节点比左节点的值大，则child直接指向右节点，否则不需要调整child。再比较两个孩子结点的数组是否比它们的父亲结点的值大。

当parent的下标指向有以它为根节点深度为3的树时，如果两个孩子结点比较后数值较大的孩子结点与父亲结点比较，若父亲结点的数值更大，则不用继续调整了。

例如：

说明：此处的usedSize为数组的最大下标。

public void creatHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i]=array[i];
            usedSize++;
        }
        for (int i = (array.length-1-1)/2; i >=0 ; i--) {
            adjustDown(i,usedSize);
        }
    }
    //每次调整后的结束位置：usedSize
    /*
    向下调整
     */
    public void adjustDown(int parent,int len) {
        int child = parent*2+1;
        while(child<len) {
            if(child+1<len&&elem[child]<elem[child+1]) {
                child++;
            }
            if(elem[child]>elem[parent]) {
                int tmp = elem[parent];
                elem[parent]=elem[child];
                elem[child]=tmp;
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }

2.创建堆的时间复杂度

有不少初学者认为，创建堆的过程为O(N*log2^N)，N为结点个数。其实不然，创建堆的时间复杂度实际上为O(N)，证明过程如下：

说明：h为整棵树的深度。

因为向下调整是从最后一个父亲结点开始的。因此每一层的结点数乘以它所要调整的堆的高度。还是以上图为例。**下标为0的结点除了它所在的层以外其余的层数都要调整为大根堆，这一层调整的时间复杂度就为2的0次方乘以(h-1)；下标为1和2的结点除了它所在的层和比他低的层外都要调整为大根堆，这一层调整的时间复杂度就为2的1次方乘以(h-2)。**以此类推，最后的时间复杂度为：

式子1：

但我们要对此进行化简，采用数学上的错位相减法。令等式的两边同乘以2，得：

式子2：

让式子2减去式子1：

转化为：

由等比数列的求和公式：

得：

又因为假设该堆有n个结点，深度为h。因为结点数n=2的h次方-1 。因此高度为h=log2为底的（n+1）。将h代入T(n)中得：

因此，创建堆的时间复杂度为T(n)=O(N)。

3.向上调整

向上调整一般适用于优先级队列（已经确定是大堆还是小堆后）中的入队操作后调整堆为大堆还是小堆。
还是以下图为例：我们向上调整是先从最后一个结点的下标作为孩子结点来进行调整，已知孩子结点的下标则能求出父亲结点的下标。若孩子结点的下标小于0，则直接退出循环。当其中一个孩子结点的值小于父亲结点的值，则直接退出循环，（因为已经确定了原本的整个堆为大堆）是因为能够直接确定整个堆已经是一个大堆。

//向上调整
    public void adjustUp(int child) {
        int parent = (child-1)/2;
        while(child>0) {
            if(elem[child]>elem[parent]) {
                int tmp = elem[parent];
                elem[parent]=elem[child];
                elem[child]=elem[parent];
                child=parent;
                parent=(child-1)/2;
            }else {
                break;
            }
        }
    }

4.模拟优先级队列的offer操作

优先级队列的offer操作，是从堆的最后一个位置处插入元素，并且插入后要进行向上调整来确保堆是大堆。

//向上调整
    public void adjustUp(int child) {
        int parent = (child-1)/2;
        while(child>0) {
            if(elem[child]>elem[parent]) {
                int tmp = elem[parent];
                elem[parent]=elem[child];
                elem[child]=elem[parent];
                child=parent;
                parent=(child-1)/2;
            }else {
                break;
            }
        }
    }
      public void offer(int val) {
        if(isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++]=val;
        adjustUp(usedSize-1);
      }
      public boolean isFull() {
        return usedSize==elem.length;
    }

5.模拟优先级队列的poll操作

优先级队列中的poll操作是使堆的堆顶元素出队（前提该堆已经是一个大堆）。那么我们可以让堆顶元素与堆的最后一个位置的元素交换，交换后再根据向下调整来调整堆为一个大堆。

代码：

//出最大的元素
    public void pop() {
        if(isEmpty()) {
            return;
        }
        int tmp = elem[0];
        elem[0]=elem[usedSize-1];
        elem[usedSize-1]=tmp;
        usedSize--;
        adjustDown(0,usedSize);
    }
    public boolean isEmpty() {
        return usedSize==0;
    }

三、优先级队列集合的使用

1.优先级队列中的比较规则

Student类：

class Student {
    private String name;
    private int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

Test类：

public static void main(String[] args) {
        PriorityQueue<Student> queue = new PriorityQueue<>();
        queue.offer(new Student("bit",18));
        queue.offer(new Student("zjr",8));
        System.out.println(queue);
    }

若直接入队，则编译器会报错。

并且我们在学习Compartor比较器时，对一个类型的数组排序要用Comparable接口或者Comparator接口。不能直接进行比较。

public static void main(String[] args) {
        Student[] students = new Student[2];
        students[0] = new Student("zjr",12);
        students[1] = new Student("bit",89);
        Arrays.sort(students,new NameComparator());
        System.out.println(Arrays.toString(students));
    }

原因是PriorityQueue不知道我们是按照哪个属性去排的序，我们点入PriorityQueue的源码当中，看到了它的其中一个构造方法中能有一个Comparator比较器。

**当然我们也可以用Comparable比较器，但是对类的嵌入性太强，**若重写的compareTo方法只是比较的是它的年龄，则该类只能按照年龄去比较，而不能用姓名去比较了。此处就直接省略了。

那Comparator可以直接创建多个类来实现该接口，可用作多个不同类型的属性的比较。如：

class AgeComparator implements Comparator<Student> {

    @Override
    public int compare(Student o1, Student o2) {
        return o1.getAge()-o2.getAge();
    }
}

class NameComparator implements Comparator<Student> {

    @Override
    public int compare(Student o1, Student o2) {
        return o1.getName().compareTo(o2.getName());
    }
}

    public static void main(String[] args) {

        PriorityQueue<Student> priorityQueue = new PriorityQueue<>(new AgeComparator());

        priorityQueue.offer(new Student("bit",18));

        priorityQueue.offer(new Student("zjr",8));

        System.out.println(priorityQueue);

    }

2.特殊的比较方式

若两个引用进行比较，是地址不同的两个引用。若在该引用的类中重写equals和hashCode方法，并且创建对象的时候创建的属性都是相同的，则调用equals返回的是true。

class Student {
    private String name;
    private int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        //是不是两个引用 同时指向一个对象
        if (this == o) return true;
        //如果传进来是一个null
        if (o == null) return false;

        Student student = (Student) o;
        //
        return age == student.age &&
                Objects.equals(name, student.name);
    }
    //hashmap讲完后
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}
    public static void main(String[] args) {
        Student student1 = new Student("bit",1);
        Student student2 = new Student("bit",1);
        System.out.println(student1 == student2);//打印结果false
        System.out.println(student1.equals(student2));//打印结果true
    }

3.刨析PriorityQueue中的offer源码

offer中的源码：
我们可以看到，如果不是第一次入队，则要采用向上调整的方式入队。

点入siftUp方法当中，可以看到它会判定使用哪一个比较器。

实际上它们方法内部的操作都是一样的，只不过Comparator根据一些属性的排序的范围更广。参数x为即将要入队的元素。k为队尾的下标，e为父亲结点的元素此时调用compare方法，o1则为即将要插入的元素，o2为父亲结点元素。若compare方法内部返回的是o1-o2，则创建的是小堆。相反，若compare方法内部返回的是o2-o1，则创建的是大堆。

四、有关堆的面试题

1.堆排序（从小到大排）

面试题1：问若一个数组用堆排序要按照从小到大排序，需要如何排序？

答：一个数组根据从小到大排序，要创建大堆来排；一个数组根据从大到小排序，要创建小堆来排。

此处就以创建大堆为例。首先将堆顶的元素和堆中的最后一个元素交换，交换后再向下调整，调整后再与堆的倒数第二个元素进行交换。

代码：

public void HeapSort() {
        int end = usedSize-1;
        while(end>0) {
            int tmp = elem[0];
            elem[0]=elem[end];
            elem[end]=tmp;
            adjustDown(0,end);
            end--;
        }
    }

2.topK问题

面试题2：问如何从100w个数字中取得最小的10数字，打印出来的数字不用排序。

答：若要从N个数字中取得最小的K个数字，则需要创建大小为K的大堆来获取。若压迫从N个数字中取得最大的K个数字，则需要创建大小为K的小堆来获取。

此处以大堆为例。若创建堆的时候里面的元素小于K，则入队。用i来遍历100个数字，若其中有一个数字比堆顶元素小，则于与堆顶元素交换。

此处以10个数字取最小的3个数。

代码：

public static void topk(int[] array,int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        //大堆
        for (int i = 0; i < array.length; i++) {
            if(maxHeap.size() < k) {
                maxHeap.offer(array[i]);
            }else {
                int top = maxHeap.peek();
                if(top > array[i]) {
                    maxHeap.poll();
                    maxHeap.offer(array[i]);
                }
            }
        }
        System.out.println(maxHeap);
    }

    public static void main(String[] args) {
        int[] array = {1, 31, 2, 10, 7, 35, 21, 19, 56,45};//找到前3个最小的数据
        topk(array, 3);
    }
//打印结果：  [7, 1, 2]

3.查找和最小的K对数字

对应leetcode题

思路：此题涉及到topK问题。但是与上面的topK问题又有些不同。因为要找和最小的K对数字，因此要创建大堆来找。整个方法的返回类型为List<List<Integer>>，则我们可以将每对数字看作一个List<Integer>类型。并且创建一个PriorityQueue只放入List<Integer>类型的数据。跟topK一样，如果其中有top > nums1[i]+nums2[j]，则top出队而nums1[i]与nums2[j]变为List<Integer>类型入队。最后队列中只剩下k对最小的数字，将它们存入到List<List<Integer>>类型中返回即可。

class Solution {
        public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> queue = new PriorityQueue<>(k, new Comparator<List<Integer>>(){
            public int compare(List<Integer> o1,List<Integer> o2) {
                return (o2.get(0) + o2.get(1)) - (o1.get(0) + o1.get(1));
            }
        }); 
        //取最小值是为了防止两个数组一个比较少的时候【1】  【1,2,3】
        //并且nums1和nums2均为升序排列
        for(int i = 0; i < Math.min(nums1.length, k); i++){
            for(int j = 0; j < Math.min(nums2.length, k); j++){
                if(queue.size() < k) {
                    List<Integer> pair = new ArrayList<>();
                    pair.add(nums1[i]);
                    pair.add(nums2[j]);
                    queue.add(pair);
                }else {
                    int top = queue.peek().get(0) + queue.peek().get(1);
                    //大于K就出队列 
                    if(top > nums1[i]+nums2[j]){
                        List<Integer> pair = new ArrayList<>();
                        queue.poll();
                        pair.add(nums1[i]);
                        pair.add(nums2[j]);
                        queue.add(pair);
                    }
                }
            }
        }
        List<List<Integer>> res = new LinkedList<>();
        for(int i =0; i < k && !queue.isEmpty(); i++){
            res.add(queue.poll());
        }
        return res;
    }
}

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/ZJRUIII/article/details/122507928

内容来源于网络，如有侵权，请联系作者删除！

Java数据结构leetcode算法

相关文章

    查看更多
    微信公众号

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com