Binary Heap
- 3 min read
- Binary Heap
- Data Structure
3 years ago
- A binary heap should be balanced, i.e. complete (each level has all of its nodes, except the last level, which is filled from left to right).
- If represented using a list, the left and right child of a node at index
iexist at indexesi * 2andi * 2 + 1.- This is assuming the first value in the list representation is a dummy value, used to make indexing easier.
- Heap Order Property-
- For a min heap, for every node
nwith a parentp, the value at nodepis smaller than or equal to the value in noden. - The value at the root is always the smallest in the entire heap at any given time.
- For a min heap, for every node
- To build a heap from a list of values:
- Set the new list of values to
self.values - Starting from the middle node and working your way up to the root, percolate down all nodes
- Why does starting from the middle work?
perc_down()ensures the largest child is always moved down the tree- Since the heap is a complete binary tree, any nodes past the halfway point will be leaves and therefore have no children.
- Set the new list of values to
- Time Complexity:
- Enqueue & Dequeue -
O(log n) - Build Heap -
O(n)
- Enqueue & Dequeue -
class MinHeap:
def __init__(self):
self.values = [None]
self.size = 0 # Could've used len(self.values) but this is smaller and
# also more easier to understand due to the fact that we have a dummy value at the 0th index
def perc_up(self, idx):
'''
Conditionally swaps a node with its parent upwards to the appropriate position
to maintain the heap order property
'''
while idx // 2:
if self.values[idx] < self.values[idx // 2]:
self.values[idx], self.values[idx // 2] = self.values[idx // 2], self.values[idx]
idx //= 2
def insert(self, value):
'''
When a new value is inserted, it is added to the end of the list and percolated up
the it's appropriate position.
'''
self.values.append(value)
self.size += 1
self.perc_up(self.size)
def get_min_child_idx(self, idx):
'''
Returns the index of child with the smaller value.
'''
if idx * 2 + 1 > self.size: # If no right child, return left child
return idx * 2
if self.values[idx * 2] < self.values[idx * 2 + 1]: # Return left child if it is smaller
return idx * 2
return idx * 2 + 1
def perc_down(self, idx):
'''
When the minimum value (at the root) is removed, the last child in the tree is swapped
with the root, and percolated down to its appropriate position. If you're wondering why
this function doesn't check for whether or not a left child exists, it's because this
function will never be called on a child node.
'''
while idx * 2 <= self.size:
min_child_idx = self.get_min_child_idx(idx)
if self.values[idx] > self.values[min_child_idx]:
self.values[idx], self.values[min_child_idx] = self.values[min_child_idx], self.values[idx]
idx = min_child_idx
def del_min(self):
'''
Returns the node with the smallest value in the heap. This messes up the heap order
property, so further processing is done once the node is removed to maintain the
sanctity of the holy binary heap.
'''
return_value = self.values[1]
self.values[1] = self.values[-1]
self.size -= 1
self.values.pop()
self.perc_down(1)
return return_value
def build_heap(self, values):
'''
Builds a new heap from a list of values. We initialize an entire list to self.values, and
starting from the middle and work our way up towards the root.
from the middle because
'''
i = len(values) // 2
self.values = [0] + values[:]
while i:
self.perc_down(i)
i -= 1