当前位置:网站首页>优先级队列(堆)
优先级队列(堆)
2022-07-05 08:46:00 【牧..】
文章目录
优先级队列(堆)
前言
在学习 堆之前,我们 回忆 一下 二叉树的 存储方式,
我们之前学习的 二叉树 是不是 链式 存储 以 left 和 right 连接起来
而接下来我们 学习的 堆 就是 顺序存储 一颗二叉树表示的。
二叉树的顺序存储
存储方式
使用数组保存二叉树结构,方式即将二叉树用层序遍历方式放入数组中。
一般只适合表示完全二叉树,因为非完全二叉树会有空间的浪费。
这种方式的主要用法就是堆的表示
下标关系
已知双亲(parent)的下标,则:
左孩子(left)下标 = 2 * parent + 1;
右孩子(right)下标 = 2 * parent + 2;
已知孩子(不区分左右)(child)下标,则:
双亲(parent)下标 = (child - 1) / 2;
堆(heap)
概念
堆逻辑上是一棵完全二叉树
堆物理上是保存在数组中
满足任意结点的值都大于其子树中结点的值,叫做大堆,或者大根堆,或者最大堆
反之,则是小堆,或者小根堆,或者最小堆
- 每颗二叉树的根节点都小于 左右孩子结点,
(小根堆/最小堆)
附上代码
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);
}
}
}
建立完 大根堆 ,接下来我们 来看一下 建堆的时间复杂度
但是 建堆的时间复杂度 为 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;
}
}
}
堆应用 - 优先级 队列
入堆 操作 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;
}
可以看到我们 入队并且我成了 交换
出堆操作 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;
}
}
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--;
}
}
分析完 在些代码是不是非常简单
接下来我们 来 完成
优先级队列插入元素
优先级队列在插入元素时有个要求:插入的元素不能是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);
}
}
回忆一下 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);
}
}
回忆完这些,那么 我们 使用优先级队列是不是 可以 ,传入比较器来完成比较的呢。这里显然是可以的
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);
}
}
这里 除了 比较器 和 使用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方法。
除了以上 这些方法 我们 还可以通过重写 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));
}
}
接下来就来完成一个 有关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;
}
}
边栏推荐
- Oracle advanced (III) detailed explanation of data dictionary
- 微信H5公众号获取openid爬坑记
- Business modeling of software model | overview
- 猜谜语啦(8)
- 猜谜语啦(142)
- Ecmascript6 introduction and environment construction
- Task failed task_ 1641530057069_ 0002_ m_ 000000
- asp. Net (c)
- Typescript hands-on tutorial, easy to understand
- golang 基础 —— golang 向 mysql 插入的时间数据和本地时间不一致
猜你喜欢
How to manage the performance of R & D team?
319. 灯泡开关
[daiy4] copy of JZ35 complex linked list
Run menu analysis
容易混淆的基本概念 成员变量 局部变量 全局变量
Programming implementation of ROS learning 6 -service node
Run菜单解析
Guess riddles (2)
The combination of deep learning model and wet experiment is expected to be used for metabolic flux analysis
猜谜语啦(10)
随机推荐
287. Looking for repeats - fast and slow pointer
My university
319. Bulb switch
猜谜语啦(8)
【日常训练】1200. 最小绝对差
Multiple linear regression (gradient descent method)
整形的分类:short in long longlong
The combination of deep learning model and wet experiment is expected to be used for metabolic flux analysis
Bit operation related operations
One dimensional vector transpose point multiplication np dot
ROS learning 1- create workspaces and function packs
Numpy 小坑:维度 (n, 1) 和 维度 (n, ) 数组相加运算后维度变为 (n, n)
Guess riddles (6)
Halcon shape_ trans
C语言标准函数scanf不安全的原因
Count of C # LINQ source code analysis
location search 属性获取登录用户名
Business modeling of software model | stakeholders
Mengxin summary of LIS (longest ascending subsequence) topics
Kubedm series-00-overview