• 优先级队列(堆)

    文章目录

    优先级队列(堆)

    前言

    在学习 堆之前，我们 回忆 一下 二叉树的 存储方式，

    我们之前学习的 二叉树 是不是 链式 存储 以 left 和 right 连接起来

    而接下来我们 学习的 堆 就是 顺序存储 一颗二叉树表示的。

    二叉树的顺序存储

    存储方式

    使用数组保存二叉树结构，方式即将二叉树用层序遍历方式放入数组中。
    一般只适合表示完全二叉树，因为非完全二叉树会有空间的浪费。
    这种方式的主要用法就是堆的表示

    在这里插入图片描述

    下标关系

    已知双亲(parent)的下标，则：

    左孩子(left)下标 = 2 * parent + 1;
    右孩子(right)下标 = 2 * parent + 2;

    已知孩子（不区分左右）(child)下标，则：

    双亲(parent)下标 = (child - 1) / 2;

    堆(heap)

    概念

    1. 堆逻辑上是一棵完全二叉树

    2. 堆物理上是保存在数组中

    3. 满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆

    4. 反之，则是小堆，或者小根堆，或者最小堆

    1. 每颗二叉树的根节点都小于 左右孩子结点，

    （小根堆/最小堆）

    1. 每颗二叉树的根节点都大于左右孩子结点

      (大根堆/ 最大堆)

      建立一个堆（大根堆）

    在这里插入图片描述

    附上代码

    public class TestHeap {

    public int[] elem;
    public int usedSize;
    public TestHeap(){
        this.elem = new int[10];
    }

    /**
     * 向下调整函数 实现
     * @param parent 每棵树的根结点
     * @param len 每棵树的调整结束位置
     */
    public void shifDown(int parent,int len) {
        int child = 2 * parent + 1;
        //1 最起码 有一个孩子 （左孩子）
        while(child < len) {
            // 9 + 1 == 10 那么就进入不了 循环
            if(child + 1< len && elem[child] < elem[child+1]) {
                child++;
            }
            if(elem[parent] < elem[child]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }

        }
    }
    // 交换完成后需要继续向下 检测
    public void createHeap(int[] array) {
        for(int i = 0;i<array.length;i++) {
            elem[i] = array[i];
            this.usedSize++;
        }
        for(int parent = (usedSize - 1-1)/2;parent >= 0;parent--) {
            // 调整
            shifDown(parent,usedSize);
        }
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    建立完 大根堆 ，接下来我们 来看一下 建堆的时间复杂度
    在这里插入图片描述

    但是 建堆的时间复杂度 为 O(n),下面 文章说明了，可以去看看

    堆排序中建堆过程时间复杂度O(n)怎么来的？

    建立小堆只需要 在 建立大堆的基础上 改一下即可

    附上代码

        public void shifDown2(int parent,int len) {
        int child = 2 * parent + 1;
        while(child < len) {
            if(child + 1 < len && elem[child] > elem[child +1]) {
                child++;
            }
            if(elem[parent] > elem[child]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    堆应用 - 优先级 队列

    在这里插入图片描述

    入堆 操作 offer

    在这里插入图片描述

     private void shiftUp(int child) {
        int parent = (child - 1) / 2;
        while(child != 0) {
            if(elem[parent] < elem[child]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;
                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;
            // 注意 这里 传入的参数  usedSize - 1
            shiftUp(usedSize - 1);
    }
    public boolean isFull() {
        return usedSize == elem.length;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    在这里插入图片描述

    可以看到我们 入队并且我成了 交换

    出堆操作 poll

    在这里插入图片描述

    附上代码

    public class TestHeap {

    public int[] elem;
    public int usedSize;
    public TestHeap(){
        this.elem = new int[10];
    }

    /**
     * 向下调整函数 实现
     * @param parent 每棵树的根结点
     * @param len 每棵树的调整结束位置
     */
    public void shifDown(int parent,int len) {
        int child = 2 * parent + 1;
        //1 最起码 有一个孩子 （左孩子）
        while(child < len) {
            // 9 + 1 == 10 那么就进入不了 循环
            if(child + 1< len && elem[child] < elem[child+1]) {
                child++;
            }
            if(elem[parent] < elem[child]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }

        }
    }

    // 交换完成后需要继续向下 检测
    public void createHeap(int[] array) {
        for(int i = 0;i<array.length;i++) {
            elem[i] = array[i];
            this.usedSize++;
        }
        for(int parent = (usedSize - 1-1)/2;parent >= 0;parent--) {
            // 调整
            shifDown(parent,usedSize);
        }
    }
    private void shiftUp(int child) {
        int parent = (child - 1) / 2;
        while(child != 0) {
            if(elem[parent] < elem[child]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;
                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;
            // 注意 这里 传入的参数  usedSize - 1
            shiftUp(usedSize - 1);
    }
    public boolean isFull() {
        return usedSize == elem.length;
    }
    // 出堆操作
    public int poll() {
        if(isEmpty()) {
            throw new RuntimeException("优先级队列为空 ！");
        }
        // 交换 0 下标和 最后 一个元素
        int tmp = elem[0];
        elem[0] = elem[usedSize-1];
        elem[usedSize-1] = tmp;
        usedSize--;
        // 调整 0 下标元素
        shifDown(0,usedSize);
        return tmp;
    }
    public boolean isEmpty() {
        return usedSize == 0;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89

    Topk问题非代码实现

    接下俩 先来了解一下 topk 问题

    在这里插入图片描述

    我们 先来 学习一下堆排序，学习完，我们才能更好的理解 有关 topk问题 的oj题 、

    堆排序

    在这里插入图片描述

    接下来我们 来代码实现

      public void shifDown(int parent,int len) {
        int child = 2 * parent + 1;
        //1 最起码 有一个孩子 （左孩子）
        while(child < len) {
            // 9 + 1 == 10 那么就进入不了 循环
            if(child + 1< len && elem[child] < elem[child+1]) {
                child++;
            }
            if(elem[parent] < elem[child]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }

        }
    }

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    分析完 在些代码是不是非常简单

    接下来我们 来 完成

    优先级队列插入元素

    优先级队列在插入元素时有个要求：插入的元素不能是null或者元素之间必须要能够进行比较，为了简单起见，我们只是插入了Integer类型，那优先级队列中能否插入自定义类型对象呢？

    在这里插入图片描述

    插入 ，和交换操作 的 源码 分析

    在这里插入图片描述

    附上代码

    class Card implements Comparable<Card> {
    public int rank; // 数值
    public String suit; // 花色
    public Card(int rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }

    @Override
    public int compareTo(Card o) {
        return this.rank - o.rank;
        //这里 换成 0.rank - this.rank,就换成了 大堆
    }

    @Override
    public String toString() {
        return "Card{" +
                "rank=" + rank +
                ", suit='" + suit + '\'' +
                '}';
    }
}
public class Test {
    public static void main(String[] args) {
        // 默认就是一个小堆
        PriorityQueue<Card> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(new Card(2,"♥"));
        priorityQueue.offer(new Card(1,"♥"));
        System.out.println(priorityQueue);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    回忆一下 Comparable 接口 ，他是不是 对类侵入性太强， 一旦写好了，根据那种规则比较那么就不能轻易进行修改了。

    那么这里 我 们就 可以 使用 单独的 写 一些比较器。

    class  RankComparator implements Comparator<Card> {

    @Override
    public int compare(Card o1, Card o2) {
        return o1.rank - o2.rank;
    }
}
public class Test {
    public static void main(String[] args) {
        Card card1 = new Card(1,"♥");
        Card card2 = new Card(2,"♥");
        RankComparator rankComparator = new RankComparator();
        int ret = rankComparator.compare(card1,card2);
        System.out.println(ret);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    回忆完这些，那么 我们 使用优先级队列是不是 可以 ，传入比较器来完成比较的呢。这里显然是可以的

    public class Test {
    public static void main(String[] args) {
        RankComparator rankComparator = new RankComparator();
        Card card1 = new Card(1,"♥");
        Card card2 = new Card(2,"♥");
        // 直接传入 比较器
        PriorityQueue<Card> priorityQueue = new PriorityQueue<>(rankComparator);
        priorityQueue.offer(card1);
        priorityQueue.offer(card2);
        System.out.println(priorityQueue);

    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    在这里插入图片描述

    这里 除了 比较器 和 使用Comparable 中 compareTo 方法比较之外还能这样写

    public static void main(String[] args) {
        RankComparator rankComparator = new RankComparator();
        Card card1 = new Card(1,"♥");
        Card card2 = new Card(2,"♥");
        PriorityQueue<Card> priorityQueue = new PriorityQueue<>(new Comparator<Card>() {
            @Override
            public int compare(Card o1, Card o2) {
                return o1.rank - o2.rank;
            }
        });
        priorityQueue.offer(card1);
        priorityQueue.offer(card2);
        System.out.println(priorityQueue);

    }

这里 就不需要 创建 比较器 也能比较，
    这里 就相当于 一个内部类，重写了 compare方法。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    在这里插入图片描述

    除了以上 这些方法 我们 还可以通过重写 equals 方法来进行比较
    在这里插入图片描述

    三种比较方式 区别

    在这里插入图片描述

    Topk 问题 代码实现

    上面 我们 已经分析完 Topk 的 思路 ，这里 代码实现

    public class Topk2 {
    /**
     * 求数组中的前K 个最小的元素
     * @param array
     * @param k
     * @return
     * 采用 大根堆
     */
    public static int[] topk(int[] array,int k){
        // 1.创建一个大小为k 的大根堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                // 这样比较就为大堆
                return o2 - o1;
            }
        });
        // 2.遍历数组当中的元素，前k个元素放到堆中
      for(int i = 0;i<array.length;i++){
          if(maxHeap.size() < k) {
            maxHeap.offer(array[i]);
          }else {
              int tmp = maxHeap.peek();
              if(tmp > array[i]) {
                  // 先弹出
                  maxHeap.poll();
                  // 在存入
                  maxHeap.offer(array[i]);
              }
          }
      }
      int[] arr = new int[k];
        for(int i = 0;i < k;i++) {
           arr[i] = maxHeap.poll();
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] array = {18,21,8,10,34,12};
     int[] ret =  topk(array,3);
        System.out.println(Arrays.toString(ret));
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    在这里插入图片描述

    接下来就来完成一个 有关topk 的 oj 题

    查找和最小的 K 对数字

    在这里插入图片描述

    class Solution {
      public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> maxHeap = new PriorityQueue<>(k, new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                // 创建大根堆 的比较方法
                return (o2.get(0)+o2.get(1)) - (o1.get(0)+o1.get(1));
            }
        });
        for(int i = 0;i< Math.min(k,nums1.length);i++) {
            for(int j = 0;j< Math.min(k,nums2.length);j++) {
                if(maxHeap.size() < k) {
                    List<Integer> tmpList = new ArrayList<>();
                    tmpList.add(nums1[i]);
                    tmpList.add(nums2[j]);
                    maxHeap.offer(tmpList);
                }else {
                    int top = maxHeap.peek().get(0) + maxHeap.peek().get(1);
                    if(top > (nums1[i] + nums2[j])) {
                        List<Integer> tmpList = new ArrayList<>();
                        maxHeap.poll();
                        tmpList.add(nums1[i]);
                        tmpList.add(nums2[j]);
                        maxHeap.offer(tmpList);
                    }
                }
            }
        }
        List<List<Integer>> ret = new ArrayList<>();
          // 这里 注意 k 如果 大于 数对 就要判断，堆是否为空
        for(int i = 0;i<k && !maxHeap.isEmpty();i++) {
            ret.add(maxHeap.poll());
        }
        return ret;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    查看源图像在这里插入图片描述

  • 相关阅读:
    Linux08——面试题篇
    分类预测 | Matlab实现CNN-BiLSTM-SAM-Attention卷积双向长短期记忆神经网络融合空间注意力机制的数据分类预测
    SQL 时间范围和时间粒度
    什么是向上管理
    unity 血条跟随
    交换机和路由器技术-25-OSPF多区域配置
    Java的Lambda表达式学习笔记：使用lambda表达式
    基于JAVA西宁市农副产品物流信息系统计算机毕业设计源码+数据库+lw文档+系统+部署
    绘制三元图、颜色空间图：R语言代码
    OBS-Studio-27.2.4-Full-Installer-x64.exe 下载
  • 原文地址：https://blog.csdn.net/mu_tong_/article/details/125587821