【数据结构】优先级队列 — 堆

2024-08-28 21:20

本文主要是介绍【数据结构】优先级队列 — 堆,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

img

文章目录

  • 前言
  • 1. 优先级队列
    • 1.1 概念
    • 1.2 特性
  • 2. 堆
    • 2.1 概念
    • 2.2 存储方式
  • 3. 堆的模拟实现
    • 3.1 堆的创建
    • 3.2 堆的插入
    • 3.3 堆的删除
  • 4. PriorityQueue
    • 4.1 注意事项
    • 4.2 构造器介绍
    • 4.3 常用方法介绍
  • 5. 经典题型
  • 6. 结语


前言

我们之前学习过队列,它是遵循先进先出原则的数据结构,对应我们现实生活中的先到先得原则,比如排队时我们就可以使用队列的数据结构来模拟实现。但是,如果我们想优先操作队列中的某些数据,即让优先级高的元素先出队列,那么这种“普通的”先进先出队列就无法满足我们的需求。这时候就需要“优先级队列”来帮忙了


1. 优先级队列

1.1 概念

优先级队列(Priority Queue)是一种抽象数据类型,它类似于常规的队列或栈,但每个元素都有一个优先级。在优先级队列中,最小元素(或最大元素,根据实现)总是在队列的前端,并且最先被移除。它通常用于需要根据元素的重要性或紧急性进行排序的场景。比如:任务调度,网络数据传输,订单处理等等


1.2 特性

  1. PriorityQueue 类是实现优先级队列的常用类,底层实现是,而堆一棵特殊的完全二叉树(下面我们会重点讲解堆)
  2. 默认情况下,PriorityQueue 不允许插入重复的元素
  3. PriorityQueue 不是线程安全的。如果需要在多线程环境中使用,我们可以使用 PriorityBlockingQueue,它是线程安全的优先级队列实现

2. 堆

2.1 概念

在逻辑结构上,堆是一棵完全二叉树,而在存储结构上,堆是通过一个一维数组来存储元素的。它把所有元素按完全二叉树的层序遍历顺序,存储在一个数组当中。并且在堆中,每个节点都必须满足以下两种属性之一:

小根堆(最小堆):父节点的键值必须小于或等于其子节点的键值

大根堆(最大堆):父节点的键值必须大于或等于其子节点的键值

image-20240728160559698


2.2 存储方式

在上面我们提到了,“堆是通过一个一维数组来存储元素的”,而它的存储顺序就是按照完全二叉树的层序遍历来存储的,这样可以更高效的利用存储空间

因为使用数组存储堆可以方便地实现父节点到子节点的转换,所以我们可以给每一个节点记一个下标,通过下标来得到节点之间的父子关系:

我们规定根节点的下标为 0,设 i 为节点在数组中的下标,则有:

  • 父节点的下标:(i - 1) / 2
  • 左节点的下标: i * 2 + 1(如果得出来的数大于等于总的节点个数,则该节点没有左节点)
  • 右节点的下标: i * 2 + 2(如果得出来的数大于等于总的节点个数,则该节点没有右节点)

下面是简单的对应关系图:

image-20240728173958870


3. 堆的模拟实现

3.1 堆的创建

问题:把集合 {37,26,77,45,6,21,66,18,42} 创建成一个大根堆

思路:我们可以先把集合中的数据先按原始顺序排成一棵完全二叉树,接着再来调整,直至调整成为一个大根堆

image-20240804151549785

那要怎么调整呢?很简单,我们回忆一下大根堆的特点:在每棵子树中,父节点始终大于子节点。顺着这个思路,我们可以得出方法:从最后一棵子树开始调整,拿根节点和两个子节点比大小,如果出现任一子节点大于根节点,就交换两者的位置,这个过程叫做“根节点的向下调整”;然后接着往前找子树,一样的套路继续调整,直至所有的父节点都大于子节点,最后调整结束,得到的就是大根堆了

