-
Notifications
You must be signed in to change notification settings - Fork 23
/
binaryheap.py
171 lines (149 loc) · 6.87 KB
/
binaryheap.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
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#!python
class BinaryMinHeap(object):
"""BinaryMinHeap: a partially ordered collection with efficient methods to
insert new items in partial order and to access and remove its minimum item.
Items are stored in a dynamic array that implicitly represents a complete
binary tree with root node at index 0 and last leaf node at index n-1."""
def __init__(self, items=None):
"""Initialize this heap and insert the given items, if any."""
# Initialize an empty list to store the items
self.items = []
if items:
for item in items:
self.insert(item)
def __repr__(self):
"""Return a string representation of this heap."""
return 'BinaryMinHeap({})'.format(self.items)
def is_empty(self):
"""Return True if this heap is empty, or False otherwise."""
# TODO: Check if empty based on how many items are in the list
# ...
def size(self):
"""Return the number of items in this heap."""
return len(self.items)
def insert(self, item):
"""Insert the given item into this heap.
TODO: Best case running time: ??? under what conditions?
TODO: Worst case running time: ??? under what conditions?"""
# Insert the item at the end and bubble up to the root
self.items.append(item)
if self.size() > 1:
self._bubble_up(self._last_index())
def get_min(self):
"""Return the minimum item at the root of this heap.
Best and worst case running time: O(1) because min item is the root."""
if self.size() == 0:
raise ValueError('Heap is empty and has no minimum item')
assert self.size() > 0
return self.items[0]
def delete_min(self):
"""Remove and return the minimum item at the root of this heap.
TODO: Best case running time: ??? under what conditions?
TODO: Worst case running time: ??? under what conditions?"""
if self.size() == 0:
raise ValueError('Heap is empty and has no minimum item')
elif self.size() == 1:
# Remove and return the only item
return self.items.pop()
assert self.size() > 1
min_item = self.items[0]
# Move the last item to the root and bubble down to the leaves
last_item = self.items.pop()
self.items[0] = last_item
if self.size() > 1:
self._bubble_down(0)
return min_item
def replace_min(self, item):
"""Remove and return the minimum item at the root of this heap,
and insert the given item into this heap.
This method is more efficient than calling delete_min and then insert.
TODO: Best case running time: ??? under what conditions?
TODO: Worst case running time: ??? under what conditions?"""
if self.size() == 0:
raise ValueError('Heap is empty and has no minimum item')
assert self.size() > 0
min_item = self.items[0]
# Replace the root and bubble down to the leaves
self.items[0] = item
if self.size() > 1:
self._bubble_down(0)
return min_item
def _bubble_up(self, index):
"""Ensure the heap ordering property is true above the given index,
swapping out of order items, or until the root node is reached.
Best case running time: O(1) if parent item is smaller than this item.
Worst case running time: O(log n) if items on path up to root node are
out of order. Maximum path length in complete binary tree is log n."""
if index == 0:
return # This index is the root node (does not have a parent)
if not (0 <= index <= self._last_index()):
raise IndexError('Invalid index: {}'.format(index))
# Get the item's value
item = self.items[index]
# Get the parent's index and value
parent_index = self._parent_index(index)
parent_item = self.items[parent_index]
# TODO: Swap this item with parent item if values are out of order
# ...
# TODO: Recursively bubble up again if necessary
# ...
def _bubble_down(self, index):
"""Ensure the heap ordering property is true below the given index,
swapping out of order items, or until a leaf node is reached.
Best case running time: O(1) if item is smaller than both child items.
Worst case running time: O(log n) if items on path down to a leaf are
out of order. Maximum path length in complete binary tree is log n."""
if not (0 <= index <= self._last_index()):
raise IndexError('Invalid index: {}'.format(index))
# Get the index of the item's left and right children
left_index = self._left_child_index(index)
right_index = self._right_child_index(index)
if left_index > self._last_index():
return # This index is a leaf node (does not have any children)
# Get the item's value
item = self.items[index]
# TODO: Determine which child item to compare this node's item to
child_index = 0
# ...
# TODO: Swap this item with a child item if values are out of order
child_item = self.items[child_index]
# ...
# TODO: Recursively bubble down again if necessary
# ...
def _last_index(self):
"""Return the last valid index in the underlying array of items."""
return len(self.items) - 1
def _parent_index(self, index):
"""Return the parent index of the item at the given index."""
if index <= 0:
raise IndexError('Heap index {} has no parent index'.format(index))
return (index - 1) >> 1 # Shift right to divide by 2
def _left_child_index(self, index):
"""Return the left child index of the item at the given index."""
return (index << 1) + 1 # Shift left to multiply by 2
def _right_child_index(self, index):
"""Return the right child index of the item at the given index."""
return (index << 1) + 2 # Shift left to multiply by 2
def test_binary_min_heap():
# Create a binary min heap of 7 items
items = [9, 25, 86, 3, 29, 5, 55]
heap = BinaryMinHeap()
print('heap: {}'.format(heap))
print('\nInserting items:')
for index, item in enumerate(items):
heap.insert(item)
print('insert({})'.format(item))
print('heap: {}'.format(heap))
print('size: {}'.format(heap.size()))
heap_min = heap.get_min()
real_min = min(items[: index + 1])
correct = heap_min == real_min
print('get_min: {}, correct: {}'.format(heap_min, correct))
print('\nDeleting items:')
for item in sorted(items):
heap_min = heap.delete_min()
print('delete_min: {}'.format(heap_min))
print('heap: {}'.format(heap))
print('size: {}'.format(heap.size()))
if __name__ == '__main__':
test_binary_min_heap()