当前位置: article > 正文

【Python】一文带你学会数据结构中的堆、栈_python 堆栈

作者：盐析白兔 | 2024-05-01 03:31:40

踩

python 堆栈

作者主页：爱笑的男孩。的博客_CSDN博客-深度学习,活动,python领域博主爱笑的男孩。擅长深度学习,活动,python,等方面的知识,爱笑的男孩。关注算法,python,计算机视觉,图像处理,深度学习,pytorch,神经网络,opencv领域.https://blog.csdn.net/Code_and516?type=blog个人简介：打工人。

持续分享：机器学习、深度学习、python相关内容、日常BUG解决方法及Windows&Linux实践小技巧。

如发现文章有误，麻烦请指出，我会及时去纠正。有其他需要可以私信我或者发我邮箱:zhilong666@foxmail.com

堆是一种特殊的数据结构，具有优秀的性能和灵活的应用场景。在Python中，堆可以通过内置的heapq模块来实现。栈是一种非常重要的数据结构，常被用于解决各种计算机科学问题。

本文将详细讲解Python数据结构中的堆、栈

2.2.1 早期栈（Early Stack）

2.2.2 数组栈（Array-Based Stack）

2.2.3 链表栈（Linked List-Based Stack）

2.2.4 动态数组栈（Dynamic Array-Based Stack）

一、堆

1.1 堆的简介

1.1.1 堆的定义

堆是一种特殊的树状数据结构，它满足以下两个主要性质：

堆是完全二叉树：堆中的所有层级除了最后一层都是完全填满的，最后一层的节点都靠左排列。
堆的任意节点的值都不大于（或不小于）其子节点的值：这一性质称为堆属性。

根据堆属性的不同，可以将堆分为最大堆和最小堆。

1.1.2 堆的表示方法

在Python中，可以使用列表来表示堆。具体而言，堆的第一个元素（索引为0）为根节点，其他元素按照从上到下、从左到右的顺序排列。

1.1.3 堆的操作

堆主要支持以下几种操作：

插入：将一个新元素插入堆中，并保持堆的结构和堆属性。
删除最小（或最大）值：移除堆中的根节点，并保持堆的结构和堆属性。
构建堆：构建一个新的堆，将一个无序列表转换为堆的形式。

1.2 堆的发展史

堆作为一种经典的数据结构，诞生于20世纪60年代，由艾德加·斯特恩（Edgar F. Codd）在数据库领域首次提出。后来，堆被应用于算法和数据结构的研究中，并衍生出了多种不同的使用形式。

1.2.1 二叉堆

二叉堆是堆的最基础形式，是堆的最常用实现方式。它满足堆的定义，同时使用完全二叉树的结构。在二叉堆中，每个节点的值都不小于（或不大于）其子节点的值。

1.2.2 Fibonacci堆

Fibonacci堆是为了解决二叉堆在某些操作上效率低下的问题而提出的。Fibonacci堆将支持由二项堆、配对堆（Pairing Heap）和斐波那契堆（Fibonacci Heap）构成的一组堆结构。与二叉堆相比，Fibonacci堆具有更好的平摊时间复杂度，但也带来了更大的常数时间。

1.2.3 优先队列

优先队列是一种特殊的数据结构，堆是实现优先队列的常用方式之一。优先队列中的每个元素都有一个优先级，优先级高的元素排在前面。堆可以很好地支持优先队列的插入和删除操作，保持队列中的元素按照优先级有序。

1.3 堆的使用方法

首先，我们需要导入Python的heapq模块，它是Python标准库中用于实现堆的模块。使用如下语句导入：

import heapq

接下来，我将逐一介绍堆的基本操作。

1.3.1 创建堆

在Python中，我们可以使用heapq模块来创建堆。可以通过heapq.heapify()函数将一个列表转换为堆。下面是一个示例：


import heapq
 
data = [5, 2, 8, 0, 3, 9, 1]
heapq.heapify(data)
print(data)  # 输出: [0, 2, 1, 5, 3, 9, 8]

可以看到，通过heapify()函数，列表data被转换为了一个堆。

1.3.2 插入元素

要在堆中插入一个元素，可以使用heapq.heappush()函数。下面是一个示例：


import heapq
 
data = [5, 2, 8, 0, 3, 9, 1]
heapq.heapify(data)
heapq.heappush(data, 6)
print(data)  # 输出: [0, 2, 1, 5, 3, 9, 8, 6]

可以看到，通过heappush()函数，元素6被插入堆中，并且堆的特性得到保持。

1.3.3 弹出元素

要从堆中弹出最小（或最大）的元素，可以使用heapq.heappop()函数。下面是一个示例：