干讲可能有点抽象,我们根据代码来辅助理解:

首先我们创建一个数组 elem,并设定初始容量为 10,再使用 usedSize 来记录实际容量;接着初始化数组,把要传进去的数组赋值进去

public class MyHeap {public int[] elem;public int usedSize;//构造方法public MyHeap() {this.elem = new int[10];}//初始化,把数组一个个赋值进去public void init(int[] array) {for (int i = 0; i < array.length; i++) {elem[i] = array[i];usedSize++;}}
}

现在我们就得到了一组原始数组,它是一棵待排序的二叉树,接着开始调整

    //把 elem 数组中的数据调整为大根堆//时间复杂度为 O(n)public void createHeap() {//parent 为待调整树的父节点位置for (int parent = (usedSize - 1 - 1) / 2; parent >= 0 ; parent--) {shiftDown(parent, usedSize);}}//向下调整public void shiftDown(int parent, int end) {int child = 2 * parent + 1;//如果存在孩子节点,就进入循环while (child < end) {//判断最大的孩子是在左还是在右if (child + 1 < end && elem[child] < elem[child+1]) {child++;}//此时child一定是最大的孩子if (elem[child] > elem[parent]) {swap(child, parent);//交换完后再往下走parent = child;child = 2 * parent + 1;}else {//说明不需要调整,直接跳出break;}}}//交换位置public void swap(int i, int j) {int tmp = elem[i];elem[i] = elem[j];elem[j] = tmp;}

通过这么一套操作,我们就能得到大根堆,最后打印出来就是顺序就是正确的

image-20240804160842761

注意:在调整以 parent 为根的树时,要保证它的左右子树都已经是堆了才能向下调整,这也是我们从最后一棵子树开始调整的原因


时间复杂度:在最坏的情况中,我们需要对每个元素进行下沉操作,下沉操作的时间复杂度是 O(log n),因为堆是一个完全二叉树,其高度是 log(n)。但总的下沉次数是 n,因此平均到每个节点上的时间复杂度就是常数时间。这导致总的时间复杂度是 O(n)


3.2 堆的插入

将元素插入到堆中,插入后依然要满足堆的性质

实现思路

  1. 判断数组容量是否满了,满的话要扩容
  2. 把要插入的数据放在最后面,记得让 usedSize++,接着向上调整 (siftUp)
  3. 直到满足堆的性质

在原先的大根堆中插入 54,要求最后的结果还是大根堆

    //堆的插入public void offer(int val) {if (isFull()) {//满了就扩容elem = Arrays.copyOf(elem,2 * elem.length);}//在最后一个位置添加欲插入数据elem[usedSize] = val;usedSize++;//向上调整shiftUp(usedSize - 1);}//向上调整public void shiftUp(int child) {//先找到父节点int parent = (child - 1) / 2;//如果存在父节点,就进入循环while (parent >= 0) {if (elem[child] > elem[parent]) {swap(child, parent);//交换后,继续往上,看是否需要调整child = parent;parent = (child - 1) / 2;} else {break;}}}//判满public boolean isFull() {return usedSize == elem.length;}

image-20240804164034279


3.3 堆的删除

因为堆的特性,所以堆的删除我们通常指的是堆顶元素的删除,也就是说删除的是堆中最大(或者最小)的元素

实现思路:目的是为了尽可能的减少堆中元素的移动,保持堆的特性,因此我们可以采用逻辑删除

  1. 让堆顶元素和堆中最后一个元素交换
  2. 让 usedSize 减一(逻辑删除)
  3. 最后调整堆顶元素,向下调整

image-20240807175209051


