【数据结构篇】堆

文章目录

    • 前言
    • 基本介绍
      • 认识堆
      • 堆的特点
      • 堆的分类
      • 堆的操作
      • 堆的常见应用
    • 堆的实现
      • JDK 自带的堆
      • 手动实现堆

前言

本文主要是对堆的一个简单介绍,如果你是刚学数据结构的话,十分推荐看这篇文章,通过本文你将对堆这个数据结构有一个大致的了解,同时学习JDK自带的堆实现类PriorityQueue类,如何基于数组手写一个堆。

基本介绍

认识堆

  • 什么是堆

    堆(Heap)是一种常见的数据结构,堆可以基于数组实现,也可以基于链表实现。堆的定义如下:n个元素的序列 { k 1 , k 2 , k i , … , k n } {\{k1,k2,ki,…,kn\}} {k1,k2,ki,,kn} 当且仅当满足下关系 ( k i < = k 2 i , k i < = k 2 i + 1 ) (ki <= k2i,ki <= k2i+1) (ki<=k2i,ki<=k2i+1)或者 ( k i > = k 2 i , k i > = k 2 i + 1 ) , ( i = 1 , 2 , 3 , 4... n / 2 ) (ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2) (ki>=k2i,ki>=k2i+1),(i=1,2,3,4...n/2)时,称之为堆。堆是具备完全二叉树的特点的,二叉堆就是一种特别的完全二叉树,多叉堆也具有完全二叉树的特点。

    备注:完全二叉树的特点是,除了最后一层,其他层的叶子节点都是满的,也就是非最后一层节点的要么是2要么是0,这个度是就是子节点的个数,堆也是具有这个特点的

以下是一些常见的堆:

  • 最大堆:父节点永远是最大的,顶点为堆中最大元素

          9/ \7   8/ \ / \6  5 2  3/ \
    1   4
    
  • 最小堆:父节点永远是最小的,顶点为堆中最小元素

    		  0/   \1     2/  \   /  \6   5  7   3/ \ 9   8/
    4
    
  • 多叉堆:

              0/ / \ \/  /   \  \2   3    4  5/ | \ 6  7  8

堆的特点

  • 堆的特点
    • 类完全二叉树:堆具有完全二叉树的特点,除了最后一层外,其他层的节点都是满的,并且最后一层的节点从左到右连续排列。
    • 堆序性质:堆中的每个节点都满足堆序性质。对于最小堆来说,任意节点的值都小于等于其子节点的值;而对于最大堆来说,任意节点的值都大于等于其子节点的值。
    • 根节点存储极值:在最小堆中,根节点存储着堆中的最小值;而在最大堆中,根节点存储着堆中的最大值。因此,可以通过堆的根节点快速获取极值。
    • 快速插入和删除:堆支持高效的插入和删除操作。在最小堆中,插入新元素和删除最小元素的时间复杂度均为 O(log n),其中 n 是堆中元素的数量。最大堆的插入和删除最大元素操作也具有相同的时间复杂度。

堆的分类

  • 堆的分类
    • 按照结构可以分为
      • 二叉堆:每个节点最多有两个子节点的堆。二叉堆分为最大堆和最小堆。
      • 多叉堆:每个节点可以拥有多个子节点的堆,其中特别常见的是二叉堆的扩展,也就是三叉堆、四叉堆等。
    • 按照顺序可以分为
      • 最大堆:在最大堆中,父节点的值大于或等于其子节点的值。堆顶元素是最大值。
      • 最小堆:在最小堆中,父节点的值小于或等于其子节点的值。堆顶元素是最小值。

所以也可以组合命名,比如:多叉最小堆、多叉最大堆、二叉最小堆、二叉最大堆,其中最为常见的就是二叉最大堆(一般直接简称最大堆)和二叉最小堆(一般直接简称最小堆),而本文中的堆实现就是主要讲解 最大堆 和 最小堆