import heapq
 
data = [0, 2, 1, 5, 3, 9, 8]
heapq.heapify(data)
smallest = heapq.heappop(data)
print(smallest)  # 输出: 0
print(data)  # 输出: [1, 2, 8, 5, 3, 9]

可以看到，通过heappop()函数，堆中的最小值0被弹出，并且堆的特性得到保持。

1.3.4 替换元素

替换堆中的元素与弹出元素操作类似，可以使用heapq.heapreplace()函数。下面是一个示例：


import heapq
 
data = [0, 2, 1, 5, 3, 9, 8]
heapq.heapify(data)
smallest = heapq.heapreplace(data, 7)
print(smallest)  # 输出: 0
print(data)  # 输出: [1, 2, 7, 5, 3, 9, 8]

可以看到，通过heapreplace()函数，堆中的最小值0被弹出，并且被元素7替换。替换操作无需先弹出最小值再插入新元素，因此具有更高的效率。

1.3.5 合并堆

可以使用heapq.merge()函数合并多个堆，返回一个新的堆。下面是一个示例：


import heapq
 
heap1 = [1, 3, 5]
heap2 = [2, 4, 6]
merged = heapq.merge(heap1, heap2)
print(list(merged))  # 输出: [1, 2, 3, 4, 5, 6]

可以看到，通过merge()函数，堆heap1和heap2被合并成了一个新的堆。

1.3.6 堆排序

堆排序是利用堆的特性来对列表进行排序的一种方法。可以使用heapq模块中的heappushpop()函数和heapq.nsmallest()函数实现堆排序。下面是一个示例：


import heapq
 
data = [5, 2, 8, 0, 3, 9, 1]
sorted_data = [heapq.heappop(data) for _ in range(len(data))]
print(sorted_data)  # 输出: [0, 1, 2, 3, 5, 8, 9]

可以看到，通过多次弹出堆中的最小元素，实现了对列表的排序。

1.4 堆的总结

堆在Python中是一个十分强大的数据结构，具有以下几个优点：

高效的插入和删除操作：堆的插入和删除最小值（或最大值）的操作时间复杂度为O(log n)，即使在大规模数据处理中也能保持较高的性能。
快速获取最值：堆的根节点即为最小（或最大）值，可以在O(1)的时间内获取。
灵活的应用场景：堆广泛应用于优先队列、排序算法（如堆排序）以及图算法中（如Dijkstra最短路径算法）等。

然而，堆也存在一些局限性：

不适合查找和修改操作：由于堆并非按照顺序排列，无法快速地找到指定元素进行修改。
无法保序：堆并不要求所有元素有序，它只保证了最值的有序性。
空间占用较大：堆的实现需要额外的存储空间，其中一些节点可能永远无法被访问到。

总的来说，堆是一种强大而灵活的数据结构，特别适用于对最值操作频繁的场景。在Python中，内置的heapq模块提供了堆的实现方式，开发者可以利用该模块快速地应用堆数据结构，提高程序的效率和性能。

二、栈

2.1 栈的简介

2.1.1 栈的定义

栈是一种线性数据结构，其特点是后进先出（Last-In-First-Out，LIFO）。栈有两个主要操作，即压栈（Push）和弹栈（Pop）。压栈将数据放入栈顶，而弹栈则从栈顶移除数据。除此之外，栈还具备返回栈顶元素（Top）的功能。

2.1.2 栈的特性

栈除了遵循后进先出的原则外，还有以下特性：

栈的容量是固定的。当栈达到其最大容量时，再次压栈操作将导致栈溢出。
栈可以为空，也可以达到最大容量。
栈中的元素不可随机访问。只能通过弹栈获取栈顶元素。

2.1.3 栈的应用场景

栈的特性使得它在许多领域有着广泛的应用。常见的应用场景包括：

逆序输出：栈可以用于将输入的字符串逆序输出。
表达式计算：栈可以用于处理数学表达式，并解决优先级问题。
函数调用：栈用于存储函数调用过程中的局部变量和返回地址。
浏览器后退：浏览器的“后退”功能通过一个栈来实现。

2.2 栈的发展史

2.2.1 早期栈（Early Stack）

早期的计算机的存储器是有限的，因此数据结构的设计也受到限制。早期计算机栈的实现方式是使用堆栈指针（Stack Pointer）作为一个寄存器。计算机通过将指令和数据保存在内存上的栈中，实现函数调用和返回地址的管理。

2.2.2 数组栈（Array-Based Stack）

随着计算机存储器的改进，栈可以使用数组来实现，通过定义一个固定大小的数组来储存栈中的元素。数组栈具有较高的访问速度，但其容量是固定的。

