数据结构中堆及优先级队列的特色解析

文章标题:

数据结构里堆与优先级队列的特性剖析

文章内容:

文章目录

    • 📕1. 堆(Heap)
        • ✏️1.1 堆的概念
      • ✏️1.2 堆的存储形式
      • ✏️1.3 堆的构建
      • ✏️1.4 堆的插入
      • ✏️1.5 堆的删除
    • 📕2. 优先级队列(PriorityQueue)
        • ✏️2.1 堆和优先级队列的关联
      • ✏️2.2 优先级队列的构造途径
      • ✏️2.3 优先级队列的常用操作
    • 3. Java对象的比较
        • 3.1 基于Comparble接口的比较
      • 3.2 基于比较器的比较

📕1. 堆(Heap)

✏️1.1 堆的概念

堆属于一种特殊的完全二叉树,它具备这样的特性:父节点的值要么始终不大于子节点的值,要么始终不小于子节点的值。其中,根节点最大的堆被称作最大堆或者大根堆,根节点最小的堆则叫做最小堆或者小根堆。

堆满足如下两个特性:
1. 堆中任意一个节点的值都不会大于或小于其根节点的值
2. 堆始终是一棵完全二叉树

在这里插入图片描述

✏️1.2 堆的存储形式

从堆的概念可知,堆是一棵完全二叉树,所以能够按照层序的规则采用顺序的方式来高效存储。

对于非完全二叉树而言,不适合运用顺序的方式进行存储,因为要还原二叉树的话,空间中得存储空节点,这会使得空间利用率比较低。

在这里插入图片描述
当元素存储到数组中后,假设i为节点在数组中的下标,那么有:

  1. 若i为0,则该节点为根节点;不然,i节点的双亲节点是 (i - 1)/2
  2. 若2 * i + 1 小于节点个数,那么节点i的左孩子下标为2 * i + 1,否则没有左孩子
  3. 若2 * i + 2 小于节点个数,那么节点i的右孩子下标为2 * i + 2,否则没有右孩子
✏️1.3 堆的构建

要构建堆,首先得了解向下调整(这里以构建小根堆为例):

  1. 将想要调整的节点标记为parent,child为该节点的左孩子(若存在孩子节点,必定是左孩子)
  2. 若存在左孩子节点,即child < size(数组元素个数)时,进行如下操作,直到child < size的条件不成立
    2.1 查看parent的右孩子是否存在,找出左右孩子中较小的那个,并用child标记(若右孩子比左孩子小,则child += 1)
    2.2
    将parent与child进行比较,如果parent <= child,那么调整结束;否则进行元素交换,交换之后,新构建的子树可能不再满足小根堆的条件,所以需要将parent = child,child = parent * 2 + 1,然后重复2步骤。这就是向下调整。
public void siftDown(int[] arr, int parent) {
    // 此时child标记左孩子,因为parent右孩子节点的话必然先有左孩子
    int child = parent * 2 + 1;
    int size = arr.length;
    while (child < size) {
        // 如果右孩子存在,找到左右孩子中较小的孩子,用child标记
        if (child + 1 < size && arr[child] < arr[child + 1]) {
            child += 1;
        }
        // 如果双亲比其最小的孩子还小,说明该结构已满足堆的特性
        if (arr[parent] <= arr[child]) {
            break;
        } else {
            // 将双亲与较小的孩子交换
            int t = arr[parent];
            arr[parent] = arr[child];
            arr[child] = t;
            // parent中大的元素往下移动,可能导致子树不满足堆的性质,因此需继续向下调整
            parent = child;
            child = parent * 2 + 1;
        }
    }
}

了解了向下调整后,对于任意给定的数据,该如何构建成小根堆呢?

public void createHeap(int[] arr) {
    // 找到倒数第一个非叶节点,从该节点位置开始往前一直到根节点,遇到一个节点就应用向下调整
    int root = (arr.length - 2) / 2;
    for (; root >= 0; root--) {
        siftDown(arr, root);
    }
}

还需注意,建堆的时间复杂度为O(N);

✏️1.4 堆的插入

堆的插入总共分为两个步骤:

  1. 先把元素放到数组的最后一个空间中(数组长度不够时需要扩容)
  2. 利用向上调整新插入的节点,直至满足堆的特性

在这里插入图片描述

向上调整:

