Heap and Priority Queue Pattern

Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
Explanation: The array sorted is [1, 2, 3, 4, 5, 6], so 2nd largest is 5

import heapq

def find_kth_largest(nums, k):
    """
    Find kth largest element using min heap.

    Time Complexity: O(n log k) - process n elements with heap of size k
    Space Complexity: O(k) - heap stores k elements
    """
    # Maintain min heap of k largest elements
    min_heap = []

    for num in nums:
        heapq.heappush(min_heap, num)

        # Keep heap size at k
        if len(min_heap) > k:
            heapq.heappop(min_heap)

    # Root of min heap is kth largest
    return min_heap[0]

# Alternative: Using Python's nlargest
def find_kth_largest_alt(nums, k):
    """Alternative using heapq.nlargest."""
    return heapq.nlargest(k, nums)[-1]

# Test
nums = [3, 2, 1, 5, 6, 4]
k = 2
print(find_kth_largest(nums, k))  # Output: 5

nums = [3, 2, 1, 5, 6, 4], k = 2

Process nums[0]=3:
  heap = [3], size = 1 < k, keep all

Process nums[1]=2:
  heap = [2, 3], size = 2 = k, keep all
  Min heap: 2 at root

Process nums[2]=1:
  heap = [1, 3, 2], size = 3 > k
  Pop smallest: heap = [2, 3]
  Min heap: 2 at root

Process nums[3]=5:
  heap = [2, 5, 3], size = 3 > k
  Pop smallest: heap = [3, 5]
  Min heap: 3 at root

Process nums[4]=6:
  heap = [3, 5, 6], size = 3 > k
  Pop smallest: heap = [5, 6]
  Min heap: 5 at root

Process nums[5]=4:
  heap = [4, 6, 5], size = 3 > k
  Pop smallest: heap = [5, 6]
  Min heap: 5 at root

Result: 5 (kth largest element)

Heap maintains 2 largest elements: [5, 6]
Smallest of these (at root) is kth largest: 5

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]

import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_k_lists(lists):
    """
    Merge k sorted linked lists.

    Time Complexity: O(n log k) - n total nodes, heap operations on k elements
    Space Complexity: O(k) - heap stores at most k nodes
    """
    # Min heap: (value, list_index, node)
    # Use index to break ties (Python heapq requires comparable elements)
    min_heap = []

    # Add first node from each list
    for i, head in enumerate(lists):
        if head:
            heapq.heappush(min_heap, (head.val, i, head))

    # Dummy head for result list
    dummy = ListNode(0)
    current = dummy

    while min_heap:
        # Get smallest element
        val, i, node = heapq.heappop(min_heap)

        # Add to result
        current.next = node
        current = current.next

        # Add next node from same list
        if node.next:
            heapq.heappush(min_heap, (node.next.val, i, node.next))

    return dummy.next

# Helper to create linked list from array
def create_list(arr):
    """Create linked list from array."""
    dummy = ListNode(0)
    current = dummy
    for val in arr:
        current.next = ListNode(val)
        current = current.next
    return dummy.next

# Helper to convert linked list to array
def list_to_array(head):
    """Convert linked list to array."""
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result

# Test
lists = [
    create_list([1, 4, 5]),
    create_list([1, 3, 4]),
    create_list([2, 6])
]
merged = merge_k_lists(lists)
print(list_to_array(merged))  # Output: [1, 1, 2, 3, 4, 4, 5, 6]

lists = [[1,4,5], [1,3,4], [2,6]]

