-
Notifications
You must be signed in to change notification settings - Fork 0
/
minheap.py
66 lines (56 loc) · 1.81 KB
/
minheap.py
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
class BinaryHeap(object):
"""
BinaryHeap class represents a binary heap data structure.
"""
def __init__(self) -> None:
self.items = [None]
def __len__(self):
return len(self.items) - 1
def _percolate_up(self):
"""
Helper method to percolate up the last inserted element in the heap.
"""
i = len(self)
parent = i // 2
while parent > 0:
if self.items[i] < self.items[parent]:
self.items[parent], self.items[i] = self.items[i], self.items[parent]
i = parent
parent = i // 2
def insert(self, k):
"""
Inserts an element into the binary heap.
Args:
k: The element to be inserted.
"""
self.items.append(k)
self._percolate_up()
def _percolate_down(self, idx):
"""
Helper method to percolate down the element at the given index in the heap.
Args:
idx: The index of the element to be percolated down.
"""
left = idx * 2
right = idx * 2 + 1
smallest = idx
if left <= len(self) and self.items[left] < self.items[smallest]:
smallest = left
if right <= len(self) and self.items[right] < self.items[smallest]:
smallest = right
if smallest != idx:
self.items[idx], self.items[smallest] = (
self.items[smallest],
self.items[idx],
)
def extract(self):
"""
Removes and returns the minimum element from the binary heap.
Returns:
The minimum element from the binary heap.
"""
extracted = self.items[1]
self.items[1] = self.items[len(self)]
self.items.pop()
self._percolate_down(1)
return extracted