public void siftUp(int child) {
    // 以创建小根堆为例
    // 找到child的根节点
    int parent = (child - 1) / 2;

    while (child > 0) {
        // 如果双亲比孩子小,parent满足堆的性质,调整结束
        if (arr[parent] < arr[child]) {
            break;
        } else {
            // 将双亲与孩子节点进行交换
            int tmp = arr[parent];
            arr[parent] = arr[child];
            arr[child] = tmp;
        }

        // 小的元素向下移动,调整后的子树可能不满足堆的性质,因此需继续向上调整
        child = parent;
        parent = (child - 1) / 2;
    }
}

插入数据:

/**
* 插入数据:
* 每次插入到当前堆的最后一个(数组的最后一个),然后向上调整
*/
public void offer(int val) {
    if (isFull()) {
        elem = Arrays.copyOf(elem, 2 * elem.length);
    }
    elem[size] = val;
    // 调整
    siftUp(size);
    size++;
}
✏️1.5 堆的删除

堆的删除包含以下步骤:

  1. 将堆顶元素与堆中最后一个元素交换
  2. 将堆中有效数据减少一个
  3. 对堆顶元素进行向下调整

注意:堆的删除一定删除的是堆顶元素

📕2. 优先级队列(PriorityQueue)

之前我们已经学习过队列,队列是一种先进先出(FIFO)的数据结构,但有些情况下,操作的数据可能带有优先级,出队列时,可能需要优先级高的元素先出队列。比如:在手机上玩游戏的时候,如果有来电,那么系统应该优先处理打进来的电话。该场景下,使用队列显然不合适,因此数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象。这种数据结构就是优先级队列(PriorityQueue)。

✏️2.1 堆和优先级队列的关联

首先要明确,堆是一种数据结构,优先级队列也是一种数据结构,二者是完全不同的。优先队列的重点在于优先,队列只是形式。优先级队列不仅可以用堆来实现,用链表也能模拟实现,不过在JDK1.8中,PriorityQueue的底层实现采用了堆这种数据结构。

✏️2.2 优先级队列的构造途径

在这里插入图片描述

注意:默认情况下,PriorityQueue队列是小堆,如果需要大堆需要用户提供比较器

✏️2.3 优先级队列的常用操作

在这里插入图片描述
优先级队列的扩容说明:
• 如果容量小于64时,是按照oldCapacity的2倍方式扩容的
• 如果容量大于等于64,是按照oldCapacity的1.5倍方式扩容的
• 如果容量超过MAX_ARRAY_SIZE,按照MAX_ARRAY_SIZE来进行扩容

3. Java对象的比较

在SE阶段中,我们介绍了引用类型变量使用equals()方法进行比较,基本数据类型变量使用大于号小于号进行比较,故以上两种方法此处不再赘述。

3.1 基于Comparble接口的比较

Comparble是JDK提供的泛型的比较接口类,源码实现具体如下:

public interface Comparable<E> {
    // 返回值:
    // < 0: 表示 this 指向的对象小于 o 指向的对象
    // == 0: 表示 this 指向的对象等于 o 指向的对象
    // > 0: 表示 this 指向的对象大于 o 指向的对象
    int compareTo(E o);
}

对于用户定义类型,如果要想按照大小的方式进行比较时:
在定义类时,实现Comparble接口即可,然后在类中重写compareTo方法。

public class Card implements Comparable<Card> {

    public int rank; // 数值
    public String suit; // 花色

    public Card(int rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }
    // 根据数值比较,不管花色
    // 这里我们认为 null 是最小的

    @Override
    public int compareTo(Card o) {
        if (o == null) {
            return 1;
        }
        return this.rank - o.rank;
    }

    public static void main(String[] args) {
        Card p = new Card(1, "♠");
        Card q = new Card(2, "♠");
        Card o = new Card(1, "♠");
        System.out.println(p.compareTo(o)); // == 0,表示牌相等
        System.out.println(p.compareTo(q)); // < 0,表示 p 比较小
        System.out.println(q.compareTo(p)); // > 0,表示 q 比较大
    }
}
3.2 基于比较器的比较

Comparator是java.util包中的泛型接口类,源码如下:

public interface Comparator<T> {
    // 返回值:
    // < 0: 表示 o1 指向的对象小于 o2 指向的对象
    // == 0: 表示 o1 指向的对象等于 o2 指向的对象
    // > 0: 表示 o1 指向的对象等于 o2 指向的对象
    int compare(T o1, T o2);
}

