6.10. 二叉堆操作

6.10. Binary Heap Operations

中文英文

我们将为我们的二叉堆实现以下基本操作：

• BinaryHeap()：创建一个新的空二叉堆。
• insert(k)：将一个新项目添加到堆中。
• get_min()：返回具有最小键值的项目，但不将该项目从堆中移除。
• delete()：返回具有最小键值的项目，并将该项目从堆中移除。
• is_empty()：如果堆为空，则返回True；否则返回False。
• size()：返回堆中的项目数量。
• heapify(list)：从一个键值列表构建一个新的堆。

ActiveCode 1 演示了使用一些二叉堆方法的示例。请注意，无论我们以何种顺序将项目添加到堆中，每次都会移除最小的项目。

Activity: 6.10.1 Using the Binary Heap

from pythonds3.trees import BinaryHeap

my_heap = BinaryHeap()
my_heap.insert(5)
my_heap.insert(7)
my_heap.insert(3)
my_heap.insert(11)

print(my_heap.delete())
print(my_heap.delete())
print(my_heap.delete())
print(my_heap.delete())

The basic operations we will implement for our binary heap are as follows:

• BinaryHeap() creates a new empty binary heap.
• insert(k) adds a new item to the heap.
• get_min() returns the item with the minimum key value, leaving the item in the heap.
• delete() returns the item with the minimum key value, removing the item from the heap.
• is_empty() returns True if the heap is empty, False otherwise.
• size() returns the number of items in the heap.
• heapify(list) builds a new heap from a list of keys.

ActiveCode 1 demonstrates the use of some of the binary heap methods. Notice that no matter what order we add items to the heap, the smallest is removed each time.

Activity: 6.10.1 Using the Binary Heap

from pythonds3.trees import BinaryHeap

my_heap = BinaryHeap()
my_heap.insert(5)
my_heap.insert(7)
my_heap.insert(3)
my_heap.insert(11)

print(my_heap.delete())
print(my_heap.delete())
print(my_heap.delete())
print(my_heap.delete())

---

最后更新: 2024年9月13日
创建日期: 2024年9月9日