​
Core Implementation

​
Binary Heap (Min Heap)

class MinHeap:
    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 swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
    
    def insert(self, key):
        self.heap.append(key)
        self._sift_up(len(self.heap) - 1)
    
    def _sift_up(self, i):
        parent = self.parent(i)
        if i > 0 and self.heap[i] < self.heap[parent]:
            self.swap(i, parent)
            self._sift_up(parent)
    
    def extract_min(self):
        if not self.heap:
            raise IndexError("Heap is empty")
        
        min_val = self.heap[0]
        last_val = self.heap.pop()
        
        if self.heap:
            self.heap[0] = last_val
            self._sift_down(0)
        
        return min_val
    
    def _sift_down(self, i):
        min_idx = i
        left = self.left_child(i)
        right = self.right_child(i)
        
        if left < len(self.heap) and self.heap[left] < self.heap[min_idx]:
            min_idx = left
        
        if right < len(self.heap) and self.heap[right] < self.heap[min_idx]:
            min_idx = right
        
        if min_idx != i:
            self.swap(i, min_idx)
            self._sift_down(min_idx)

​
Implementation Variations

​
1. Max Heap

class MaxHeap(MinHeap):
    def _sift_up(self, i):
        parent = self.parent(i)
        if i > 0 and self.heap[i] > self.heap[parent]:
            self.swap(i, parent)
            self._sift_up(parent)
    
    def _sift_down(self, i):
        max_idx = i
        left = self.left_child(i)
        right = self.right_child(i)
        
        if left < len(self.heap) and self.heap[left] > self.heap[max_idx]:
            max_idx = left
        
        if right < len(self.heap) and self.heap[right] > self.heap[max_idx]:
            max_idx = right
        
        if max_idx != i:
            self.swap(i, max_idx)
            self._sift_down(max_idx)
    
    def extract_max(self):
        return super().extract_min()

​
2. Priority Queue with Custom Objects

class PriorityQueue:
    def __init__(self):
        self.heap = []
        self.entry_count = 0  # For stable sorting
    
    class Entry:
        def __init__(self, priority, count, item):
            self.priority = priority
            self.count = count
            self.item = item
        
        def __lt__(self, other):
            return (self.priority, self.count) < (other.priority, other.count)
    
    def push(self, item, priority):
        entry = self.Entry(priority, self.entry_count, item)
        heapq.heappush(self.heap, entry)
        self.entry_count += 1
    
    def pop(self):
        if not self.heap:
            raise IndexError("Queue is empty")
        return heapq.heappop(self.heap).item

​
3. D-ary Heap

class DaryHeap:
    def __init__(self, d=3):
        self.heap = []
        self.d = d
    
    def parent(self, i):
        return (i - 1) // self.d
    
    def child(self, i, k):
        return self.d * i + k + 1
    
    def insert(self, key):
        self.heap.append(key)
        self._sift_up(len(self.heap) - 1)
    
    def _sift_up(self, i):
        parent = self.parent(i)
        if i > 0 and self.heap[i] < self.heap[parent]:
            self.swap(i, parent)
            self._sift_up(parent)
    
    def _sift_down(self, i):
        min_idx = i
        for k in range(self.d):
            child = self.child(i, k)
            if child < len(self.heap) and self.heap[child] < self.heap[min_idx]:
                min_idx = child
        
        if min_idx != i:
            self.swap(i, min_idx)
            self._sift_down(min_idx)

​
Time Complexities

OperationBinary HeapD-ary HeapPriority Queue
Build HeapO(n)O(n)O(n)
InsertO(log n)O(logd n)O(log n)
Extract Min/MaxO(log n)O(d logd n)O(log n)
Decrease KeyO(log n)O(logd n)N/A
Get Min/MaxO(1)O(1)O(1)
DeleteO(log n)O(d logd n)O(log n)
MergeO(n)O(n)O(n)

​
Space Complexities

ImplementationSpace ComplexityAdditional Notes
Binary HeapO(n)Complete binary tree structure
D-ary HeapO(n)D children per node
Priority QueueO(n)Additional space for entry objects

