数据结构(三)堆和哈希表

目录

  • 哈希表和堆
    • 什么是哈希表 ?
    • 什么是堆 ?
    • 什么是图 ?
    • 案例一:使用python实现最小堆
    • 案例二 : 如何用Python通过哈希表的方式完成商品库存管理
    • 闯关题 (包含案例三:python实现哈希表)

本文是在原本数据结构与算法闯关的基础上总结得来,加入了自己的理解和部分习题讲解

原活动链接

邀请码: JL57F5

哈希表和堆

什么是哈希表 ?

哈希表存储的是由键(key)和值(value)组成的数据。例如,我们将每个人的性别作为数据进行存储,键为人名,值为对应的性别, 一般来说,我们可以把键当成数据的标识符,把值当成数据的内容。

Image Name

为了对比一下哈希表的优势 , 我们先把这些数据存储到数组中看看效果

Image Name

此处准备了6个箱子(即长度为6的数组)来存储数据。假设我们需要查询Ally的性别,由于不知道Ally的数据存储在哪个箱子里,所以只能从头开始查询。这个操作便叫作“线性查找”。 当我们查找到索引为4的时候, 才找到数据的键为Ally然后可以根据键把对应的值取出来

​ 但是我们发现 , 数据量越多,线性查找耗费的时间就越长。由此可知:由于数据的查询较为耗时,所以此处并不适合使用数组来存储数据。但使用哈希表便可以解决这个问题。首先准备好数组,这次我们用5个箱子的数组来存储数据。

首先尝试把Joe存进去。注意 这个时候就不能把它放在所以为0的数组上了 要不然没啥意义 , 那怎么放, 通过什么方式呢 ? 这个我们涉及到用哈希函数(Hash)去进行操作。 使用哈希函数(Hash)计算Joe的键,也就是字符串“Joe”的哈希值 。 得到的结果为4928 ( 哈希函数可以把给定的数据转换成固定长度的无规律数值。 我们可以想象使数据更加的安全)

​ 将得到的哈希值除以数组的长度5,求得其余数。这样的求余运算叫作“mod运算”。此处mod运算的结果为3。

Image Name

同理 : Sue键的哈希值为7291, mod 5的结果为1,将Sue的数据存进1号箱中。

Image Name

但是我们会发现, 如果余数都一样 , 冲突了怎么办 ? 比如 : Nell键的哈希值为6276, mod 5的结果为1。本应将其存进数组的1号箱中,但此时1号箱中已经存储了Sue的数据。这种存储位置重复了的情况便叫作“冲突”。

Image Name

遇到这种情况,可使用链表在已有数据的后面继续存储新的数据, 这样我们如果查找Ally的性别该如何操作呢 ?

为了找到它的存储位置,先要算出Ally键的哈希值,再对其进行mod运算。最终得到的结果为3。于是我们找到了键为Ally的数据。取出其对应的值,便知道了Ally的性别为女(F)。

Image Name

注意 : 在存储数据的过程中,如果发生冲突,可以利用链表在已有数据的后面插入新数据来解决冲突。这种方法被称为“链地址法”。比如这里的 1位置 和 3位置 都存在"冲突"

什么是堆 ?

​ 堆是一种图的树形结构, 可以自由添加数据,但取出数据时要从最小值开始按顺序取出。在堆的树形结构中,各个顶点被称为“结点”(node),数据就存储在这些结点中。

什么是图 ?

​ 那什么又是图呢 ? 说到“图”,我想可能大部分人想到的是散点图、柱状图,而计算机科学领域中说的“图”却是下面这样的。
Image Name

上图中的圆圈叫作“顶点”(也可以叫“结点”),连接顶点的线叫作“边”。也就是说,由顶点和连接每对顶点的边所构成的图形就是图。

​ ok , 回到我们讲的堆

Image Name

上图 , 这就是堆的例子 。结点内的数字就是它存储的数据。特别注意 : 堆中的每个结点最多有两个子结点。树的形状取决于数据的个数。另外,结点的排列顺序为从上到下,同一行里则为从左到右

