Python Data Structure 简明教程

Python - Heaps

堆是一种特殊的树结构，其中每个父节点都小于或等于其子节点。然后将其称为最小堆。如果每个父节点都大于或等于其子节点，则将其称为最大堆。在实现优先级队列时它非常有用，其中赋予具有较高权重的队列项在处理中更高的优先级。

Heap is a special tree structure in which each parent node is less than or equal to its child node. Then it is called a Min Heap. If each parent node is greater than or equal to its child node then it is called a max heap. It is very useful is implementing priority queues where the queue item with higher weightage is given more priority in processing.

关于堆的详细讨论可在我们的网站上获得这里。如果你不熟悉堆数据结构，请先学习它。在本章中，我们将看到使用 Python 实现堆数据结构。

A detailed discussion on heaps is available in our website here. Please study it first if you are new to heap data structure. In this chapter we will see the implementation of heap data structure using python.

Create a Heap

通过使用名为 heapq 的 Python 内置库来创建堆。此库具有执行堆数据结构上各种操作的相关函数。以下是这些函数的列表。

A heap is created by using python’s inbuilt library named heapq. This library has the relevant functions to carry out various operations on heap data structure. Below is a list of these functions.

  1. heapify − This function converts a regular list to a heap. In the resulting heap the smallest element gets pushed to the index position 0. But rest of the data elements are not necessarily sorted.

  2. heappush − This function adds an element to the heap without altering the current heap.

  3. heappop − This function returns the smallest data element from the heap.

  4. heapreplace − This function replaces the smallest data element with a new value supplied in the function.

Creating a Heap

只需使用带堆化函数的元素列表就可以创建堆。以下示例中，我们提供一个元素列表，堆化函数重新排列元素，将最小元素放置在第一位。

A heap is created by simply using a list of elements with the heapify function. In the below example we supply a list of elements and the heapify function rearranges the elements bringing the smallest element to the first position.

Example

import heapq

H = [21,1,45,78,3,5]
# Use heapify to rearrange the elements
heapq.heapify(H)
print(H)

Output

执行上述代码后，将生成以下结果 −

When the above code is executed, it produces the following result −

[1, 3, 5, 78, 21, 45]

Inserting into heap

向堆中插入数据元素时总是将元素添加到最后一个索引位置。但只在该元素的数值最小的情况下，才能再次应用堆化函数以将新添加的元素移动到第一索引位置。以下示例中，我们插入数字 8。

Inserting a data element to a heap always adds the element at the last index. But you can apply heapify function again to bring the newly added element to the first index only if it smallest in value. In the below example we insert the number 8.

Example

import heapq

H = [21,1,45,78,3,5]
# Covert to a heap
heapq.heapify(H)
print(H)

# Add element
heapq.heappush(H,8)
print(H)

Output

执行上述代码后，将生成以下结果 −

When the above code is executed, it produces the following result −

[1, 3, 5, 78, 21, 45]
[1, 3, 5, 78, 21, 45, 8]

Removing from heap

可以使用此函数移除第一个索引位置处的元素。以下示例中，该函数总是将索引位置为 1 处的元素移除。

You can remove the element at first index by using this function. In the below example the function will always remove the element at the index position 1.

Example

import heapq

H = [21,1,45,78,3,5]
# Create the heap

heapq.heapify(H)
print(H)

# Remove element from the heap
heapq.heappop(H)

print(H)

Output

执行上述代码后，将生成以下结果 −

When the above code is executed, it produces the following result −

[1, 3, 5, 78, 21, 45]
[3, 21, 5, 78, 45]

Replacing in a Heap

堆替换函数始终移除堆中最小的元素，并将新进入的元素插入某个未按任何顺序固定的位置。

The heap replace function always removes the smallest element of the heap and inserts the new incoming element at some place not fixed by any order.

Example

import heapq

H = [21,1,45,78,3,5]
# Create the heap

heapq.heapify(H)
print(H)

# Replace an element
heapq.heapreplace(H,6)
print(H)

Output

执行上述代码后，将生成以下结果 −

When the above code is executed, it produces the following result −

[1, 3, 5, 78, 21, 45]
[3, 6, 5, 78, 21, 45]