# Complete the Max Heap

Sep 5, 2019 by Chris Luedtke

## Description

Given a partial object representation of a Max Heap (below), complete the `insert` and `delete` methods.

Max Heap are binary tree data structures implemented as an array.

1. each node is greater than each of its children
2. the tree is balanced
3. all leaves are in the leftmost position available

The storage of heaps are implemented as arrays. This allows us to take advantage of constant-time access to any element in the heap. Given a parent node’s index value, `i`, the parent’s left child index is `2i + 1`, and its right child index is `2i + 2`. Conversely, a node’s parent is located at index `floor((i - 1) / 2)`.

To get a better understanding of heaps and how they work, study the images below and experiment with this Min Heap annimation. ``````class MaxHeap:
def __init__(self):
self.storage = []

def insert(self, value):
self.storage.append(value)
self._bubble_up(len(self.storage)-1)

def delete(self):
if not self.storage:
return None
elif len(self.storage) == 1:
return self.storage.pop()
else:
top = self.storage
self.storage = self.storage.pop()
self._sift_down(0)

def _bubble_up(self, index):
# TODO

def _sift_down(self, index):
# TODO
``````

## Solution

``````class MaxHeap:
def __init__(self):
self.storage = []

def insert(self, value):
self.storage.append(value)
self._bubble_up(len(self.storage)-1)

def delete(self):
if not self.storage:
return None
elif len(self.storage) == 1:
return self.storage.pop()
else:
top = self.storage  # store top heap value so we can return it
self.storage = self.storage.pop()
self._sift_down(0)

def get_max(self):
if self.storage:
return self.storage
else:
return None

def get_size(self):
return len(self.storage)

def _bubble_up(self, index):
while index > 0:
# compare to parent
parent_i = (index - 1) // 2  # floor division

if parent_i < 0:
break

if self.storage[parent_i] < self.storage[index]:
self.storage[index], self.storage[parent_i] = \
self.storage[parent_i], self.storage[index]  # swap

index = parent_i
else:
break

def _sift_down(self, index):
end_i = len(self.storage) - 1
l_i = 2 * index + 1

while l_i <= end_i:
r_i = l_i + 1

if (r_i <= end_i and self.storage[l_i] < self.storage[r_i]):
swap_i = r_i
else:
swap_i = l_i

if self.storage[index] < self.storage[swap_i]:
self.storage[index], self.storage[swap_i] = \
self.storage[swap_i], self.storage[index]  # swap

index = swap_i
l_i = 2 * index + 1
else:
break
``````