Top-K Elements

import heapq

# heapq is a MIN heap by default
nums = [3, 1, 4, 1, 5]
heapq.heapify(nums)         # O(n) - transforms list in-place
heapq.heappush(nums, 2)     # O(log n)
smallest = heapq.heappop(nums)  # O(log n) - pops SMALLEST

# MAX heap trick: NEGATE all values
max_heap = []
heapq.heappush(max_heap, -5)    # push negative
heapq.heappush(max_heap, -3)
val = -heapq.heappop(max_heap)  # negate on pop -> gives 5 (largest)

# Convenience functions
heapq.nlargest(k, iterable)     # returns k largest (uses min heap internally)
heapq.nsmallest(k, iterable)    # returns k smallest (uses max heap internally)

# Tuple comparison: compares first element, then second for ties
heapq.heappush(heap, (priority, value))
# Useful for custom ordering (frequency, distance, etc.)

import heapq

def top_k_largest(nums, k):
    """Returns k largest elements using a min heap of size k."""
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)  # remove smallest -> keeps k largest
    return heap  # heap[0] is the kth largest

def top_k_smallest(nums, k):
    """Returns k smallest elements using a max heap of size k."""
    heap = []  # max heap via negation
    for num in nums:
        heapq.heappush(heap, -num)
        if len(heap) > k:
            heapq.heappop(heap)  # remove largest (most negative)
    return [-x for x in heap]

def findKthLargest(nums, k):
    # Approach 1: Min heap of size k
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]  # root = kth largest

    # Approach 2: One-liner
    # return heapq.nlargest(k, nums)[-1]

import random

def findKthLargest_quickselect(nums, k):
    """Find kth largest = (n-k)th smallest in 0-indexed."""
    target = len(nums) - k

    def quickselect(left, right):
        pivot_idx = random.randint(left, right)
        nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
        pivot = nums[right]

        store = left
        for i in range(left, right):
            if nums[i] < pivot:
                nums[i], nums[store] = nums[store], nums[i]
                store += 1
        nums[store], nums[right] = nums[right], nums[store]

        if store == target:
            return nums[store]
        elif store < target:
            return quickselect(store + 1, right)
        else:
            return quickselect(left, store - 1)

    return quickselect(0, len(nums) - 1)

from collections import Counter

def topKFrequent(nums, k):
    # Count frequencies, then use heap
    count = Counter(nums)

    # Min heap of size k based on frequency
    return heapq.nlargest(k, count.keys(), key=count.get)

    # OR manual heap approach:
    # heap = []
    # for num, freq in count.items():
    #     heapq.heappush(heap, (freq, num))
    #     if len(heap) > k:
    #         heapq.heappop(heap)
    # return [num for freq, num in heap]

def topKFrequent_bucket(nums, k):
    count = Counter(nums)
    # Bucket index = frequency, bucket value = list of nums with that freq
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        buckets[freq].append(num)

    result = []
    for freq in range(len(buckets) - 1, 0, -1):
        for num in buckets[freq]:
            result.append(num)
            if len(result) == k:
                return result
    return result

def kClosest(points, k):
    # Max heap of size k (negate distance to simulate max heap)
    heap = []
    for x, y in points:
        dist = -(x * x + y * y)  # negate for max heap
        heapq.heappush(heap, (dist, x, y))
        if len(heap) > k:
            heapq.heappop(heap)  # remove farthest
    return [[x, y] for _, x, y in heap]

def mergeKLists(lists):
    """Merge k sorted linked lists using a min heap."""
    heap = []
    # Push the head of each list
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    dummy = ListNode(0)
    curr = dummy

    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
            # 'i' as tiebreaker prevents comparing ListNode objects

    return dummy.next

from collections import Counter

def reorganizeString(s):
    count = Counter(s)
    max_heap = [(-freq, ch) for ch, freq in count.items()]
    heapq.heapify(max_heap)

    result = []
    prev_freq, prev_ch = 0, ""

    while max_heap:
        freq, ch = heapq.heappop(max_heap)
        # Re-add previous character if it still has count
        if prev_freq < 0:
            heapq.heappush(max_heap, (prev_freq, prev_ch))

        result.append(ch)
        prev_freq = freq + 1  # used one (freq is negative)
        prev_ch = ch

    return "".join(result) if len(result) == len(s) else ""

class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.heap = []
        for num in nums:
            self.add(num)

    def add(self, val):
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0]  # root = kth largest

heapq.heappush(heap, -val)       # push negated
original = -heapq.heappop(heap)  # negate back on pop