堆中存储数据时必须遵守这样的规则:

子结点必定大于父结点。因此,最小值被存储在顶端的根结点中。往堆中添加数据时,为了遵守这条规则,一般会把新数据放在最下面一行靠左的位置。当最下面一行里没有多余空间,就再往下另起一行,把数据加在这一行的最左端。所以说大家记住了吗 ?

​ ok, 我们来举个例子吧

Image Name

我们试试往堆里添加数字5。如果放在6的右下角显然不符合堆的原则, 因为5小于6 , 按照规定必须是子节点大于父节点 , 那么此时 5 和 6调换一下位置就刚刚好 , 如果遇到同样的问题, 重复这样的操作直到数据都符合规则,不再需要交换为止。现在,父结点的1小于子结点的5,父结点的数字更小,所以不再交换。 因为 如果从堆中取出数据时,取出的是最上面的数据。这样,堆中就能始终保持最上面的数据最小, 需要注意的是 : 一旦最上面的数据被取出,因此堆的结构也需要根据原则进行重新调整。在此我们不过多赘述
Image Name

堆中最顶端的数据始终最小,所以无论数据量有多少,取出最小值的时间复杂度都为O(1)

案例一:使用python实现最小堆

import heapqdef find_top_k_largest(nums,k):min_heap = []for num in nums:if len(min_heap)<k:heapq.heappush(min_heap,num)else:if num > min_heap[0]:heapq.heappop(min_heap)heapq.heappush(min_heap,num)return min_heap# return sorted(min_heap,reverse = True)# 示例用法
nums = [4,2,9,7,5,1,6,8,3]
k = 3
top_k_largest = find_top_k_largest(nums,k)
print(top_k_largest)
[7, 9, 8]

逐行解析代码:

import heapqdef find_top_k_largest(nums, k):min_heap = []
  • import heapq: 这行代码导入了 Python 的 heapq 模块,它提供了堆队列算法的实现,特别是最小堆。
  • def find_top_k_largest(nums, k): 定义了一个函数 find_top_k_largest,它接受两个参数:一个数组 nums 和一个整数 k
  • min_heap = []: 初始化一个空列表 min_heap,这个列表将被用作最小堆。
    for num in nums:
  • for num in nums: 遍历数组 nums 中的每个元素,每个元素被引用为 num
        if len(min_heap) < k:heapq.heappush(min_heap, num)
  • if len(min_heap) < k: 检查当前最小堆的大小是否小于 k
  • heapq.heappush(min_heap, num): 如果是,则将当前元素 num 添加到最小堆中。
        else:if num > min_heap[0]:heapq.heappop(min_heap)heapq.heappush(min_heap, num)
  • else: 如果最小堆的大小已经达到 k
  • if num > min_heap[0]: 检查当前元素 num 是否大于最小堆的顶部元素(即最小元素)。
  • heapq.heappop(min_heap): 如果是,首先从最小堆中移除顶部元素(最小元素)。
  • heapq.heappush(min_heap, num): 然后将当前元素 num 加入到最小堆中。
    return min_heap
  • return min_heap: 函数返回最终构建的最小堆,这个堆包含了数组 nums 中的前 k 个最大元素。

在您的示例用法中,这个函数被用来找出数组 [4, 2, 9, 7, 5, 1, 6, 8, 3] 中的前 3 个最大元素,最终结果为 [7, 8, 9]。这个方法是通过维护一个大小为 k 的最小堆实现的,它确保了堆中始终保持数组中的前 k 个最大元素。

  • 提问:输出的顺序是[7,9,8] 非 [7,8,9]

您提到的输出 [7, 9, 8] 实际上也是正确的。这个结果出现的原因在于堆不保证元素的有序性,尤其是在非根部的位置。在您的例子中,最小堆确实维护了数组中的前 k 个最大元素,但是这些元素在堆中的顺序并不是有序的。

