深入解析数据结构与算法之堆

2023-11-22 09:15

本文主要是介绍深入解析数据结构与算法之堆,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

    • 🥦引言:
    • 🥦什么是堆
    • 🥦大顶堆与小顶堆
      • 🧄大顶堆(Max Heap)
      • 🧄小顶堆(Min Heap)
    • 🥦堆的表示
      • 🧄数组表示:
      • 🧄树表示:
    • 🥦堆的操作
      • 🧄堆化操作
      • 🧄插入操作
      • 🧄删除根节点操作
      • 🧄堆的创建
    • 🥦堆的应用
      • 🧄优先队列
      • 🧄堆排序
      • 🧄辅助数据结构
    • 🥦堆的复杂度分析
    • 🥦结论
    • 🥦参考文献

🥦引言:

在计算机科学中,数据结构和算法是构建复杂软件系统的基石。堆作为一种经典的数据结构,具有广泛的应用和重要的算法基础。本文将深入解析堆的原理、性质和常见的操作,帮助读者更好地理解和应用堆。

🥦什么是堆

堆是一种特殊的数据结构,属于树的一种表现形式。堆具有以下两个主要特征:

  • 堆是一个完全二叉树(或近似完全二叉树):堆中的所有层次都被填满,最后一层从左到右填入节点。

  • 堆具有堆序性:对于最小堆来说,父节点的值始终小于或等于其子节点的值;对于最大堆来说,父节点的值始终大于或等于其子节点的值。

  • 在堆中,每个节点的值都取决于其子节点的值:对于最小堆来说,父节点的值不大于任何子节点的值;对于最大堆来说,父节点的值不小于任何子节点的值。

🥦大顶堆与小顶堆

对于堆来说,可以根据节点的性质分为两种类型:大顶堆(Max Heap)和小顶堆(Min Heap)。

🧄大顶堆(Max Heap)

在大顶堆中,父节点的值大于或等于其子节点的值。也就是说,大顶堆的根节点是堆中的最大值。对于任意节点i,其子节点的值必须小于或等于节点i的值。大顶堆常用于获取最大值或进行部分排序。
结构表示如下:
在这里插入图片描述

🧄小顶堆(Min Heap)

在小顶堆中,父节点的值小于或等于其子节点的值。也就是说,小顶堆的根节点是堆中的最小值。对于任意节点i,其子节点的值必须大于或等于节点i的值。小顶堆常用于获取最小值或进行部分排序。
结构表示如下:
在这里插入图片描述

无论是大顶堆还是小顶堆,堆的逻辑结构和操作都是相同的。唯一的区别是节点的值大小和根节点的值。

在实际应用中,大顶堆和小顶堆都有各自的用途。例如,在优先队列中,可以使用大顶堆来实现,以便快速获取优先级最高的元素。而在进行部分排序时,可以使用小顶堆来实现,以方便获取最小的k个元素。

无论是大顶堆还是小顶堆,它们都是一种非常重要的数据结构,在算法和数据处理中有广泛的应用。了解堆的性质和操作,可以帮助我们更好地理解和应用这两种堆。

🥦堆的表示

堆可以使用数组或树来表示。下面分别介绍这两种表示方法:

🧄数组表示:

  • 在数组表示中,堆的元素按照完全二叉树的形式存储在一个数组中。

  • 堆的根节点存储在数组的索引位置0处。

  • 对于索引为i的节点,其左子节点的索引为2i + 1,右子节点的索引为2i + 2。

  • 通过数组的索引关系,可以方便地在堆的插入、删除等操作中定位到对应的节点。

例如,对于一个大顶堆(Max Heap)的数组表示:heap = [9, 6, 7, 3, 5, 1, 4],可以构建如下的堆结构:
在这里插入图片描述
数组表示:

在这里插入图片描述

🧄树表示:

  • 在树表示中,堆可以使用二叉树进行表示。

  • 堆的根节点是二叉树的根节点。

  • 每个节点最多有两个子节点,并且子节点与父节点之间有特定的大小关系(对于大顶堆是大于等于,对于小顶堆是小于等于)。

  • 通过指针或引用,可以方便地在堆的插入、删除等操作中定位到对应的节点。

  • 例如,对于一个大顶堆(Max Heap)的树表示:
    在这里插入图片描述

🥦堆的操作

🧄堆化操作

首先引入堆化的概念, 当我们向一个已经是堆的数据结构(如数组或二叉堆)中插入一个新元素时,需要进行插入操作,并保持堆的性质。这个过程可以称为"堆插入"。堆插入的一般步骤如下:

将新元素插入到堆的最后一个位置(或数组的末尾)。
向上调整(也称为上浮)新插入的元素,直到它在堆中找到合适的位置并满足堆的性质。
具体来说,对于大顶堆(Max Heap)的情况,堆插入的过程如下:

将新元素插入到堆的最后一个位置。
与其父节点进行比较,如果新元素的值大于父节点的值,则交换它们的位置。
重复上述步骤,直到新元素找到了合适的位置并满足堆的性质。

类似地,对于小顶堆(Min Heap)的情况,堆插入的过程如下:

将新元素插入到堆的最后一个位置。
与其父节点进行比较,如果新元素的值小于父节点的值,则交换它们的位置。
重复上述步骤,直到新元素找到了合适的位置并满足堆的性质。

