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)

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()

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

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)

if not self.heap:
    raise IndexError("Heap is empty")

if len(self.heap) == 1:
    return self.heap.pop()

# 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

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)

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)

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

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)

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)

def push_many(self, items):
    self.heap.extend(items)
    self._heapify()  # More efficient than individual pushes

class CacheOptimizedHeap:
    def __init__(self):
        self.block_size = 64  # Cache line size
        self.heap = bytearray(self.block_size * 16)

# 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)

# 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

# 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