在最小堆中,只有根部(即堆顶元素,min_heap[0])是保证最小的,其他位置的元素并没有特定的顺序。当您提取出堆中的元素时,它们的顺序依赖于堆在内部的具体排列,这个排列是由 heapq 模块在执行插入和删除操作时决定的。

如果您需要一个有序的结果,您可以在返回前对堆中的元素进行排序。例如:

return sorted(min_heap, reverse=True)

这将确保返回的列表是按照从大到小的顺序排列的。但请注意,这个排序步骤会增加额外的时间复杂度。如果您不关心结果的顺序,那么直接返回未排序的堆就足够了。

案例二 : 如何用Python通过哈希表的方式完成商品库存管理

背景:
在一个电商系统中,我们需要管理商品的库存信息。每个商品都有一个唯一的商品编号(item_id)和对应的库存数量(stock)。当用户下单购买商品时,需要实时检查商品的库存情况,以确保有足够的库存供应。

任务:
请实现一个基于哈希表(字典)的商品库存管理系统。具体要求如下:

定义一个函数 add_stock(item_id, quantity),用于向库存系统中添加商品库存。如果商品已存在于系统中,则将库存数量累加;如果商品还不存在于系统中,则添加新的商品及其库存信息。
定义一个函数 subtract_stock(item_id, quantity),用于从库存系统中减少商品库存。如果商品不存在于系统中,则抛出异常;如果商品库存不足以满足要求的减少量,则抛出异常;否则,更新商品的库存数量。
定义一个函数 get_stock(item_id),用于获取指定商品的库存数量。


# 商品库存管理系统
stock_dict = {}  # 创建一个字典作为商品库存表def add_stock(item_id, quantity):"""向库存系统中添加商品库存如果商品已存在于系统中,则将库存数量累加;如果商品还不存在于系统中,则添加新的商品及其库存信息。"""if item_id in stock_dict:stock_dict[item_id] += quantityelse:stock_dict[item_id] = quantitydef subtract_stock(item_id, quantity):"""从库存系统中减少商品库存如果商品不存在于系统中,则抛出异常;如果商品库存不足以满足要求的减少量,则抛出异常;否则,更新商品的库存数量。"""if item_id not in stock_dict:raise Exception("Item does not exist in stock")if stock_dict[item_id] < quantity:raise Exception("Insufficient stock")stock_dict[item_id] -= quantitydef get_stock(item_id):"""获取指定商品的库存数量"""return stock_dict.get(item_id, 0)# 示例演示
add_stock("item001", 100)  # 添加商品 "item001",库存数量为 100
add_stock("item002", 50)   # 添加商品 "item002",库存数量为 50print("Current stock:")
print(stock_dict)  # 打印当前商品库存情况subtract_stock("item001", 20)  # 减少商品 "item001" 库存 20
stock = get_stock("item001")    # 获取商品 "item001" 的库存
print("Current stock:", stock)subtract_stock("item002", 70)  # 尝试减少商品 "item002" 库存 70(超过实际库存量)
# 库存不足异常将被抛出,程序终止运行
Current stock:
{'item001': 100, 'item002': 50}
Current stock: 80---------------------------------------------------------------------------Exception                                 Traceback (most recent call last)<ipython-input-1-3a5c254f3c86> in <module>45 print("Current stock:", stock)46 
---> 47 subtract_stock("item002", 70)  # 尝试减少商品 "item002" 库存 70(超过实际库存量)48 # 库存不足异常将被抛出,程序终止运行<ipython-input-1-3a5c254f3c86> in subtract_stock(item_id, quantity)24 25     if stock_dict[item_id] < quantity:
---> 26        raise Exception("Insufficient stock")27 28     stock_dict[item_id] -= quantityException: Insufficient stock

在以上代码示例中,我们创建了一个名为 stock_dict 的字典,用于存储商品库存信息。通过 add_stock 函数向库存系统中添加商品库存,通过 subtract_stock 函数减少商品库存,通过 get_stock 函数获取指定商品的库存数量。在函数实现上,我们利用字典的键值对特性,将商品编号作为键,库存数量作为对应的值进行存储和访问。

