Python 中的二叉堆是什么？

17 Mar 2025 | 6 分钟阅读

二叉堆是 Python 中一种重要的非线性数据结构。堆是一个完全二叉树。堆是实现一种称为优先队列的数据结构的高效方法。W. J. Williams 于 1964 年引入了二叉堆，其主要目的是实现堆排序算法。堆不是有序的数据结构。

二叉堆可以分为两种类型

最小堆
最大堆

在最小堆中，根节点的值小于其子节点的值。因此，根节点的值将是整个树中最小的。
在最大堆中，根节点的值大于其子节点的值。因此，根节点的值将是整个树中最大的。
树中的所有子树都必须满足这些属性。

判断二叉树是否为堆

树必须是完全二叉树
- 直到倒数第二层的所有层都必须填满。
- 倒数第二层的所有子节点必须从左到右填满。
必须满足堆属性——最小堆或最大堆。

上述两棵二叉树都是堆。

在第一棵树中，第 0 层和第 1 层的每个节点都已填满。第 1 层是倒数第二层。因此，第一棵二叉树是一个堆。
在第二棵树中，倒数第二层，即第 1 层，只有一个节点被填满。第 1 层的所有叶节点都位于左侧。因此，它是一棵二叉树。

在这棵二叉树中，倒数第二层，即第 1 层，只填满了一个节点，但第 1 层到叶节点的节点不是从左到右填满的。因此，它不是堆。

在本教程中，我们将通过示例学习最小堆。

堆数据结构的重要应用

用于优先队列的图算法
序统计
堆排序

表示

二叉堆可以使用数组表示，就像二叉树一样

首先，堆中的根节点存储在数组的第 0 个索引处。长度为 n 的数组可以表示具有 n 个节点的堆。
如果 n 表示树的深度，则必须构建长度为 2n + 1 的数组。

要将所有其他节点放入数组，可以使用以下两个公式和一个验证公式

左子节点 = 2*父节点在数组中的索引 + 1
右子节点 = 2*父节点在数组中的索引 + 2

验证

父节点索引 = (子节点索引 - 1)/2

这里有一个例子

现在，让我们创建一个数组来表示堆

1. 堆有 7 个节点。因此，我们需要创建一个长度为 7 的数组：(0-6)

2. 堆中的根节点是 1。将 1 放在数组的索引 0 处

3. 现在，查看 2 的左子节点

左子节点 = 2*父节点在数组中的索引 + 1

= 2*0 + 1

= 1

4. 根节点的右子节点：3

右子节点 = 2*父节点在数组中的索引 + 2

= 2*0 + 2

= 2

5. 在下一层：节点(2)的子节点

4: 左子节点 = 2*父节点在数组中的索引 + 1

= 2*索引(2) + 1

= 2*1 + 1

= 3

5: 右子节点 = 2*父节点在数组中的索引 + 2

= 2*索引(2) + 2

= 2*1 + 2

= 4

6. 节点(3)的子节点

6: 左子节点 = 2*父节点在数组中的索引 + 1

= 2*索引(3) + 1

= 2*2 + 1

= 5

7: 右子节点 = 2*父节点在数组中的索引 + 2

= 2*索引(3) + 2

= 2*2 + 2

= 6

因此，上述堆表示为数组

堆上的操作

1. 堆化

给定一个二叉树，将其转换为堆称为“堆化”。我们使用树的数组实现，并将其转换为表示堆的数组

#Min Heap
def heapify(BT, nodes, node):
    smallest = node
    leftchild = 2 * node + 1
    rightchild = 2 * node + 2
    
    if leftchild < nodes and BT[node] > BT[leftchild]:
        smallest = leftchild
    if rightchild < nodes and BT[smallest] > BT[rightchild]:
        smallest = rightchild
    
    if smallest != node:
        BT[node], BT[smallest] = BT[smallest], BT[node]
        heapify(BT, nodes, smallest)
    
