二叉堆简单实现

  • 二叉堆的定义

二叉堆是一棵完全二叉树。二叉堆满足堆特性:父节点的键值总是保持固定的序关系于任何一个子节点的键值,且每个节点的左子树和右子树都是一个二叉堆。
当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。

这里我们实现 最小二叉堆堆

  • 二叉堆的基本操作

下图是一个最小二叉堆,使用数组形式表示:数组索引从1开始。

  1. 插入新元素

比如插入7,首先将7加在数组的末尾,然后与其父节点比较,如果小于父节点则与之交换,直到大于父节点或到达树的根部。

  1. 删除最小元素

首先移除根部的元素。然后将最后一个元素移到根部,再向下过滤,遇到比它小的元素则交换,直到到达叶子节点或者没有比它更小的元素。

  • 二叉堆实现
binary_heap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

"""
BinaryHeap类:
方法:
delete_min:删除最小元素,时间复杂度为O(logN)
insert: 插入元素,时间复杂度为O(logN)
find_min: 返回最小元素,时间复杂度为O(1)
is_empty: 判断是否为空
"""

class BinaryHeap:
def __init__(self, *args):
i = len(args) // 2
self.size = len(args)
# index从1开始
self.items = [None] + list(args)
while i > 0:
self.percolate_down(i)
i -= 1

def percolate_down(self, i):
while i * 2 <= self.size:
min_child_index = self.min_child(i)
if self.items[i] > self.items[min_child_index]:
self.items[i], self.items[min_child_index] = self.items[min_child_index], self.items[i]
i = min_child_index

def min_child(self, i):
if 2 * i + 1 > self.size:
return 2 * i
else:
if self.items[2*i] < self.items[2*i+1]:
return 2 * i
else:
return 2 * i + 1

def percolate_up(self, i):
while i // 2 > 0:
if self.items[i] < self.items[i // 2]:
self.items[i], self.items[i // 2] = self.items[i // 2], self.items[i]
i //= 2

def delete_min(self):
min_value = self.items[1]
self.items[1] = self.items[self.size]
self.size -= 1
self.items.pop()
self.percolate_down(1)
return min_value

def insert(self, data):
self.size += 1
self.items.append(data)
self.percolate_up(self.size)

def find_min(self):
return self.items[1]

def is_empty(self):
return self.size == 0

# test
if __name__ == '__main__':
binary_heap = BinaryHeap(9, 6, 5, 2, 3)

# find_min
# will print The minimum data of this Binary Heap is 2
print("The minimum data of this Binary Heap is {0}".format(binary_heap.find_min()))

# delete min
binary_heap.delete_min()
# will print The minimum data of this Binary Heap is 3
print("The minimum data of this Binary Heap is {0}".format(binary_heap.find_min()))

# insert 1
# will print The minimum data of this Binary Heap is 1
binary_heap.insert(1)
print("The minimum data of this Binary Heap is {0}".format(binary_heap.find_min()))

print(binary_heap.is_empty()) # False
for i in range(5):
binary_heap.delete_min()

print(binary_heap.is_empty()) # True
print(binary_heap.items) # [None]