在主程序中,我们先添加了两个商品的库存信息,然后演示了减少库存和获取库存的操作。在减少库存时,如果库存不足或商品不存在,将会抛出相应的异常信息。

闯关题 (包含案例三:python实现哈希表)

STEP1:根据要求完成题目

Q1.(单选) 一个大小为n的数组中,可以快速找到前k大的数,应该使用哪种数据结构?

A. 数组
B. 链表
C. 栈
D. 堆
E. 哈希表

Q2.(单选)以下哪一组操作不是哈希表的基本操作?

A. 插入
B. 删除
C. 清空
D. 查找
E. 排序

Q3.(判断对错)堆中的每个结点最多有两个子结点, 这两个节点要求是所有结点中最大的 (T/F)
Q4.(判断对错)结点的排列顺序为从上到下,同一行里则为从左到右 (T/F)

使用 Python 实现一个哈希表,要求具有以下方法:

  • set(key, value):将键值对(key, value)插入哈希表中,如果 key 已经存在,则覆盖其原有的值
  • get(key):返回哈希表中指定 key 的值,如果 key 不存在,则返回 None
  • delete(key):从哈希表中删除指定 key 的键值对

提示:

  • 可以使用 Python 内置的字典 dict 来实现哈希表
  • 在 set 和 delete 方法中,要注意先检查字典中是否存在该 key
class HashTable:# 定义哈希表类,使用 Python 内置的 dict 实现def __init__(self):self.table = {}def set(self, key, value):"""向哈希表中插入键值对"""#题目q5 :  向哈希表中插入键值对self.table[key] = valuedef get(self, key):"""获取指定 key 对应的 value"""if key in self.table:# 题目q6 :返回指定的键对应的值return self.table[key]else:return Nonedef delete(self, key):"""从哈希表中删除指定的键值对"""if key in self.table:del self.table[key]

观察上面的代码,完成下面的单选题(注意查看前后代码)

Q5. 代码第11行为空,现在需要实现向哈希表中插入键值对,下面哪个选项为正确代码,选择正确选项并把结果赋值给a5

A : self.table[key] = value

B : table[key] = value

C : self.table = {}

D : self.table[key] = {key : value}

Q6. 代码第19行为空,现在需要实现返回指定的键对应的值,下面哪个选项为正确代码,选择正确选项并把结果赋值给a6

A : return table[key]

B : return self.table[key]

C : return value

D : return {value}

#填入你的答案
a1 = 'D'  # 如 a1 = 'A'
a2 = 'E'  # 如 a2 = 'A'
a3 = 'F'  # 如 a3 = 'T'
a4 = 'T'  # 如 a4 = 'T'
a5 = 'A'  # 如 a5 = 'C'
a6 = 'B'  # 如 a6 = 'A'  

STEP2:将结果保存为 csv 文件
csv 需要有两列,列名:id、answer。其中,id 列为题号,如 q1、q2;answer 列为 STEP1 中各题你计算出来的结果。💡 这一步的代码你无需修改,直接运行即可。

# 生成 csv 作业答案文件
def save_csv(a1, a2, a3, a4, a5,a6) : import pandas as pddf = pd.DataFrame({"id": ["q1", "q2", "q3", "q4","q5","q6"], "answer": [a1, a2, a3,a4,a5,a6]})df.to_csv("answer_ago_1_3.csv", index=None)save_csv(a1, a2, a3, a4, a5,a6)  # 运行这个cell,生成答案文件;该文件在左侧文件树project工作区下,你可以自行右击下载或者读取查看

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

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

相关文章

鸿鹄电子招投标系统源码实现与立项流程:基于Spring Boot、Mybatis、Redis和Layui的企业电子招采平台

随着企业的快速发展&#xff0c;招采管理逐渐成为企业运营中的重要环节。为了满足公司对内部招采管理提升的要求&#xff0c;建立一个公平、公开、公正的采购环境至关重要。在这个背景下&#xff0c;我们开发了一款电子招标采购软件&#xff0c;以最大限度地控制采购成本&#…