BinaryTree = [7, 2, 5, 6, 3, 4, 1]
for i in range((len(BinaryTree)//2)-1, -1, -1):
    heapify(BinaryTree, len(BinaryTree), i)
print(BinaryTree)

输出

 [1, 2, 4, 6, 3, 7, 5]

正如你所观察到的，最小节点 1 被放置在根节点（索引 0）位置，满足了最小堆的属性。

2. 插入节点

给定一个节点，我们需要将其附加到数组末尾，以便从左到右填充最后一个节点，最重要的一步是在插入后对数组进行堆化

def insertion(BT, newnode):
    n = len(BT)
    n += 1
    BT.append(newnode)
    for i in range((n//2)-1, -1, -1):
        heapify(BT, n, i)

BinaryTree = [2, 4, 6, 3, 7, 5]
for i in range((len(BinaryTree)//2)-1, -1, -1):
    heapify(BinaryTree, len(BinaryTree), i)
print(BinaryTree)
insertion(BinaryTree, 1)
print(BinaryTree)

输出

[2, 3, 4, 6, 7, 5]
[1, 3, 2, 6, 7, 5, 4]

我们将 1 插入堆中。在堆的所有元素中，1 是最小的；根据最小堆的属性，它必须放在根节点（索引 0）处。

3. 从堆中删除元素

如果要删除的节点是叶节点，则可以直接删除。如果它是内部节点，我们需要将该节点与任何叶节点交换，然后删除它。

永远不要忘记对数组进行堆化。

def deletion(BT, ele):
    n = len(BT)
    for i in range(0, n):
        if ele == BT[i]:
            break
    BT[i], BT[n-1] = BT[n-1], BT[i]
    BT.remove(ele)
    for i in range((len(BT)//2)-1, -1, -1):
        heapify(BT, len(BT), i)
    
BinaryTree = [7, 2, 5, 6, 3, 4]
for i in range((len(BinaryTree)//2)-1, -1, -1):
    heapify(BinaryTree, len(BinaryTree), i)
print(BinaryTree)
insertion(BinaryTree, 1)
print(BinaryTree)
deletion(BinaryTree, 1)
print(BinaryTree)

输出

[2, 3, 4, 6, 7, 5]
[1, 3, 2, 6, 7, 5, 4]
[2, 3, 4, 6, 7, 5]

4. 获取最小节点/最大节点

在最小堆中，根节点将具有最小值。因此，我们可以编写一个函数来查找最小节点并返回根节点（索引 0）。

同样，在最大堆中，根节点将具有最大值

def minnode(BT):
	return BT[0]
print(minnode([3, 7, 8, 9]))

输出

Heapq 模块

如前所述，我们可以使用堆来实现优先队列。在 Python 的库中，有一个模块——heapq 模块，用于实现优先队列算法。该模块包含用于不同堆操作的函数，例如

1. heappush(heap, node)

将节点插入堆

2. heappop(heap)

该函数删除并返回堆中的最小元素。

3. heapify(list)

以线性时间将给定列表转换为堆

现在我们将尝试使用 heapq 模块来实现堆操作——插入和删除

import heapq
class minheap:
    def __init__(self):
        self.heap = []
    def parentnode(self, node):
        return (node - 1)//2
    def insertion(self, newnode):
        heapq.heappush(self.heap, newnode)
    def display(self):
        print(self.heap)
    def deletion(self, ele):
        self.heapify(ele, float('-inf'))
        self.extractmin()
    def heapify(self, i, val):
        self.heap[i] = val
        while(i != 0 and self.heap[self.parentnode(i)] > self.heap[i]):
            self.heap[i], self.heap[self.parentnode(i)] = (self.heap[self.parentnode(i)], self.heap[i])
    def extractmin(self):
        return heapq.heappop(self.heap)
    def getminnode(self):
        return self.heap[0]

MyHeap = minheap()
MyHeap.insertion(3)
MyHeap.insertion(2)
MyHeap.insertion(4)
MyHeap.insertion(1)
MyHeap.insertion(6)
MyHeap.insertion(5)
print("Heap:")
MyHeap.display()
MyHeap.deletion(0)
print("After deleting element at 0th index:")
MyHeap.display()
print("Minimum node:",MyHeap.getminnode())

输出

Heap:
[1, 2, 4, 3, 6, 5]
After deleting element at 0th index:
[2, 3, 4, 5, 6]
Minimum node: 2

堆排序

堆排序是可用的排序算法之一。要对元素进行排序，我们将所有给定值推入堆，并且在所有元素插入后，我们将逐个弹出最小的元素

import heapq
def heapsort(mylist):
    list1 = []
    sortedlist = []
    for i in mylist:
        heapq.heappush(sortedlist, i)
    for i in range(len(sortedlist)):
        list1.append(heapq.heappop(sortedlist))
    print(list1)
    
list1 = [3, 1, 2]
heapsort(list1)

输出

[1, 2, 3]

下一个主题Python 中的命名空间和作用域是什么

Python 中的二叉堆是什么？

堆数据结构的重要应用

表示

堆上的操作

Heapq 模块

堆排序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Python 问题

Python 中的二叉堆是什么？

堆数据结构的重要应用

表示

堆上的操作

Heapq 模块

堆排序

相关帖子

Python 程序返回数组乘积的符号

SciPy CSGraph - 压缩稀疏图

如何使用 Python 创建倒计时器

Python for Finance

如何在 Python 中打印给定矩阵的螺旋矩阵

统计学中使用 Python 的对数正态分布

使用 PyQt5 在 Python 中制作简单的 FLAMES 游戏

Python 中的赋值运算符

Python 事件驱动编程

Python 中的循环技术

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器