2.2.3 链表栈（Linked List-Based Stack）

为了克服数组栈容量固定的问题，链表栈（Linked List-Based Stack）提供了一种动态的栈实现方式。链表栈使用链表结构来储存栈中的元素，使得栈的容量可以根据需求动态增加或减少。链表栈通常需要更多的内存空间用于储存指针。

2.2.4 动态数组栈（Dynamic Array-Based Stack）

动态数组栈是数组栈和链表栈的结合体。它使用数组来储存栈中的元素，但具有动态增长和缩小容量的功能。当栈的大小超过数组容量时，动态数组栈会自动重新分配更大的内存空间。相比链表栈，动态数组栈的访问速度更快，但在扩容时需要额外的内存分配和数据复制操作。

2.3 栈的使用方法

栈是一种常见的数据结构，它的特点是“后进先出”（Last-In-First-Out，LIFO）。在Python中，我们可以使用列表（List）来实现栈。

2.3.1 初始化栈

初始化一个空栈，可以使用空列表表示。示例代码如下：

stack = []

2.3.2 压栈（入栈）

将元素添加到栈的顶部，称为压栈或入栈。可以使用列表的 append() 方法将元素添加到栈的末尾。示例代码如下：


stack.append(1)
stack.append(2)
stack.append(3)

栈的元素现在变为 [1, 2, 3]。

2.3.3 弹栈（出栈）

从栈的顶部移除元素，称为弹栈或出栈。可以使用列表的 pop() 方法将栈顶的元素移除并返回。示例代码如下：


element = stack.pop()
print(element)  # 输出：3

栈的元素现在变为 [1, 2]。

2.3.4 获取栈顶元素

获取栈顶的元素，但并不移除它。可以直接使用列表的索引 -1 来获取栈顶元素。示例代码如下：


top_element = stack[-1]
print(top_element)  # 输出：2

2.3.5 判断栈是否为空

通过检查栈的长度是否为零，可以确定栈是否为空。可以使用列表的 len() 方法获取栈的长度。示例代码如下：


python
is_empty = len(stack) == 0
print(is_empty)  # 输出：False

2.3.6 显示栈的元素

可以使用循环遍历列表来显示栈的元素。示例代码如下：


for element in stack:
    print(element)
# 输出：
# 1
# 2

2.3.7 综合示例代码如下：


stack = []
stack.append(1)
stack.append(2)
stack.append(3)
 
element = stack.pop()
print(element)  # 输出：3
 
top_element = stack[-1]
print(top_element)  # 输出：2
 
is_empty = len(stack) == 0
print(is_empty)  # 输出：False
 
for element in stack:
    print(element)
# 输出：
# 1
# 2

栈在实际应用中有广泛的用途，比如递归函数的调用、表达式求值、深度优先搜索等。掌握栈的使用方法对于Python编程非常重要。

2.4 栈的总结

2.4.1 栈的特点：

栈是一种受限的线性数据结构，存储元素的顺序按“后进先出”原则。由于栈操作的特殊性，栈具有一些独特的性质：常数时间复杂度的插入和删除，但只能访问栈顶元素。

2.4.2 基本操作：

入栈（push）：将元素添加到栈顶。
出栈（pop）：删除栈顶元素，并返回其值。
栈顶元素获取（top）：返回栈顶元素的值。
栈是否为空（isEmpty）：判断栈是否为空。
栈的大小（size）：返回栈中元素的个数。

2.4.3 栈的应用：

函数调用：函数的调用顺序使用栈来记录，每当一个函数被调用，其调用信息被压入栈中，当函数执行完毕后再将其弹出。
括号匹配：栈可以用来检查表达式中的括号是否匹配，遇到左括号入栈，遇到右括号与栈顶元素进行匹配。
浏览器的前进后退：浏览器的前进后退功能可以通过两个栈来实现，一个栈用于存储用户的浏览记录，另一个栈用于存储用户的后退记录。

2.4.4 栈的实现：

在Python中，可以使用列表（list）来实现栈的功能。通过列表的append()方法实现入栈操作，使用pop()方法实现出栈操作。此外，还可以使用collections模块中的deque来实现栈，deque是一个双端队列，可以实现高效的入栈和出栈操作。

综上所述，栈作为一种受限的线性数据结构，在计算机科学中有着广泛的应用。它的发展始于硬件系统，随着软件系统的发展得到了进一步的拓展。栈不仅仅是数据结构中的一个概念，更是我们在编程中常用的一种工具和思维方式。掌握栈的基本概念和操作，对于理解算法和编程语言的工作方式具有重要意义。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/516774