删除堆中的堆顶元素,并要求删除后依然是一个大根堆

    //弹出第一个数字public int poll() {//先判断堆是不是空的if (isEmpty()) {return -1;}int old = elem[0];//记录下第一个数//把第一个和最后一个交换swap(0,usedSize - 1);//再排成大根堆usedSize--;//把最后一个数覆盖掉//第一个数向下调整,传入自己位置和堆的实际容量shiftDown(0,usedSize);//返回删除的元素return old;}public boolean isEmpty() {return usedSize == 0;}

除了 poll( ) 弹出,我们也可以来实现 peek( ),即瞥一眼堆顶元素,这个就很简单了

    //瞥一眼第一个元素public int peek() {//先判断堆是不是空的if (isEmpty()) {return -1;}return elem[0];}

4. PriorityQueue

4.1 注意事项

在使用之前,记得导包

import java.util.PriorityQueue;

接下来,我们来详细讲解使用时的一些注意点:

  1. 在 PriorityQueue 中放置的元素必须是可比较的,若插入无法比较大小的元素,就回抛出 ClassCastException 类型转换异常
  2. 在使用优先队列之前,应检查队列是否为空,避免在空队列上执行删除操作导致错误
  3. 不能插入 null,否则会抛出 NullPointerException 空指针异常
  4. PriorityQueue 默认情况下是小堆,若想建成的是大堆,则需要在构造时传入比较器
  5. PriorityQueue 不是线程安全的。如果需要在多线程环境中使用,我们可以使用 PriorityBlockingQueue,它是线程安全的优先级队列实现

4.2 构造器介绍

  1. 默认构造方法:创建一个空的优先队列,默认容量为 11

    public PriorityQueue() 
    
  2. 带初始容量的构造方法:可以指定初始容量

    public PriorityQueue(int initialCapacity)
    
  3. 带初始集合的构造方法:可以指定集合中的元素来初始化(实现了 Collection 接口的就可以接收,该集合的类型是包含 E 类型或其任何子类型的对象)

    public PriorityQueue(Collection<? extends E> c)
    
  4. 带比较器的构造方法:可以使用指定的比较器来初始化(比较器决定了元素的排序方式)

    public PriorityQueue(Comparator<? super E> comparator)
    
  5. 带初始集合和比较器的构造方法:可以使用指定集合中的元素和比较器来初始化

    public PriorityQueue(Collection<? extends E> c, Comparator<? super E> comparator)
    

在这里我们重点演示一下带比较器的构造方法:

class IntCmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1); //调换了原来的顺序}
}
public class Test {public static void main(String[] args) {//不传入比较器PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();priorityQueue1.offer(24);priorityQueue1.offer(52);priorityQueue1.offer(14);priorityQueue1.offer(37);System.out.println("小根堆:" + priorityQueue1);//传入比较器PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(new IntCmp());priorityQueue2.offer(24);priorityQueue2.offer(52);priorityQueue2.offer(14);priorityQueue2.offer(37);System.out.println("大根堆:" + priorityQueue2);}
}    

运行结果如下:

image-20240808170726831


4.3 常用方法介绍

方法描述
boolean offer(E e)将指定元素添加到此队列中
E peek( )返回队列头部的元素但不移除它。如果队列为空,则返回 null
E poll( )移除此队列头部的元素。如果队列为空,则返回 null
int size( )返回队列中的元素数量
boolean remove(Object o)从队列中移除指定的元素,移除成功返回 true,否则返回 false
void clear( )移除队列中的所有元素
boolean isEmpty( )如果队列为空,则返回 true

以上都是 PriorityQueue 的常用方法,有需要的话可以去该网址查询: PriorityQueue 的官方文档


5. 经典题型

Top-K 问题:求数据集合中前 K 个大(或者小)的元素

我们可以想想要怎么解决这个问题?最“朴素”的方法,当然是直接把数据集合排序,这样取到前 K 个大(或者小)的元素当然很简单

但是如果此时的数据量非常大,用排序法的时间复杂度一定不小,因此我们可以使用来求,那要怎么求呢?


力扣:最小K个数

image-20240814170551181


思路:问题要求我们找到前 k 个小的元素,“前 K 个”的意思就是我们不需要给所有数排序,只要把数据集合中的前 k 个小的元素就行

题目要求取出数据中前 k 个小的元素,我们就得建大堆(有点反直觉),把前 k 个数据先建成一个大堆,接着将剩余的 N - k 个元素依次和堆顶元素比较,比堆顶元素小就换,比完后堆中剩余的 k 个元素就是题目所要求的数

class IntCmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1); }
}class Solution {public int[] smallestK(int[] arr, int k) {//建大堆,只放前k个数PriorityQueue<Integer> minK = new PriorityQueue<>(new IntCmp());for (int i = 0; i < k; i++) {minK.offer(arr[i]);}//比较大小,若比堆顶元素小就放进去for (int i = k; i < arr.length; i++) {if(minK.size() != 0 && arr[i] < minK.peek()) {minK.poll();minK.offer(arr[i]);}}//返回int[] ret = new int[k];for (int i = 0; i < k; i++) {ret[i] = minK.poll();}return ret;}
}

当然,有很多其他更好的解法,博主在这只是提供一个简单的思路


6. 结语

今天我们介绍了优先级队列,重点掌握它的特性,还有堆的概念以及模拟实现,明白怎么使用 PriorityQueue 的常用方法,还有 Top—K 问题,也是非常经典~

希望大家能够喜欢本篇博客,有总结不到位的地方还请多多谅解。若有纰漏,希望大佬们能够在私信或评论区指正,博主会及时改正,共同进步!

这篇关于【数据结构】优先级队列 — 堆的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1115915

相关文章

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2431 poj 3253 优先队列的运用

poj 2431: 题意: 一条路起点为0, 终点为l。 卡车初始时在0点,并且有p升油,假设油箱无限大。 给n个加油站,每个加油站距离终点 l 距离为 x[i],可以加的油量为fuel[i]。 问最少加几次油可以到达终点,若不能到达,输出-1。 解析: 《挑战程序设计竞赛》: “在卡车开往终点的途中,只有在加油站才可以加油。但是,如果认为“在到达加油站i时,就获得了一

poj3750约瑟夫环,循环队列

Description 有N个小孩围成一圈,给他们从1开始依次编号,现指定从第W个开始报数,报到第S个时,该小孩出列,然后从下一个小孩开始报数,仍是报到S个出列,如此重复下去,直到所有的小孩都出列(总人数不足S个时将循环报数),求小孩出列的顺序。 Input 第一行输入小孩的人数N(N<=64) 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N),用

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

POJ2010 贪心优先队列

c头牛,需要选n头(奇数);学校总共有f的资金, 每头牛分数score和学费cost,问合法招生方案中,中间分数(即排名第(n+1)/2)最高的是多少。 n头牛按照先score后cost从小到大排序; 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心 public class Main {public static voi

Java并发编程之——BlockingQueue(队列)

一、什么是BlockingQueue BlockingQueue即阻塞队列,从阻塞这个词可以看出,在某些情况下对阻塞队列的访问可能会造成阻塞。被阻塞的情况主要有如下两种: 1. 当队列满了的时候进行入队列操作2. 当队列空了的时候进行出队列操作123 因此,当一个线程试图对一个已经满了的队列进行入队列操作时,它将会被阻塞,除非有另一个线程做了出队列操作;同样,当一个线程试图对一个空

web群集--nginx配置文件location匹配符的优先级顺序详解及验证

文章目录 前言优先级顺序优先级顺序(详解)1. 精确匹配(Exact Match)2. 正则表达式匹配(Regex Match)3. 前缀匹配(Prefix Match) 匹配规则的综合应用验证优先级 前言 location的作用 在 NGINX 中,location 指令用于定义如何处理特定的请求 URI。由于网站往往需要不同的处理方式来适应各种请求,NGINX 提供了多种匹