| 优先队列算法（ Priority queue） | 您所在的位置：网站首页 › 如何实现优先队列发展模式的方法 › 优先队列算法（ Priority queue） |
优先队列算法（ Priority queue）
|
优先队列算法（ Priority queue）
前言：源码阅读Priority queue类：底层分析：依据优先级构造堆复杂度分析：Lambda表达式构建Priority queue例题实现：
前言：
引入：优先队列问题常用于降低时间复杂度，达到快速搜索的目的 源码阅读Priority queue类：
下面我们来谈一谈实现的原理 优先队列是利用堆来实现的 堆可以看做的一颗完全二叉树的顺序存储结构，（大顶堆：每个结点的值都大于等于左右孩子的值） 优先队列的两个基本操作：（都在维护堆序性） 出队：堆顶出队，最后一个记录，代替堆顶的位置，重新调整为堆 入队：将新元素放入树中的末尾，再调整为堆 一个大顶堆构建完成后，且堆顶出队后，其他结点都满足最大堆的定义，只需要将堆顶执行下沉操作， 即都可再次调整为堆 出队后的操作：下沉（在已经构建好堆的基础上再次维护堆）： 堆顶与左右孩子比较，若大则已经满足无需构建，若比孩子小，则与较大的孩子交换，交换到新位置后继续向下比较 （这里在堆排序里详细探讨过） 比较次数最多为树的高度 入队后的操作：上浮 （比较次数：最多为树的高度h） 入队时，将新元素放入最后一个记录之后，例如29入队，放在12的后面
优先队列的时间复杂度为：logn（而线性的复杂度为n，有时为二维复杂度将程指数阶，使用优先队列将大大提升效率） 这是是由于上浮和下沉中最大遍历范围为树的高度，完全二叉树的树高为h=[logn]+1 Lambda表达式构建Priority queue
Lambda作为排序参口传递进方法中，也就是说Lambda可以替代Comparator接口作为排序参数 Lambda表达式的基本语法: ( p a r a m e t e r s ) − > e x p r e s s i o n 或 ( p a r a m e t e r s ) − > s t a t e m e n t s ; (parameters) -> expression 或 (parameters) ->{ statements; } (parameters)−>expression或(parameters)−>statements; // 1. 不需要参数,返回值为 5 () -> 5 // 2. 接收一个参数(数字类型),返回其2倍的值 x -> 2 * x // 3. 接受2个参数(数字),并返回他们的差值 (x, y) -> x – y // 4. 接收2个int型整数,返回他们的和 (int x, int y) -> x + y // 5. 接受一个 string 对象,并在控制台打印,不返回任何值(看起来像是返回void) (String s) -> System.out.print(s)那么我们如何实现以小顶堆进行排序的优先级队列呢 PriorityQueue heap=new PriorityQueue((n1,n2)->n1-n2);（这里的泛型最好加上） 解释：参数为两个数，返回两个值的差 差为1 则交换，差为负数和0不交换，维护了升序排列 例题实现： 找出第 K 大的异或坐标值 给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。矩阵中坐标 (a, b) 的 值 可由对所有满足 0 int m = mat.length, n = mat[0].length; int[][] sum = new int[m + 1][n + 1]; PriorityQueue q = new PriorityQueue(k, (a, b)->a - b); for (int i = 1; i sum[i][j] = sum[i - 1][j] ^ sum[i][j - 1] ^ sum[i - 1][j - 1] ^ mat[i - 1][j - 1]; if (q.size() if (sum[i][j] > q.peek()) {//比堆顶元素大，加入进堆中并维护 q.poll(); q.add(sum[i][j]); } } } } return q.peek(); } } |
如果不理解上述过程建议看我的博客：堆排序
这里我们只需要 PriorityQueue queue =new PriorityQueue(大小，比较器类型);【本文地址】