canvas创建图像数据,并在画布上展示

查看专栏目录 canvas示例教程100专栏&#xff0c;提供canvas的基础知识&#xff0c;高级动画&#xff0c;相关应用扩展等信息。canvas作为html的一部分&#xff0c;是图像图标地图可视化的一个重要的基础&#xff0c;学好了canvas&#xff0c;在其他的一些应用上将会起到非常重…

简单整理FFmpeg相关命令集

FFmpeg相关命令集 简单整理了FFmpeg相关命令&#xff0c;主要包括ffplay播放控制和媒体播放命令、ffmpeg命令相关参数以及常用的提取音视频等命令。 &#x1f3a1;导航小助手&#x1f3a1; FFmpeg相关命令集1.ffmpeg命令分类查询2.ffplay命令2.1 ffplay播放控制2.2 ffplay命令…

【J-Flash基本使用总结】

【J-Flash基本使用总结】 VX&#xff1a;hao541022348 ■ 烧录文件■ 创建新的工程■ 烧录模式-SWD模式■ J-Flash下载程序到单片机 ■ J-Flash拼接多个hex或bin文件■ J-Flash读单片机的option byte■ J-Flash读单片机Flash数据■ 将读出来的文件用jflash烧录到其他的芯片■ 设…

【C++ 程序设计入门基础】- 第4节-函数

1、函数 函数是对实现某一功能的代码的模块化封装。 函数的定义&#xff1a; 标准函数&#xff1a; 输入 n 对整数的 a、b &#xff0c;输出它们的和。 #include <iostream> #include <windows.h> using namespace std;int add(int a,int b);//函数原型声明int…

Python数据分析案例34——IMDB电影评论情感分析(Transformer)

电影评论的情感分析 案例背景 很多同学对电影系列的数据都比较喜欢&#xff0c;那我就补充一下这个最经典的文本分类数据集&#xff0c;电影情感评论分析。用神经网络做。对国外的英文评论文本进行分类&#xff0c;看是正面还是负面情感。 数据集介绍 数据集&#xff1a;IMDb…

java每日一题——ATM系统编写(答案及编程思路)

前言&#xff1a; 基础语句学完&#xff0c;也可以编写一些像样的程序了&#xff0c;现在要做的是多加练习&#xff0c;巩固下知识点&#xff0c;打好基础&#xff0c;daydayup! 题目&#xff1a;模仿银行ATM系统&#xff0c;可以创建用户&#xff0c;存钱&#xff0c;转账&…

VMware workstation安装debian-12.1.0虚拟机(最小化安装)并配置网络

VMware workstation安装debian-12.1.0虚拟机&#xff08;最小化安装&#xff09;并配置网络 Debian 是一个完全自由的操作系统&#xff01;Debian 有一个由普罗大众组成的社区&#xff01;该文档适用于在VMware workstation平台安装最小化安装debian-12.1.0虚拟机。 1.安装准…

索引和视图

索引和视图 一、实验目的 学会使用SQL语句CREATE INDEX创建索引。学会使用SQL语句DROP INDEX删除索引。学会使用SQL语句CREATE VIEW创建视图的用法。掌握使用SQL语句ALTER VIEW修改视图的方法。了解删除视图的SQL语句DROP VIEW的用法。 二、实验内容SQL语句CREATE INDEX创建索…

谷粒商城-缓存使用分布式锁SpringCache(5天)

缓存使用 1.1.1 哪些数据适合放入缓存 即时性、 数据一致性要求不高的 访问量大且更新频率不高的数据&#xff08;读多&#xff0c; 写少&#xff09; 例如&#xff1a;电商类应用&#xff0c; 商品分类&#xff0c; 商品列表等适合缓存 本地缓存 使用Map进行本地缓存 本地缓存…

基于JavaWeb+BS架构+SpringBoot+Vue智慧党建系统设计与实现

