This notebook was prepared by Donne Martin. Source and license info is on GitHub.

Challenge Notebook¶

Problem: Implement a min heap with extract_min and insert methods.¶

Constraints¶

Can we assume the inputs are ints?
- Yes
Can we assume this fits memory?
- Yes

Test Cases¶

Extract min of an empty tree
Extract min general case
Insert into an empty tree
Insert general case (left and right insert)

          _5_
        /     \
       20     15
      / \    /  \
     22  40 25
     
extract_min(): 5

          _15_
        /      \
       20      25
      / \     /  \
     22  40 

insert(2):

          _2_
        /     \
       20      5
      / \     / \
     22  40  25  15

Algorithm¶

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.

Code¶

In [ ]:

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

Unit Test¶

The following unit test is expected to fail until you solve the challenge.

In [ ]:

# %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()

Solution Notebook¶

Review the Solution Notebook for a discussion on algorithms and code solutions.