首页 > 其他分享 >优先级队列(堆)的知识点详解

优先级队列(堆)的知识点详解

时间:2024-06-21 23:29:13浏览次数:26  
标签:知识点 优先级 parent int elem PriorityQueue 详解 child

目录

1. 优先级队列

1.1 概念

2. 优先级队列的模拟实现

2.1 堆的概念

2.2 堆的存储方式

2.3 堆的创建

2.3.1 堆向下调整

2.4 堆的插入与删除

2.4.1 堆的插入

2.4.2 堆的删除

3.常用接口介绍

3.1PriorityQueue的特性

3.2 PriorityQueue常用接口介绍

1. 优先级队列

1.1 概念

前面介绍过队列,队列是一种先进先出(FIFO)的数据结构,但有些情况下,操作的数据可能带有优先级,一般出队 列时,可能需要优先级高的元素先出队列,该中场景下,使用队列显然不合适,比如:在手机上玩游戏的时候,如 果有来电,那么系统应该优先处理打进来的电话;初中那会班主任排座位时可能会让成绩好的同学先挑座位。

在这种情况下,数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象。这种数 据结构就是优先级队列(Priority Queue)。

2. 优先级队列的模拟实现

JDK1.8中的PriorityQueue底层使用了堆这种数据结构,而堆实际就是在完全二叉树的基础上进行了一些调整。

2.1 堆的概念

如果有一个关键码的集合K = {k0,k1, k2,…,kn-1},把它的所有元素按完全二叉树的顺序存储方式存储 在一 个一维数组中,并满足:Ki = K2i+1 且 Ki >= K2i+2) i = 0,1,2…,则称为 小堆(或大 堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

堆的性质:

1,堆中某个节点的值总是不大于或不小于其父节点的值;

2,堆总是一棵完全二叉树。

2.2 堆的存储方式

从堆的概念可知,堆是一棵完全二叉树,因此可以层序的规则采用顺序的方式来高效存储

注意:对于非完全二叉树,则不适合使用顺序方式进行存储,因为为了能够还原二叉树,空间中必须要存储空节 点,就会导致空间利用率比较低。

将元素存储到数组中后,可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标,则有:

如果i为0,则i表示的节点为根节点,否则i节点的双亲节点为 (i - 1)/2

如果2 * i + 1 小于节点个数,则节点i的左孩子下标为2 * i + 1,否则没有左孩子

如果2 * i + 2 小于节点个数,则节点i的右孩子下标为2 * i + 2,否则没有右孩子

2.3 堆的创建

2.3.1 堆向下调整

对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据,如果将其创建成堆呢?

根节点的左右子树已经完全满足堆的性质,因此只需将根节点向下调整好即可。

向下过程(以小堆为例): 1

. 让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子)

2. 如果parent的左孩子存在,即:child < size, 进行以下操作,直到parent的左孩子不存在

parent右孩子是否存在,存在找到左右孩子中最小的孩子,让child进行标

将parent与较小的孩子child比较,如果:

parent小于较小的孩子child,调整结束 否则:交换parent与较小的孩子child,交换完成之后,parent中大的元素向下移动,可能导致子 树不满足对的性质,因此需要继续向下调整,即parent = child;child = parent*2+1; 然后继续2。

注意:在调整以parent为根的二叉树时,必须要满足parent的左子树和右子树已经是堆了才可以向下调整。 时间复杂度分析:

最坏的情况即图示的情况,从根一路比较到叶子,比较的次数为完全二叉树的高度,即时间复杂度为O(log2N)

2.4 堆的插入与删除

2.4.1 堆的插入

堆的插入总共需要两个步骤:

1. 先将元素放入到底层空间中(注意:空间不够时需要扩容)

2. 将最后新插入的节点向上调整,直到满足堆的性质

2.4.2 堆的删除

注意:堆的删除一定删除的是堆顶元素。具体如下:

1. 将堆顶元素对堆中最后一个元素交换

2. 将堆中有效数据个数减少一个

3. 对堆顶元素进行向下调整

如下列代码则是堆的一些基本操作。

import java.util.Arrays;