基于JavaWebBS架构SpringBootVue智慧党建系统设计与实现 文末获取源码Lun文目录前言主要技术系统设计功能截图订阅经典源码专栏Java项目精品实战案例《500套》 源码获取 文末获取源码 Lun文目录 1 概 述 1 1.1 课题研究背景 1 1.2 课题研究意义 1 1.3 课题研究内容 2 2 系统开…

MySQL 基于 GTID 主从复制

GTID 定义 GTID 是 MySQL 事务标识&#xff0c;为每一个提交的事务都生成一个标识&#xff0c;并且是全局唯一的&#xff0c;这个特性是从 MySQL5.6 引进的。 组成 GTID 是由 UUID TID&#xff0c;UUID 是MySQL的唯一标识&#xff0c;每个MySQL实例之间都是不同的。TID是代表…

速度之巅-位图算法

1:简单通俗来讲就是速度非常之快 以字节为单位,用一位一位寻找 #include <iostream> using namespace std; //加载数据 //就是将能被3整除的位设置为:1 void init(char* data, int len) {unsigned int n len * 8;for (unsigned i 0; i < n; i){if (i%30){//判断能被…

DNS从入门到精通

DNS从入门到精通 Dns从入门到精通 DNS从入门到精通一、DNS原理二、企业高速缓存dns的搭建三、DNS相关名词解释四、权威DNS搭建编辑子配置文件&#xff08;主要写我们维护的域zone)开始解析 五、权威dns中的数据记录种类及应用编辑子配置文件&#xff08;主要写我们维护的域zone…

图像提取大师:轻松从指定时长中获取某帧的图片,视频剪辑方法

在数字媒体时代&#xff0c;视频和图像已成为生活中不可或缺的部分。要从视频中提取某一帧作为图片&#xff0c;或者在视频剪辑时要采用其他的方法来达到需求的效果。下面来看云炫AI智剪如何轻松地从指定时长的视频中获取某帧的图片&#xff0c;视频剪辑的新方法。 视频中按指定…

JMeter定时器之同步定时器

JMeter定时器之同步定时器 1. 背景2. 目的3. 介绍4. 例子4.1单个请求4.2多个请求 1. 背景 在实际生活中大家肯定遇到过一种场景&#xff0c;就是在某一时间或某一时刻&#xff0c;某件商品进行抢购&#xff0c;相当于秒杀&#xff1b;但是用JMeter进行测试的时候&#xff0c;如…

tcpdump常用命令

tcp首部解析&#xff1a; tcp-首部_tcp首部-CSDN博客 ref&#xff1a; Home | TCPDUMP & LIBPCAP https://www.cnblogs.com/onlyforcloud/p/4396126.html tcpdump 详细使用指南&#xff08;请尽情食用&#xff09;_tcpdump指定ip和端口-CSDN博客 【博客192】抓取报文查…

【Python机器学习】SVM——线性模型与非线性特征

SVM&#xff08;核支持向量机&#xff09;是一种监督学习模型&#xff0c;是可以推广到更复杂模型的扩展&#xff0c;这些模型无法被输入空间的超平面定义。 线模型在低维空间中可能非常受限&#xff0c;因为线和平面的灵活性有限&#xff0c;但是有一种方式可以让线性模型更加…

软件测试|Python数据可视化神器——pyecharts教程(十四)

使用pyecharts绘制极坐标系图 简介 极坐标系图是一种用于可视化数据的坐标系&#xff0c;与常见的直角坐标系图&#xff08;笛卡尔坐标系&#xff09;不同&#xff0c;它使用角度和半径来表示数据点的位置。极坐标系图非常适合展示数据的循环性和周期性关系&#xff0c;以及数…

VSCode 正则表达式 匹配多行

VS Code 正则表达式匹配多行 (.|\n)*? //test.js const test {str: VS Code 正则表达式匹配多行VS Code 正则表达式匹配多行VS Code 正则表达式匹配多行VS Code 正则表达式匹配多行VS Code 正则表达式匹配多行VS Code 正则表达式匹配多行VS Code 正则表达式匹配多行VS Code …