Repository navigation
Expand file tree
/
Copy pathmin_heap.py
More file actions
46 lines (35 loc) · 1.5 KB
/
Copy pathmin_heap.py
File metadata and controls
46 lines (35 loc) · 1.5 KB
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
class MinHeap:
"""Min Heap.
A Min Heap is a complete binary tree where every parent node is smaller than or equal to its children.
The smallest element is always at the root. It is commonly backed by an array where for a node at
index `i`, its parent is at `(i - 1) // 2` and its children are at `2i + 1` and `2i + 2`.
New values are inserted at the end of the array and then "sifted up" - repeatedly swapped with their
parent until the heap property is restored.
"""
def __init__(self):
self.list = []
def insert(self, val):
"""Add val to the end of the array, then sift it up until the heap property is restored."""
self.list.append(val)
self._sift_up(len(self.list) - 1)
def is_empty(self):
return len(self.list) == 0
def size(self):
return len(self.list)
def values(self):
return self.list.copy()
def _get_parent(self, idx):
return (idx - 1) // 2
def _sift_up(self, idx):
"""Repeatedly swap the value at idx with its parent until it is no longer smaller than its parent."""
current_index = idx
while current_index > 0:
parent = self._get_parent(current_index)
if self.list[current_index] < self.list[parent]:
self.list[current_index], self.list[parent] = (
self.list[parent],
self.list[current_index],
)
current_index = parent
else:
break