Min/Max Heap

Data Structure: What is a Min/Max (Binary Heap) Heap? What are the operations it supports and give their runtimes. Implement it

Binary Heap. A min heap is a complete binary tree where:

  • each node is smaller its children.
  • Therefore, the root is the minimum element in the tree.
  • The min heap uses an array to represent the data and operation. For example a min heap:
     4
   /   \
  50    7
 / \   /
55 90 87

Heap [0, 4, 50, 7, 55, 90, 87]

Method in class: insert, remove_min
For example insert(2) in a min heap:

     4                     4                     2
   /   \                 /   \                 /   \
  50    7      -->     50     2       -->     50    4
 / \   /  \           /  \   / \             /  \  /  \
55 90 87   2         55  90 87  7           55  90 87  7

For example remove_min() in a min heap:

     4                     87                    7
   /   \                 /   \                 /   \
  50    7      -->     50     7       -->     50    87
 / \   /              /  \                   /  \
55 90 87             55  90                 55  90

class MinHeap(object):

    def __init__(self):
        # TODO: Implement me
        self.heap = [0]
        self.size = 0

    def extract_min(self):
        # TODO: Implement me
				if len(self.heap) > 1:
            heap_min = self.heap[1]
            self.heap[1] = self.heap[self.size]
            self.size -= 1
            self.heap.pop()
            self._bubble_up(self.size)
            return heap_min

    def peek_min(self):
        # TODO: Implement me
				if len(self.heap) > 1:
            return self.heap[1]
        else:
            return None

    def insert(self, data):
        # TODO: Implement me
        self.heap.append(data)
        self.size += 1
        self._bubble_up(self.size)

    def _bubble_up(self, index):
        # TODO: Implement me
				def swap(i,j):
		        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
        while (index//2 > 0):
						# (size // 2) is the parent
            if(self.heap[index//2] > self.heap[index]):
                swap(index, index//2)
            index = index // 2

Source: Interactive Coding Challenges