Problem: Write a heap class that represents a minimum heap using an array. Implement the insert method for this min heap class.

Example:

min_heap = MinHeap()
min_heap.insert(2)
min_heap.insert(4)
min_heap.insert(1)
# Underlying array should look like: [1, 4, 2]

1. Understand

Restate the problem. Come up with (additional) test cases. Identify input/output data types, potential edge cases that may result in an error. Are there any time/space constraints?

I need to a list to represent a min heap. The insert function should take an integer argument and that should be appended to list. Then this newly appended integer should be “bubbled up” if necessary in order to maintain he properties of a minheap.

2. Match

What type of problem is this? What data structure could you use? Are there general techniques you’re familiar with that could apply?

This is a list problem. I can use the existing append function in Python to append the new element to the end of the list. I can use the fact that a node’s parent index = (current index -1) //2 to check if the parent is less than the current node.

3. Plan/Pseudo

# heap_list = [] (list)
# getParent(index) returns parent index (int)
# getLeft(index) returns left child index (int)
# getRight(index) returns right child index (int)
# insert(int) appends int to minheap list then calls checks
# if min heap constraints still hold:
# Root node must be smallest element,
# All parent nodes are less than or equal
# to their children (do this bottom up)

4. Implement

5. Review

min_heap = MinHeap()
min_heap.insert(2)
print(min_heap)
min_heap.insert(4)
print(min_heap)
min_heap.insert(1)
print(min_heap)

6. Evaluate

Space: O(N)

Time: Worst: O(N), Best O(1)