Original link: http://www.nosuchfield.com/2022/06/29/Principle-and-implementation-of-maximum-heap/
Fundamental
The maximum heap is a binary tree, and the parent node of the binary tree is required to be larger than its child nodes. At the same time, the binary tree is a complete binary tree, which means that all nodes except the bottom layer of the binary tree should be filled, and the bottom layer should be from the left. to the right is filled. Obviously, the value of the top node of the max heap is the largest in the entire binary tree.
We use arrays to build a max heap, and use arrays to build a binary tree max heap has the following properties. Assuming that the subscript index of a node in the binary tree in the array is index , the subscript index of its parent node in the array is parent = (index - 1) // 2 , and the subscript index of its left child node is child_left = index * 2 + 1 , the subscript index of the right child node is child_right = index * 2 + 2 . If it is calculated that parent is less than 0 or child is greater than the maximum value of the array, it means that there is no parent node or child node.
Code
Next, we create the maximum heap class to store some basic information of the heap and tool methods
1
2
3
4
5
6
7
|
class Heap (object) :
def __init__ (self) -> None :
self._data = []
def _size (self) -> int:
return len(self._data)
def _swap (self, i: int, j: int) -> None :
self._data[i], self._data[j] = self._data[j], self._data[i]
|
The Heap class contains three methods, an initialization method creates an array, the _size method returns the length of the array, and the _swap method is used to swap the values of two elements in the array.
insert element
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
def push (self, item: int) -> None :
self._data.append(item)
# Move the last element, which is the element just added, up to a position where the tree size is kept in order
self._siftup(self._size() - 1 )
def _siftup (self, index: int) -> None :
while True :
parent = (index - 1 ) >> 1 # right shift by one, equivalent to dividing by two
# If it is moved to the head, or the parent element is already larger than the current element, it is already in order and does not need to be moved anymore
if index <= 0 or self._data[parent] >= self._data[index]:
break
# Not yet in order, you need to exchange the current value with the value of the parent node, and let the parent node continue to move in the next round
self._swap(index, parent)
index = parent
|
The process of inserting an element is very simple, that is, first append the element to the end of the array, and then continuously move the element up until the element is smaller than the parent element, or the element has reached the head of the binary tree. At this time, the binary tree is in order. push ends.
popup element
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
twenty one
twenty two
|
def pop (self) -> int:
max_item = self._data[ 0 ]
# Swap the head element with the last element
self._swap( 0 , self._size() - 1 )
# pop the last element
self._data.pop()
# Move the first element, which is the element displaced from the tail, to the appropriate position
self._shift_down( 0 )
return max_item
def _shift_down (self, index) -> None :
while True :
child = (index << 1 ) + 1
# If the right child node is larger, use the right child node to replace
if child + 1 < self._size() and self._data[child] < self._data[child + 1 ]:
child += 1
# If you move to the end, or the current node is already larger than the child node, you can stop moving
if child >= self._size() or self._data[index] >= self._data[child]:
break
# Not yet in order, you need to exchange the current value with the value of the child node, and let the child node continue to move in the next round
self._swap(index, child)
index = child
|
The pop-up process is not complicated, just pop the top element first. Then for simplicity, we swap the last element with the top element, and then remove the last element. Then we only need to keep moving the top element down until it is larger than its own child node, or moves to the end, at which point the binary tree is ordered and pop ends.
Summarize
We can use the following code to test the max heap
flat
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
twenty one
twenty two
twenty three
twenty four
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
import math
import random
class Heap (object) :
def __init__ (self) -> None :
self._data = []
def _size (self) -> int:
return len(self._data)
def pretty_print (self) -> None :
"""
print binary tree
:return:
"""
height = int(math.log2(len(self._data))) + 1
for i in range(height):
width = 2 ** (height - i) - 2
print( ' ' * width, end= '' )
blank = ' ' * (width * 2 + 2 )
print(
blank.join(
[ '{: >2d}' .format(num) for num in self._data[ 2 ** i - 1 :min( 2 ** (i + 1 ) - 1 , len(self._data))]]) )
print()
def _swap (self, i: int, j: int) -> None :
"""
swap the values of two elements
:param i:
:param j:
:return:
"""
self._data[i], self._data[j] = self._data[j], self._data[i]
def push (self, item: int) -> None :
"""
add an element to the tree
:param item:
:return:
"""
self._data.append(item)
# Move the last element, which is the element just added, up to a position where the tree size is kept in order
self._siftup(self._size() - 1 )
def _siftup (self, index: int) -> None :
while True :
parent = (index - 1 ) >> 1 # right shift by one, equivalent to dividing by two
# If it is moved to the head, or the parent element is already larger than the current element, it is already in order and does not need to be moved anymore
if index <= 0 or self._data[parent] >= self._data[index]:
break
# Not yet in order, you need to exchange the current value with the value of the parent node, and let the parent node continue to move in the next round
self._swap(index, parent)
index = parent
def pop (self) -> int:
"""
Pop the largest element at the top
:return:
"""
max_item = self._data[ 0 ]
# Swap the head element with the last element
self._swap( 0 , self._size() - 1 )
# pop the last element
self._data.pop()
# Move the first element, which is the element displaced from the tail, to the appropriate position
self._shift_down( 0 )
return max_item
def _shift_down (self, index) -> None :
while True :
child = (index << 1 ) + 1
# If the right child node is larger, use the right child node to replace
if child + 1 < self._size() and self._data[child] < self._data[child + 1 ]:
child += 1
# If you move to the end, or the current node is already larger than the child node, you can stop moving
if child >= self._size() or self._data[index] >= self._data[child]:
break
# Not yet in order, you need to exchange the current value with the value of the child node, and let the child node continue to move in the next round
self._swap(index, child)
index = child
if __name__ == '__main__' :
range_num, num = 1000 , 300
data = random.sample(range(range_num), num)
sorted_data = sorted(data, reverse= True )
heap = Heap()
for d in data:
heap.push(d)
heap.pretty_print()
for n in range(num):
v1 = sorted_data[n]
v2 = heap.pop()
assert v1 == v2, ''
print( '{} -> {}' .format(v1, v2))
for n in range( 10 ):
print( '-' * 100 )
heap.push(n)
heap.pretty_print()
|
refer to
https://www.cnblogs.com/q1214367903/p/14220949.html
This article is reprinted from: http://www.nosuchfield.com/2022/06/29/Principle-and-implementation-of-maximum-heap/
This site is for inclusion only, and the copyright belongs to the original author.