堆的操作

  1. 插入元素:将一个新元素插入到堆中。插入操作通常是在堆的末尾添加新元素,然后通过上浮操作(Heapify Up)或下浮操作(Heapify Down)调整堆的结构,以满足堆的性质。
  2. 删除元素:从堆中删除指定元素。通常情况下,需要删除的元素是位于堆的根节点。删除操作会将根节点与最后一个叶子节点交换,然后通过下沉操作(Heapify Down)调整堆的结构,以满足堆的性质。
  3. 获取极值:获取堆中的最大值或最小值(取决于是最大堆还是最小堆)。在最大堆中,最大值存储在根节点;在最小堆中,最小值存储在根节点。获取极值操作可以在 O(1) 的时间复杂度内完成。
  4. 堆化:通过上浮操作或下沉操作,调整堆的结构,使之满足堆的性质。上浮操作用于维护插入元素后的堆性质,而下沉操作用于维护删除元素后的堆性质。
  5. 构建堆:将一个无序数组转换为堆的过程。构建堆的常见方法是从数组最后一个非叶子节点开始,依次进行下沉操作,以保证每个节点都满足堆的性质。
  • 堆的上浮和下浮操作

    • 上浮(Heapify Up):也称为向上调整或上升,是指在插入元素到堆时将其移动到正确的位置以满足堆的性质。对于最大堆来说,上浮操作是将新插入的元素不断与其父节点进行比较和交换,直到满足堆的性质。具体步骤如下:

      • Step1:将新插入的元素放在堆数组的末尾。
      • Step2:将该元素与父节点进行比较,如果它比父节点大(对于最大堆),则交换两者位置。
      • Step3:重复上述比较和交换的过程,直到新插入的元素达到合适的位置或成为根节点。

      上浮操作保证了插入后的堆仍然保持堆的性质,即对于最大堆,父节点的值大于等于子节点的值。

      image-20230930170714265

    • 下沉(Heapify Down):也称为向下调整或下降,是指在删除堆顶元素后,将最后一个元素移到堆顶并将其下沉到正确的位置以满足堆的性质。对于最大堆来说,下沉操作是将堆顶元素不断与其子节点进行比较和交换,直到满足堆的性质。具体步骤如下:

      • Step1:将堆数组的最后一个元素移到堆顶位置。
      • Step2:将堆顶元素与它的子节点进行比较,选择较大的子节点。
      • Step3:如果堆顶元素小于较大的子节点(对于最大堆),则交换两者位置。
      • Step4:重复上述比较和交换的过程,直到堆顶元素达到合适的位置或成为叶子节点。

      下沉操作保证了删除堆顶元素后的堆仍然保持堆的性质,即对于最大堆,父节点的值大于等于子节点的值。

      image-20230930194114849

堆的常见应用

基于堆的特点,堆的常见应用有:

  1. 优先队列(Priority Queue):堆常被用于实现优先队列,其中元素按照优先级进行排序。通过堆的性质,可以快速插入新元素和获取当前最高优先级的元素。
  2. 堆排序(Heap Sort):堆排序是一种基于堆的排序算法,它利用堆的属性进行排序。堆排序是一种原地、稳定的排序算法,具有较好的平均和最坏时间复杂度,适用于大规模数据集的排序。
  3. 图算法中的最短路径和最小生成树:堆被广泛用于图算法中的最短路径和最小生成树问题。例如,Dijkstra算法使用最小堆来选择下一个距离顶点最短的节点,Prim算法使用最小堆来选择下一个距离树最近的边。
  4. 模拟系统中的事件调度:在模拟系统中,堆可用于事件驱动的调度和处理。每个事件都具有优先级,堆的结构使得可以快速找到下一个最高优先级的事件进行处理。
  5. 中位数的查找:通过使用两个堆,分别维护数据流的较小部分和较大部分,可以高效地查找中位数。
  6. 数据压缩和哈夫曼编码:堆可用于构建哈夫曼树,用于数据压缩和编码。根据字符频率构建最小堆,然后按照频率合并节点,生成哈夫曼树,并将字符编码为可变长度的前缀码。

堆的实现

JDK 自带的堆

在Java中,有一个名为PriorityQueue的类实现了堆(Heap)的功能。PriorityQueue是一个优先队列,基于堆的数据结构实现。

使用PriorityQueue可以方便地操作堆的插入、删除和获取极值等操作。它根据元素的优先级进行排序,并保证每次操作都能够高效地获取最高优先级的元素。

以下是一些PriorityQueue常用方法的示例:

  • add(E e)offer(E e):网堆中添加元素。将元素插入优先队列。
  • remove()poll():删除堆的根节点。删除并返回队列中的最高优先级元素。
  • peek():获取极值。返回队列中的最高优先级元素,但不删除。
  • size():获取堆中元素的数量。返回队列中的元素个数。

至于堆化和构建堆的操作 JDK 底层自动实现了,我们只管调用无需关心实现,这就是 Java 的好处吧

备注PriorityQueue默认是最小堆(小顶堆),即优先级较低的元素具有更高的优先级。如果需要使用最大堆(大顶堆),可以通过提供自定义的Comparator来实现。