通过堆插入操作,可以在保持堆的性质下有效地将新元素插入到堆中,并且时间复杂度为O(log n),其中n表示堆的大小。插入完成后,堆将继续保持堆的性质。

🧄插入操作

向堆中插入一个新节点。通常,插入操作首先将新节点添加到堆的末尾,然后通过向上调整(上滤)操作来恢复堆的堆序性。
示例:

  1. 初始状态
    在这里插入图片描述

  2. 插入元素12
    插入12后,需要将其与父节点5进行比较,因为12大于5,所以交换它们的位置。
    在这里插入图片描述

  3. 插入12后,需要将其与父节点5进行比较,因为12大于5,所以交换它们的位置。然后,还需要将12与其父节点8进行比较,因为12大于8,所以交换它们的位置。最后,还需要将12与其父节点10进行比较,因为12大于10,所以交换它们的位置。
    在这里插入图片描述


代码示例

def heapify_up(heap, index):parent_index = (index - 1) // 2while parent_index >= 0 and heap[index] > heap[parent_index]:heap[index], heap[parent_index] = heap[parent_index], heap[index]index = parent_indexparent_index = (index - 1) // 2def insert_into_heap(heap, new_item):heap.append(new_item)heapify_up(heap, len(heap) - 1)# 示例使用:
heap = [10,8,7,5,6,3,4]
print("原始堆:", heap)insert_into_heap(heap, 9)
print("插入后的堆:", heap)

🧄删除根节点操作

将堆中的根节点删除。通常,删除根节点后,将堆中最后一个节点移到根位置,然后通过向下调整(下滤)操作来恢复堆的堆序性。
下面是一个示例的大顶堆删除操作的结构图:

  1. 初始状态:

在这里插入图片描述

  1. 删除堆顶元素12:

在这里插入图片描述

删除堆顶元素时,需要将最后一个元素5替换到堆顶,然后通过向下调整操作,将其移动到合适的位置,并保持大顶堆的性质。

  1. 向下调整操作:

在这里插入图片描述

在向下调整的过程中,将当前节点与其子节点进行比较,如果子节点的值较大,则将当前节点与较大的子节点交换位置。继续以上比较和交换的步骤,直到当前节点不再有子节点或者当前节点的值大于等于其子节点的值,保持大顶堆的性质。

  1. 最终结果:

在这里插入图片描述

在删除堆顶元素的过程中,需要进行多次比较和交换,并通过向下调整操作将新的堆顶元素移动到正确的位置,同时保持大顶堆的性质。以上是一个简单的示例,实际操作中可能还需要考虑边界情况和特殊情况的处理。

下面是一个示例的 Python 代码,展示了如何执行堆的删除操作:

import heapq# 创建一个堆
heap = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]# 将列表转换为堆
heapq.heapify(heap)# 删除堆顶元素
root = heapq.heappop(heap)print("删除的堆顶元素:", root)
print("删除后的堆:", heap)

输出如下:

删除的堆顶元素: 1
删除后的堆: [2, 3, 4, 3, 5, 9, 5, 6, 5]

在上述代码中,使用了 heapq 模块提供的函数来执行堆操作。heapify 函数将普通列表转换为堆,heappop 函数用于删除堆顶元素,并返回被删除的元素。最后,打印删除的堆顶元素和删除后的堆。

🧄堆的创建

现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提:左右子树必须是一个堆,才能调整。
  
int array[] = {27,15,19,18,28,34};
在这里插入图片描述


在这里插入图片描述

🥦堆的应用

🧄优先队列

使用堆来实现优先队列,可以快速找到最大或最小的元素,并在一系列数据中动态调整优先级。

🧄堆排序

堆排序是一种高效的排序算法,利用堆的性质进行排序操作。

🧄辅助数据结构

堆在其他算法和数据结构中的实现中起到辅助作用,如图的最短路径算法中使用的Dijkstra算法。

🥦堆的复杂度分析

堆的插入和删除操作的时间复杂度均为O(log n),其中n为堆中元素的数量。堆化操作的时间复杂度为O(n)。

🥦结论

堆作为一种重要的数据结构,在计算机科学中广泛应用。通过深入理解堆的原理、性质和操作,我们能够更好地应用堆解决实际问题。堆不仅作为优先队列和排序算法的基础,还在各种算法和系统中发挥着重要的作用。熟练掌握堆的概念和操作,将极大地提高算法设计和实现的能力。

🥦参考文献

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.

🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄🍄


🏫博客主页:魔王-T

🏯系列专栏:结构算法

🥝大鹏一日同风起 扶摇直上九万里

❤️感谢大家点赞👍收藏⭐评论✍️


END

这篇关于深入解析数据结构与算法之堆的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

Spring MVC使用视图解析的问题解读

《SpringMVC使用视图解析的问题解读》:本文主要介绍SpringMVC使用视图解析的问题解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC使用视图解析1. 会使用视图解析的情况2. 不会使用视图解析的情况总结Spring MVC使用视图

一文带你深入了解Python中的GeneratorExit异常处理

《一文带你深入了解Python中的GeneratorExit异常处理》GeneratorExit是Python内置的异常,当生成器或协程被强制关闭时,Python解释器会向其发送这个异常,下面我们来看... 目录GeneratorExit:协程世界的死亡通知书什么是GeneratorExit实际中的问题案例