Initialize heap with first nodes:
  heap = [(1, 0, node1), (1, 1, node1'), (2, 2, node2)]
  Heap structure (min): 1 at root

Iteration 1:
  Pop (1, 0, node1) - smallest
  Add to result: [1]
  Push next from list 0: (4, 0, node4)
  heap = [(1, 1, node1'), (2, 2, node2), (4, 0, node4)]

Iteration 2:
  Pop (1, 1, node1') - smallest
  Add to result: [1, 1]
  Push next from list 1: (3, 1, node3)
  heap = [(2, 2, node2), (3, 1, node3), (4, 0, node4)]

Iteration 3:
  Pop (2, 2, node2) - smallest
  Add to result: [1, 1, 2]
  Push next from list 2: (6, 2, node6)
  heap = [(3, 1, node3), (4, 0, node4), (6, 2, node6)]

Iteration 4:
  Pop (3, 1, node3)
  Add to result: [1, 1, 2, 3]
  Push next from list 1: (4, 1, node4')
  heap = [(4, 0, node4), (4, 1, node4'), (6, 2, node6)]

Iteration 5:
  Pop (4, 0, node4)
  Add to result: [1, 1, 2, 3, 4]
  Push next from list 0: (5, 0, node5)
  heap = [(4, 1, node4'), (5, 0, node5), (6, 2, node6)]

Iteration 6:
  Pop (4, 1, node4')
  Add to result: [1, 1, 2, 3, 4, 4]
  No next from list 1
  heap = [(5, 0, node5), (6, 2, node6)]

Iteration 7:
  Pop (5, 0, node5)
  Add to result: [1, 1, 2, 3, 4, 4, 5]
  No next from list 0
  heap = [(6, 2, node6)]

Iteration 8:
  Pop (6, 2, node6)
  Add to result: [1, 1, 2, 3, 4, 4, 5, 6]
  No next from list 2
  heap = []

Result: [1, 1, 2, 3, 4, 4, 5, 6]

MedianFinder mf = new MedianFinder()
mf.addNum(1)    
mf.addNum(2)    
mf.findMedian() -> 1.5
mf.addNum(3)    
mf.findMedian() -> 2

import heapq

class MedianFinder:
    """
    Maintain running median using two heaps.

    Time Complexity: 
      - addNum: O(log n) - heap operations
      - findMedian: O(1) - just peek at heap tops
    Space Complexity: O(n) - store all numbers
    """

    def __init__(self):
        # Max heap (smaller half) - use negative values for max heap
        self.small = []
        # Min heap (larger half)
        self.large = []

    def addNum(self, num):
        """Add number to data structure."""
        # Add to max heap (small) first
        heapq.heappush(self.small, -num)

        # Balance: ensure max(small) <= min(large)
        if self.small and self.large and (-self.small[0] > self.large[0]):
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)

        # Balance sizes: difference should be at most 1
        if len(self.small) > len(self.large) + 1:
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)
        elif len(self.large) > len(self.small):
            val = heapq.heappop(self.large)
            heapq.heappush(self.small, -val)

    def findMedian(self):
        """Find current median."""
        if len(self.small) > len(self.large):
            # Odd count: median is top of larger heap (small)
            return -self.small[0]
        else:
            # Even count: median is average of both tops
            return (-self.small[0] + self.large[0]) / 2.0

# Test
mf = MedianFinder()
mf.addNum(1)
mf.addNum(2)
print(mf.findMedian())  # Output: 1.5
mf.addNum(3)
print(mf.findMedian())  # Output: 2.0

Operations: addNum(1), addNum(2), findMedian(), addNum(3), findMedian()

addNum(1):
  Push -1 to small: small = [-1], large = []
  No balancing needed (large is empty)
  Sizes: small=1, large=0

addNum(2):
  Push -2 to small: small = [-2, -1], large = []
  Check max(small) vs min(large): -(-2)=2 > empty, skip
  Balance sizes: small=2, large=0 (diff > 1)
    Move from small to large: pop -2, push 2
    small = [-1], large = [2]
  Sizes: small=1, large=1

findMedian():
  Even count: (1 + 2) / 2 = 1.5
  Result: 1.5

addNum(3):
  Push -3 to small: small = [-3, -1], large = [2]
  Check max(small) vs min(large): -(-3)=3 > 2
    Move max from small to large: pop -3, push 3
    small = [-1], large = [2, 3]
  Balance sizes: small=1, large=2 (large > small)
    Move from large to small: pop 2, push -2
    small = [-2, -1], large = [3]
  Sizes: small=2, large=1

findMedian():
  Odd count: top of small = -(-2) = 2
  Result: 2.0

Final state:
  small (max heap) = [-2, -1] → represents [2, 1]
  large (min heap) = [3]
  Numbers in order: 1, 2, 3
  Median: 2

import heapq

# Single heap for k-th element
def kth_element_template(arr, k):
    """Find kth largest using min heap."""
    heap = []
    for num in arr:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

# Two heaps for running median
class MedianTemplate:
    """Maintain running median."""
    def __init__(self):
        self.small = []  # max heap (negated)
        self.large = []  # min heap

    def add(self, num):
        heapq.heappush(self.small, -num)

        # Balance property
        if self.small and self.large and (-self.small[0] > self.large[0]):
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)

        # Balance sizes
        if len(self.small) > len(self.large) + 1:
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)
        elif len(self.large) > len(self.small):
            val = heapq.heappop(self.large)
            heapq.heappush(self.small, -val)

    def get_median(self):
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2.0

def top_k_frequent(nums, k):
    """
    Find k most frequent elements using heap.

    Time: O(n log k) - Better than O(n log n) full sort
    Space: O(n) - frequency map + O(k) heap
    """
    from collections import Counter
    import heapq

    # Count frequencies
    freq = Counter(nums)

    # Min heap of size k (stores (freq, num) pairs)
    # Keep k largest frequencies
    heap = []
    for num, count in freq.items():
        heapq.heappush(heap, (count, num))
        if len(heap) > k:
            heapq.heappop(heap)

    # Extract numbers (discard frequencies)
    return [num for count, num in heap]

# Example: Social media trending
posts = [1, 1, 1, 2, 2, 3, 4, 4, 4, 4]
print(top_k_frequent(posts, 2))  # [1, 4] - top 2 posts

import heapq
from collections import defaultdict

def dijkstra(graph, start):
    """
    Find shortest paths from start to all nodes.

    Time: O((V + E) log V) with heap
          O(V²) with simple array (worse for sparse graphs)
    Space: O(V)

    Args:
        graph: dict of node -> [(neighbor, weight)]
        start: starting node

    Returns:
        dict of node -> shortest distance from start
    """
    # Distance to each node (infinity initially)
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    # Min heap: (distance, node)
    heap = [(0, start)]
    visited = set()

    while heap:
        current_dist, node = heapq.heappop(heap)

        # Skip if already processed
        if node in visited:
            continue
        visited.add(node)

        # Update neighbors
        for neighbor, weight in graph[node]:
            distance = current_dist + weight

            # Found shorter path
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))

    return distances

# Example: Road network
roads = {
    'A': [('B', 4), ('C', 2)],
    'B': [('C', 1), ('D', 5)],
    'C': [('D', 8), ('E', 10)],
    'D': [('E', 2)],
    'E': []
}

distances = dijkstra(roads, 'A')
print(f"Shortest path A to E: {distances['E']}")  # 11

import heapq
from collections import Counter, namedtuple

Node = namedtuple('Node', ['freq', 'char', 'left', 'right'])

def huffman_encoding(text):
    """
    Build Huffman tree and generate codes.

    Time: O(n log n) - n chars, heap operations
    Space: O(n) - tree nodes
    """
    if not text:
        return {}, None

    # Count frequencies
    freq = Counter(text)

    # Build heap of leaf nodes
    # Use negative freq for max heap behavior (most frequent first)
    heap = [Node(f, ch, None, None) for ch, f in freq.items()]
    heapq.heapify(heap)

    # Build tree
    while len(heap) > 1:
        # Pop two smallest frequency nodes
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)

        # Create parent with combined frequency
        parent = Node(
            freq=left.freq + right.freq,
            char=None,  # Internal nodes have no character
            left=left,
            right=right
        )
        heapq.heappush(heap, parent)

    # Root of tree
    root = heap[0]

    # Generate codes (DFS on tree)
    codes = {}
    def generate_codes(node, code=''):
        if node.char is not None:  # Leaf node
            codes[node.char] = code or '0'  # Single char gets '0'
        else:
            if node.left:
                generate_codes(node.left, code + '0')
            if node.right:
                generate_codes(node.right, code + '1')

    generate_codes(root)
    return codes, root

def encode_text(text, codes):
    """Encode text using Huffman codes."""
    return ''.join(codes[ch] for ch in text)

def decode_text(encoded, root):
    """Decode using Huffman tree."""
    if not encoded:
        return ''

    result = []
    node = root

    for bit in encoded:
        # Traverse tree
        node = node.left if bit == '0' else node.right

        # Reached leaf
        if node.char is not None:
            result.append(node.char)
            node = root  # Reset to root

    return ''.join(result)

# Example
text = "huffman encoding example"
codes, tree = huffman_encoding(text)

print("Character codes:")
for char, code in sorted(codes.items()):
    print(f"  '{char}': {code}")

encoded = encode_text(text, codes)
print(f"\nOriginal: {len(text) * 8} bits")
print(f"Encoded:  {len(encoded)} bits")
print(f"Compression: {(1 - len(encoded)/(len(text)*8)) * 100:.1f}%")

decoded = decode_text(encoded, tree)
assert decoded == text, "Encoding/decoding failed!"