This notebook was prepared by Donne Martin. Source and license info is on GitHub.
_5_ / \ 20 15 / \ / \ 22 40 25 extract_min(): 5 _15_ / \ 20 25 / \ / \ 22 40 insert(2): _2_ / \ 20 5 / \ / \ 22 40 25 15
Refer to the Solution Notebook. If you are stuck and need a hint, the solution notebook's algorithm discussion might be a good place to start.
class MinHeap(object):
def __init__(self):
# TODO: Implement me
pass
def extract_min(self):
# TODO: Implement me
pass
def peek_min(self):
# TODO: Implement me
pass
def insert(self, data):
# TODO: Implement me
pass
def _bubble_up(self, index):
# TODO: Implement me
pass
The following unit test is expected to fail until you solve the challenge.
# %load test_min_heap.py
import unittest
class TestMinHeap(unittest.TestCase):
def test_min_heap(self):
heap = MinHeap()
self.assertEqual(heap.peek_min(), None)
self.assertEqual(heap.extract_min(), None)
heap.insert(20)
self.assertEqual(heap.peek_min(), 20)
heap.insert(5)
self.assertEqual(heap.peek_min(), 5)
heap.insert(15)
heap.insert(22)
heap.insert(40)
heap.insert(5)
self.assertEqual(heap.peek_min(), 5)
heap.insert(3)
self.assertEqual(heap.peek_min(), 3)
self.assertEqual(heap.extract_min(), 3)
self.assertEqual(heap.peek_min(), 5)
print('Success: test_min_heap')
def main():
test = TestMinHeap()
test.test_min_heap()
if __name__ == '__main__':
main()
Review the Solution Notebook for a discussion on algorithms and code solutions.