​
Common Data Structure Patterns

  1. Priority Queue Applications

    • Task Scheduling
    • Event Processing
    • Dijkstra’s Algorithm

  2. Heap Sort Patterns

    • K-way Merge
    • Partial Sorting
    • Stream Processing

  3. Median Finding

    • Running Median
    • Sliding Window Median
    • Two-Heap Pattern

  4. K-th Element Problems

    • K Largest Elements
    • K Closest Points
    • Top K Frequent

  5. Merge Patterns

    • Merge K Sorted Lists
    • Merge K Sorted Arrays
    • Stream Merging

  6. Optimization Problems

    • Load Balancing
    • Resource Allocation
    • Job Scheduling

​
Edge Cases to Consider

  1. Empty Heap
if not self.heap:
    raise IndexError("Heap is empty")
  1. Single Element
if len(self.heap) == 1:
    return self.heap.pop()
  1. Duplicate Elements
# Using custom comparison
class HeapEntry:
    def __init__(self, val, index):
        self.val = val
        self.index = index
    
    def __lt__(self, other):
        if self.val == other.val:
            return self.index < other.index
        return self.val < other.val

​
Optimization Techniques

  1. Array-based Implementation
def build_heap(self, arr):
    self.heap = arr[:]
    n = len(self.heap)
    for i in range(n//2 - 1, -1, -1):
        self._sift_down(i)
  1. Bottom-up Heap Construction
def build_heap_bottom_up(self, arr):
    self.heap = arr[:]
    for i in range(len(self.heap)//2 - 1, -1, -1):
        self._sift_down(i)
  1. Index Mapping for Quick Access
class IndexedHeap:
    def __init__(self):
        self.heap = []
        self.index_map = {}  # Value to index mapping
    
    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
        self.index_map[self.heap[i]] = i
        self.index_map[self.heap[j]] = j

​
Memory Management

  1. Fixed-size Heap
class FixedSizeHeap:
    def __init__(self, max_size):
        self.max_size = max_size
        self.heap = []
    
    def push(self, item):
        if len(self.heap) < self.max_size:
            heapq.heappush(self.heap, item)
        elif item > self.heap[0]:
            heapq.heapreplace(self.heap, item)
  1. Memory-Efficient Implementation
class CompactHeap:
    def __init__(self):
        self.data = array.array('i')  # Use array module for primitive types
    
    def push(self, item):
        self.data.append(item)
        self._sift_up(len(self.data) - 1)

​
Performance Considerations

  1. Batch Operations
def push_many(self, items):
    self.heap.extend(items)
    self._heapify()  # More efficient than individual pushes
  1. Cache-Friendly Implementation
class CacheOptimizedHeap:
    def __init__(self):
        self.block_size = 64  # Cache line size
        self.heap = bytearray(self.block_size * 16)

​
Common Pitfalls

  1. Incorrect Heap Property Maintenance
# Wrong
def decrease_key(self, i, new_val):
    self.heap[i] = new_val
    # Missing sift up

# Correct
def decrease_key(self, i, new_val):
    if new_val > self.heap[i]:
        raise ValueError("New value is greater than current value")
    self.heap[i] = new_val
    self._sift_up(i)
  1. Improper Memory Management
# Wrong
def extract_min(self):
    min_val = self.heap[0]
    self.heap[0] = self.heap[-1]
    self.heap.pop()  # Memory leak potential

# Correct
def extract_min(self):
    if not self.heap:
        raise IndexError("Heap is empty")
    min_val = self.heap[0]
    last_val = self.heap.pop()
    if self.heap:
        self.heap[0] = last_val
        self._sift_down(0)
    return min_val
  1. Index Out of Bounds
# Wrong
def get_children(self, i):
    left = 2 * i + 1
    right = 2 * i + 2
    return [left, right]  # Might be invalid indices

# Correct
def get_children(self, i):
    children = []
    left = 2 * i + 1
    right = 2 * i + 2
    if left < len(self.heap):
        children.append(left)
    if right < len(self.heap):
        children.append(right)
    return children