public class TestHeap {
    public int []elem;
    public int usedSize;
    public TestHeap(){
        this.elem=new int[10];
    }
    public void initElem(int []array){
        for (int i = 0; i < array.length; i++) {
            elem[i]=array[i];
            usedSize++;
        }
    }
    public void createBigHeap(){
        for (int parent = (usedSize-1-1)/2;parent>=0 ; parent--) {
            siftDown(parent,usedSize);
        }
    }
    private void siftDown(int parent,int end){
        int child=2*parent+1;
        while(child<end){
            if(child+1<usedSize&&elem[child]<elem[child+1]){
                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;
    }
    public int pool(){
        int tmp=elem[0];
        swap(0,usedSize-1);
        usedSize--;
        siftDown(0,usedSize);
        return tmp;
    }
    public void offer(int val){

        if(isFull()){
            //扩容
            this.elem= Arrays.copyOf(elem,2*elem.length);
        }
        //插入元素
        elem[usedSize]=val;
        usedSize++;
        //向上调整
        siftUp(usedSize-1);
    }
    private void siftUp(int child){
        int parent=(child-1)/2;
        while(child>0){
        if(elem[child]>elem[parent]){
            swap(child,parent);
            child=parent;
            parent=(child-1)/2;
        }else{
            break;
        }
        }
    }
    public boolean isFull(){
        return usedSize== elem.length;
    }
}

3.常用接口介绍

3.1PriorityQueue的特性

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,本文主要介绍PriorityQueue。

关于PriorityQueue的使用要注意:

1. 使用时必须导入PriorityQueue所在的包,即:

import java.util.PriorityQueue;

2. PriorityQueue中放置的元素必须要能够比较大小,不能插入无法比较大小的对象,否则会抛出 ClassCastException异常

3. 不能插入null对象,否则会抛出NullPointerException

4. 没有容量限制,可以插入任意多个元素,其内部可以自动扩容

5. 插入和删除元素的时间复杂度为

6. PriorityQueue底层使用了堆数据结构

7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素

3.2 PriorityQueue常用接口介绍

1. 优先级队列的构造

此处只是列出了PriorityQueue中常见的几种构造方式。

构造器功能介绍
PriorityQueue()创建一个空的优先级队列,默认容量是11
PriorityQueue(int initialCapacity)创建一个初始容量为initialCapacity的优先级队列,注意: initialCapacity不能小于1,否则会抛IllegalArgumentException异 常
PriorityQueue(Collection c)用一个集合来创建优先级队列

2. 插入/删除/获取优先级最高的元素

函数名功能介绍
boolean offer(E e)插入元素e,插入成功返回true,如果e对象为空,抛出NullPointerException异常,时 间复杂度,注意:空间不够时候会进行扩容
E peek()获取优先级最高的元素,如果优先级队列为空,返回null
E poll()移除优先级最高的元素并返回,如果优先级队列为空,返回null
int size()获取有效元素的个数
void clear()清空
boolean isEmpty()检测优先级队列是否为空,空返回true

标签:知识点,优先级,parent,int,elem,PriorityQueue,详解,child
From: https://blog.csdn.net/2302_80113478/article/details/139392172

相关文章

  • 面试题(TCP/IP协议)详解三次握手
    TCP/IP协议中的三次握手我们首先来了解一下TCPTCP(TransmissionControlProtocol,传输控制协议)是一个面向连接的、可靠的、基于字节流的传输层通信协议。以下是TCP的一些主要特点:面向连接:在数据传输之前,TCP必须先建立连接(三次握手),在数据传输结束后,还要终止这个连接(......
  • 【数据结构与算法 刷题系列】判断链表是否有环(图文详解)
                   ......
  • Java变量技术详解
    在Java编程中,变量是存储数据的基本单元,理解变量的概念、类型和使用方法是编写高效代码的基础。本文将详细介绍Java中的变量,包括变量的定义、类型、作用域和常见用法,并通过代码示例来帮助理解这些概念。一、变量的定义和声明在Java中,变量的定义和声明遵循以下格式:typevar......
  • 数据结构——队列(Queue)详解
    1.队列(Queue)1.1概念队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(FirstInFirstOut)的性质入队列:进行插入操作的一端称为队尾(Tail/Rear)出队列:进行删除操作的一端称为队头(Head/Front)2队列的使用在Java中,Queue是个接......
  • 【机器学习】Transformer框架理论详解和代码实现
    1.引言1.1.讨论背景在本文中,我们将深入探讨近两年最具影响力的架构之一:Transformer模型。自从2017年Vaswani等人发表划时代论文《AttentionIsAllYouNeed》以来,Transformer架构便在众多领域,尤其是自然语言处理(NLP)领域,不断刷新性能上限。这种拥有庞大参数量的Transform......
  • Kotlin 数据类型详解:数字、字符、布尔值与类型转换指南
    Kotlin数据类型在Kotlin中,变量的类型由其值决定:示例valmyNum=5//IntvalmyDoubleNum=5.99//DoublevalmyLetter='D'//CharvalmyBoolean=true//BooleanvalmyText="Hello"//String然而,从上一章中你了解到,如果需......
  • 消息队列kafka中间件详解:案例解析(第10天)
    系列文章目录1-消息队列(熟悉)2-Kafka的基本介绍(掌握架构,其他了解)3-Kafka的相关使用(掌握kafka常用shell命令)4-Kafka的PythonAPI的操作(熟悉)文章目录系列文章目录前言一、消息队列(熟悉)1、产生背景2、消息队列介绍2.1常见的消息队列产品2.2应用场景2.3消息队列中两......
  • C语言--指针详解(二)
    C语言--指针详解(二)一.前言二.指针运算(1)指针+-整数(2)指针-指针(3)指针的关系运算三.指针类型分类及详解(1)整型指针(2)浮点型指针(3)字符指针(4)特殊指针类型void*(5)函数指针(6)数组指针(7)结构体指针五.指针与数组5.1数组名的理解5.2数组指针5.3指......
  • Windows C++ 应用软件开发从入门到精通详解
    目录1、引言2、IDE开发环境介绍2.1、VisualStudio 2.2、QTCreator3、Windows平台实用小工具介绍3.1、代码编辑器VSCode3.2、代码查看编辑器SourceInsight3.3、文本编辑器Notepad++3.4、文件搜索工具Everything4、C++语言特性4.1、熟悉泛型编程4.2、了解......
  • 详解pip换源步骤,打造极速Python开发环境
    在当今日益数字化的世界中,Python及其包管理工具pip已成为开发者们不可缺少的工具。Python的广泛应用,从数据分析到人工智能,从Web开发到科学计算,都离不开大量高质量的库和包的支持。但是,在安装和管理这些库和包时,网络速度和源的可靠性往往成为制约效率的瓶颈。为了解决这一问题,......