示例

示例一:最小堆(默认)

堆顶元素永远是最小的

import java.util.PriorityQueue;public class HeapExample {public static void main(String[] args) {PriorityQueue<Integer> minHeap = new PriorityQueue<>();minHeap.add(5);minHeap.add(2);minHeap.add(8);System.out.println(minHeap.peek()); // 输出: 2System.out.println(minHeap.poll()); // 输出: 2System.out.println(minHeap.peek()); // 输出: 5System.out.println(minHeap.size()); // 输出: 2}
}

示例二:最大堆

堆顶元素永远是最大的

import java.util.Comparator;
import java.util.PriorityQueue;public class MaxHeapExample {public static void main(String[] args) {PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());maxHeap.add(5);maxHeap.add(2);maxHeap.add(8);System.out.println(maxHeap.peek()); // 输出: 8System.out.println(maxHeap.poll()); // 输出: 8System.out.println(maxHeap.peek()); // 输出: 5System.out.println(maxHeap.size()); // 输出: 2}
}

手动实现堆

注意:以下实现都是基于数组实现的,基于链表实现的我就没有写了,一般而言堆都是基于数组实现的,因为数组相对链表,内存是连续的,不需要存引用,相较而言,查询性能更好,内存占用也会相对少很多

手写堆提供的API

  • Heap():创建堆的无参构造方法,默认容量为10

  • Heap(int capacity):创建堆的有参构造方法,指定堆的初始容量

  • add(int val):往堆中添加一个元素,超过容量会自动进行扩容,扩容为原来容量的两倍

  • remove():移除并返回堆顶的元素(也就是极大值)

  • remove(int val):移除指定元素并返回,如果不存在抛异常

  • printHeap():打印堆中的元素,相当于是层序遍历二叉树

  • isEmpty():判断堆是否为空

/*** @author ghp* @title* @description*/
public class Heap {/*** 堆的默认容量*/private static final int DEFAULT_CAPACITY = 10;/*** 堆数组,用于存储堆中的元素*/private int[] heapArray;/*** 堆的容量*/private int capacity;/*** 堆中元素的数量*/private int size;public Heap() {this.capacity = DEFAULT_CAPACITY;this.heapArray = new int[capacity];this.size = 0;}public Heap(int capacity) {this.capacity = capacity;this.heapArray = new int[capacity];this.size = 0;}/*** 遍历打印堆中所有的元素*/public void printHeap() {for (int i = 0; i < size; i++) {System.out.print(heapArray[i] + " ");}System.out.println();}/*** 判断堆是否为空** @return*/public boolean isEmpty() {return size == 0;}/*** 往队中添加一个元素** @param value*/public void add(int value) {if (size == capacity) {// 扩容为当前容量的两倍resize(capacity * 2);}heapArray[size] = value;heapifyUp(size++);}/*** 移除堆顶元素** @return*/public int remove() {if (isEmpty()) {throw new IllegalStateException("Heap is empty");}int max = heapArray[0];heapArray[0] = heapArray[--size];heapifyDown(0);return max;}/*** 移除堆中指定元素** @param value*/public void remove(int value) {int index = findIndex(value);if (index == -1) {throw new IllegalArgumentException("Element does not exist in the heap");}// 使用最后一个节点覆盖要删除的元素,这样才能确保节点都能进行一个更新heapArray[index] = heapArray[--size];heapifyDown(index);}/*** 寻找到指定元素的索引** @param value* @return*/private int findIndex(int value) {for (int i = 0; i < size; i++) {if (heapArray[i] == value) {return i;}}return -1;}/*** 上浮(新增操作时节点上移)** @param index*/private void heapifyUp(int index) {// 定位父节点int parent = (index - 1) / 2;if (parent >= 0 && heapArray[parent] < heapArray[index]) {// 如果父节点比子节点小,则进行交换,然后递归上浮,确保父节点是永远大于子节点的swap(parent, index);heapifyUp(parent);}}/*** 下浮(删除操作时节点下移)** @param index*/private void heapifyDown(int index) {// 左节点的索引int left = 2 * index + 1;// 右节点的索引int right = 2 * index + 2;// 父节点索引int parent = index;// 判断左右节点是否大于父节点if (left < size && heapArray[left] > heapArray[parent]) {parent = left;}if (right < size && heapArray[right] > heapArray[parent]) {parent = right;}if (parent != index) {// 如果父节点发生了更新,则交换父节点和子节点的位置,同时递归下浮,确保父节点永远是最大的swap(parent, index);heapifyDown(parent);}}/*** 交换堆数组索引为 i 和 j 的两个元素** @param i* @param j*/private void swap(int i, int j) {int temp = heapArray[i];heapArray[i] = heapArray[j];heapArray[j] = temp;}/*** 扩容堆大小** @param newCapacity*/private void resize(int newCapacity) {if (newCapacity < DEFAULT_CAPACITY){newCapacity = DEFAULT_CAPACITY;}if (newCapacity < 0) {newCapacity = Integer.MAX_VALUE;}heapArray = Arrays.copyOf(heapArray, newCapacity);capacity = newCapacity;}
}

备注:如果想要使用最小堆,则只需要修改上浮和下浮的if判断条件即可

测试:

public class Test {public static void main(String[] args) {Heap heap = new Heap(0);heap.add(1);heap.add(2);heap.add(3);heap.add(4);heap.add(5);heap.printHeap();heap.remove(1);heap.printHeap();}
}

image-20230930194253344

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/145132.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Flink之Watermark生成策略

在Flink1.12以后,watermark默认是按固定频率周期性的产生. 在Flink1.12版本以前是有两种生成策略的: AssignerWithPeriodicWatermarks周期性生成watermarkAssignerWithPunctuatedWatermarks[已过时] 按照指定标记性事件生成watermark 新版本API内置的watermark策略 单调递增的…

(vue3)create-vue 组合式APIsetup、ref、watch,通信

优势&#xff1a; 更易维护&#xff1a;组合式api&#xff0c;更好的TS支持 之前是选项式api&#xff0c;现在是组合式&#xff0c;把同功能的api集合式管理 复用功能封装成一整个函数 更快的速度 更小的体积 更优的数据响应式&#xff1a;Proxy create-vue 新的脚手架工…

【小沐学前端】Node.js实现UDP通信

文章目录 1、简介2、下载和安装3、代码示例3.1 HTTP3.2 UDP单播3.4 UDP广播 结语 1、简介 Node.js 是一个开源的、跨平台的 JavaScript 运行时环境。 Node.js 是一个开源和跨平台的 JavaScript 运行时环境。 它是几乎任何类型项目的流行工具&#xff01; Node.js 在浏览器之外…

【PHP】如何关闭buffer实时输出内容到前端

前言 默认情况下&#xff0c;我们在PHP里使用echo等函数输出的内容&#xff0c;是不会马上发送给前端的&#xff0c;原因是有 buffer 的存在&#xff0c;buffer又分两处&#xff0c;一处是PHP本身的buffer&#xff0c;另一处是Nginx的buffer。只有当buffer满了之后&#xff0c…

【图论C++】链式前向星(图(树)的存储)

/*** file * author jUicE_g2R(qq:3406291309)————彬(bin-必应)* 一个某双流一大学通信与信息专业大二在读 * * brief 一直在竞赛算法学习的路上* * copyright 2023.9* COPYRIGHT 原创技术笔记&#xff1a;转载需获得博主本人…

django 实现:闭包表—树状结构

闭包表—树状结构数据的数据库表设计 闭包表模型 闭包表&#xff08;Closure Table&#xff09;是一种通过空间换时间的模型&#xff0c;它是用一个专门的关系表&#xff08;其实这也是我们推荐的归一化方式&#xff09;来记录树上节点之间的层级关系以及距离。 场景 我们 …

红米手机 导出 通讯录 到电脑保存

不要搞什么 云服务 不要安装什么 手机助手 不要安装 什么app 用 usb 线 连接 手机 和 电脑 手机上会跳出 提示 选择 仅传输文件 会出现下面的 一个 盘 进入 MIUI目录 然后进入 此电脑\Redmi Note 5\内部存储设备\MIUI\backup\AllBackup\20230927_043337 如何没有上面的文件&a…

MyBatis的一级缓存和二级缓存:原理和作用

MyBatis的一级缓存和二级缓存&#xff1a;原理和作用 引言 在数据库访问中&#xff0c;缓存是一种重要的性能优化手段&#xff0c;它可以减少数据库查询的次数&#xff0c;加快数据访问速度。MyBatis作为一款流行的Java持久层框架&#xff0c;提供了一级缓存和二级缓存来帮助…

C++(string类)

本节目标&#xff1a; 1、为什么要学习string类 2.标准库中的string类 3.vs和g下string结构说明 1.为什么学习string类 1.1 c语言中的字符串 C 语言中&#xff0c;字符串是以 \0 结尾的一些字符的集合&#xff0c;为了操作方便&#xff0c; C 标准库中提供了一些 str系列的…

1.6.C++项目:仿mudou库实现并发服务器之channel模块的设计

项目完整版在&#xff1a; 文章目录 一、channel模块&#xff1a;事件管理Channel类实现二、提供的功能三、实现思想&#xff08;一&#xff09;功能&#xff08;二&#xff09;意义&#xff08;三&#xff09;功能设计 四、代码&#xff08;一&#xff09;框架&#xff08;二…

3.物联网射频识别,(高频)RFID应用ISO14443-2协议

一。ISO14443-2协议简介 1.ISO14443协议组成及部分缩略语 &#xff08;1&#xff09;14443协议组成&#xff08;下面的协议简介会详细介绍&#xff09; 14443-1 物理特性 14443-2 射频功率和信号接口 14443-3 初始化和防冲突 &#xff08;分为Type A、Type B两种接口&…

深入理解操作系统- - 进程篇(1)

目录 进程解释&#xff1a; process in memory(进程在内存中包含什么) : 并发的进程&#xff1a; 进程定义&#xff1a; 个人定义&#xff1a; 书本定义&#xff1a; 进程状态&#xff1a; 进程何时离开CPU&#xff1a; 内部事件&#xff1a; 外部事件&#xff1a; 进…

卫星图像应用 - 洪水检测 使用DALI进行数据预处理

这篇文章是上一篇的延申。 运行环境&#xff1a;Google Colab 1. 当今的深度学习应用包含由许多串行运算组成的、复杂的多阶段数据处理流水线&#xff0c;仅依靠 CPU 处理这些流水线已成为限制性能和可扩展性的瓶颈。 2. DALI 是一个用于加载和预处理数据的库&#xff0c;可…

消息队列实现进程之间通信方式代码,现象

1、向消息队列中写入数据 #include<myhead.h>//消息结构体 typedef struct {long msgtype; //消息类型char data[1024]; //消息正文 }Msg_ds;#define SIZE sizeof(Msg_ds)-sizeof(long) //正文大小int main(int argc, const char *argv[]) {//1、创建…

raw智能照片处理工具DxO PureRAW mac介绍

DxO PureRAW Mac版是一款raw智能照片处理工具&#xff0c;该软件采用了智能技术&#xff0c;以解决影响所有RAW文件的七个问题&#xff1a;去马赛克&#xff0c;降噪&#xff0c;波纹&#xff0c;变形&#xff0c;色差&#xff0c;不想要的渐晕&#xff0c;以及缺乏清晰度。 Dx…

渗透测试之打点

请遵守中华人民共和国网络安全法 打点的目的是获取一个服务器的控制权限 1. 企业架构收集 &#xff08;1&#xff09;官网 &#xff08;2&#xff09;网站或下属的子网站&#xff0c;依次往下 天眼查 企查查 2. ICP 备案查询 ICP/IP地址/域名信息备案管理系统 使用网站…

基于微信小程序的宠物寄养平台小程序设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言系统主要功能&#xff1a;具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序&#xff08;小蔡coding&#xff09;有保障的售后福利 代码参考源码获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计…

浏览器输入 URL 并回车发生了什么

本文节选自我的博客&#xff1a;浏览器输入 URL 并回车发生了什么 &#x1f496; 作者简介&#xff1a;大家好&#xff0c;我是MilesChen&#xff0c;偏前端的全栈开发者。&#x1f4dd; CSDN主页&#xff1a;爱吃糖的猫&#x1f525;&#x1f4e3; 我的博客&#xff1a;爱吃糖…

国庆9.30

消息队列实现进程间通信 snd #include <myhead.h> //消息结构体 typedef struct {long msgtype; //消息类型char data[1024]; //消息正文 }Msg_ds;#define SIZE sizeof(Msg_ds)-sizeof(long) //正文大小int main(int argc, const char *argv[]) {//1、创建key…

常用数学分布

正态分布&#xff08;高斯分布&#xff09; 若随机变数 X X X 服从一个期望 μ \mu μ&#xff0c;标准差 的正态分布 σ \sigma σ&#xff0c;则记为 X ≈ N ( μ , σ 2 ) X \approx N(\mu,\sigma^2) X≈N(μ,σ2)&#xff0c;其密度函数为&#xff1a; f ( x ) 1 σ …