按照比较器方式进行比较,具体步骤如下:

  1. 用户自定义比较器类,实现Comparator接口
  2. 重写Comparator中的compare方法
import java.util.Comparator;

class Card {
    public int rank; // 数值
    public String suit; // 花色

    public Card(int rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }
}

class CardComparator implements Comparator<Card> {
    // 根据数值比较,不管花色
    // 这里我们认为 null 是最小的

    @Override
    public int compare(Card o1, Card o2) {
        if (o1 == o2) {
            return 0;
        }
        if (o1 == null) {
            return -1;
        }
        if (o2 == null) {
            return 1;
        }
        return o1.rank - o2.rank;
    }

    public static void main(String[] args) {
        Card p = new Card(1, "♠");
        Card q = new Card(2, "♠");
        Card o = new Card(1, "♠");
        // 定义比较器对象
        CardComparator cmptor = new CardComparator();
        // 使用比较器对象进行比较
        System.out.println(cmptor.compare(p, o)); // == 0,表示牌相等
        System.out.println(cmptor.compare(p, q)); // < 0,表示 p 比较小
        System.out.println(cmptor.compare(q, p)); // > 0,表示 q 比较大
    }
}

文章整理自互联网,只做测试使用。发布者:Lomu,转转请注明出处:https://www.it1024doc.com/12849.html

(0)
LomuLomu
上一篇 13小时前
下一篇 11小时前

相关推荐

  • Java集成Dify AI服务的客户端工具包

    项目源码 Dify Java SDK是为Java开发者设计的开源工具包,专门用于与Dify AI平台的无缝对接。该工具包全面覆盖了Dify平台的各项API功能,使开发者能够便捷地在Java应用中调用AI服务。 核心功能 本工具包具备以下主要特性: 1. 多场景应用支持 智能对话系统:通过专用接口实现多轮对话管理 文本自动生成:支持各类文本内容的智能创作 流程…

    未分类 2025 年 5 月 13 日
    15000
  • 2024 IDEA最新激活码,IDEA永久免费激活码2024-12-30 更新

    IDEA 2024最新激活码 以下是最新的IDEA激活码,更新时间:2024-12-30 🔑 激活码使用说明 1️⃣ 复制下方激活码 2️⃣ 打开 IDEA 软件 3️⃣ 在菜单栏中选择 Help -> Register 4️⃣ 选择 Activation Code 5️⃣ 粘贴激活码,点击 Activate ⚠️ 必看!必看! 🔥 获取最新激活码: 实时更…

    2024 年 12 月 30 日
    58500
  • 🚀 2025年最新IDEA激活码分享 | 永久破解IDEA 2024.3.5终极教程(支持JetBrains全家桶)

    🔥 还在为IDEA激活烦恼? 本文手把手教你如何将IDEA破解到2099年!支持最新2024.3.5版本,亲测有效!文末附2025年最新激活码~ 💻 效果预览 先上破解成功截图!看看这令人舒适的2099年到期时间 👇 ✨ 适用所有JetBrains产品:PyCharm、DataGrip、Goland等全家桶都能用这个方法激活! 📥 准备工作 1. 下载IDE…

    2025 年 6 月 6 日
    25300
  • 高效算法中的优先队列甄选

    文章标题: 优先队列在算法问题中的巧妙应用 目录 一、1046.最后的石头重量计算 二、703. 数据流里的第 K 大元素 三、692. 前 K 个高频词语 四、295. 数据流的中位数求解 一、1046.最后的石头重量计算 题目链接:1046.最后的石头重量题目描述:![ ](https://i-blog.csdnimg.cn/direct/16f1995…

    14小时前
    1600
  • Redis事务与锁机制在并发秒杀场景的深入剖析

    十. Redis 事务与 “锁机制”——并发秒杀处理的详细阐述 目录 十. Redis 事务与 “锁机制”——并发秒杀处理的详细阐述 1. Redis 事务的定义 2. Redis 事务的三大特性 3. Redis 事务相关指令 Multi、Exec、discard 及 “watch & unwatch” 3.1 快速入门(演示 Redis 事务控制…

    2025 年 6 月 18 日
    4900

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

联系我们

400-800-8888

在线咨询: QQ交谈

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息

关注微信