Binary Heap Visualization
Explore the complete binary tree with heap property: parent nodes are always greater (max-heap) or smaller (min-heap) than their children.
Interactive Heap Operations
🌳 Tree & Array View
Heap Visualization
🌳
Empty Heap
Array Representation:
Current Step:
Select an operation to begin visualization
Complexity Analysis
O(log n)
Insert
O(log n)
Extract
O(1)
Peek
O(n) Space
Array-based storage
Heap Properties
• Complete Binary Tree: All levels filled except possibly the last
• Heap Property: Parent ≥ Children
• Array Implementation: Left child at 2i+1, Right child at 2i+2
• Parent Formula: Parent at ⌊(i-1)/2⌋
• Height: O(log n) for n elements
Applications
• Priority Queues: Task scheduling with priorities
• Heap Sort: Efficient O(n log n) sorting algorithm
• Dijkstra's Algorithm: Finding shortest paths in graphs
• Median Finding: Using min-heap and max-heap together
• K-way Merge: Merging k sorted arrays efficiently
Implementation
class MaxHeap:
def __init__(self):
self.heap = []
def parent(self, i):
return (i - 1) // 2
def left_child(self, i):
return 2 * i + 1
def right_child(self, i):
return 2 * i + 2
def insert(self, value):
# Add element at the end
self.heap.append(value)
# Heapify up
current = len(self.heap) - 1
while current > 0:
parent = self.parent(current)
if self.heap[current] > self.heap[parent]:
# Swap with parent
self.heap[current], self.heap[parent] = \
self.heap[parent], self.heap[current]
current = parent
else:
break
def extract_root(self):
if not self.heap:
return None
# Save root value
root = self.heap[0]
# Move last element to root
self.heap[0] = self.heap[-1]
self.heap.pop()
# Heapify down
self._heapify_down(0)
return root
def _heapify_down(self, i):
size = len(self.heap)
while True:
largest = i
left = self.left_child(i)
right = self.right_child(i)
if left < size:
if self.heap[left] > self.heap[largest]:
largest = left
if right < size:
if self.heap[right] > self.heap[largest]:
largest = right
if largest == i:
break
# Swap with largest child
self.heap[i], self.heap[largest] = \
self.heap[largest], self.heap[i]
i = largest
def peek(self):
return self.heap[0] if self.heap else None
def size(self):
return len(self.heap)