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

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