// Min-heap
heap = new MinHeap()
heap.push(val)
heap.pop()
heap.peek()

// Max-heap
heap = new MaxHeap()

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

import heapq

min_heap = []
heapq.heappush(min_heap, val)

max_heap = []                       # negate to simulate max-heap
heapq.heappush(max_heap, -val)

priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;

// No built-in heap — use an array-backed binary heap
// (helpers shown in the snippets below)
const minHeap = [];
const maxHeap = []; // store negated values

heap = new MinHeap()

for each element:
    heap.push(element)
    if heap.size > k:
        heap.pop()

return heap.peek()

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();

    for (int num : nums) {
        pq.offer(num);
        if (pq.size() > k) pq.poll();
    }

    return pq.peek();
}

import heapq

def find_kth_largest(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> pq;

    for (int num : nums) {
        pq.push(num);
        if ((int)pq.size() > k) pq.pop();
    }

    return pq.top();
}

function findKthLargest(nums, k) {
  const h = [];
  const up = (i) => {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (h[p] <= h[i]) break;
      [h[p], h[i]] = [h[i], h[p]];
      i = p;
    }
  };
  const down = () => {
    let i = 0;
    for (;;) {
      const l = 2 * i + 1,
        r = l + 1;
      let m = i;
      if (l < h.length && h[l] < h[m]) m = l;
      if (r < h.length && h[r] < h[m]) m = r;
      if (m === i) break;
      [h[m], h[i]] = [h[i], h[m]];
      i = m;
    }
  };
  const push = (v) => (h.push(v), up(h.length - 1));
  const pop = () => {
    const top = h[0],
      last = h.pop();
    if (h.length) {
      h[0] = last;
      down();
    }
    return top;
  };

  for (const x of nums) {
    push(x);
    if (h.length > k) pop();
  }
  return h[0];
}

heap = new MinHeap()

for each list head:
    push (head.val, head) into heap

dummy = new Node()
curr = dummy

while heap not empty:
    node = heap.poll()
    curr.next = node
    curr = curr.next

    if node.next:
        heap.push(node.next)

return dummy.next

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>(
        (a, b) -> a.val - b.val);

    for (ListNode head : lists)
        if (head != null) pq.offer(head);

    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;

    while (!pq.isEmpty()) {
        ListNode node = pq.poll();
        curr.next = node;
        curr = curr.next;
        if (node.next != null) pq.offer(node.next);
    }

    return dummy.next;
}

import heapq

def merge_k_lists(lists):
    heap = [(node.val, node) for node in lists if node]
    heapq.heapify(heap)

    dummy = curr = ListNode(0)
    while heap:
        _, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, node.next))
    return dummy.next

struct Cmp {
    bool operator()(ListNode* a, ListNode* b) { return a->val > b->val; }
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
    priority_queue<ListNode*, vector<ListNode*>, Cmp> pq;

    for (ListNode* head : lists)
        if (head) pq.push(head);

    ListNode dummy(0);
    ListNode* curr = &dummy;

    while (!pq.empty()) {
        ListNode* node = pq.top(); pq.pop();
        curr->next = node;
        curr = curr->next;
        if (node->next) pq.push(node->next);
    }

    return dummy.next;
}

function mergeKLists(lists) {
  const heap = [];
  const less = (a, b) => a[0] < b[0]; // compare by node.val
  const up = (i) => {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (!less(heap[i], heap[p])) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  };
  const down = () => {
    let i = 0;
    for (;;) {
      const l = 2 * i + 1,
        r = l + 1;
      let m = i;
      if (l < heap.length && less(heap[l], heap[m])) m = l;
      if (r < heap.length && less(heap[r], heap[m])) m = r;
      if (m === i) break;
      [heap[m], heap[i]] = [heap[i], heap[m]];
      i = m;
    }
  };
  const push = (item) => (heap.push(item), up(heap.length - 1));
  const pop = () => {
    const top = heap[0],
      last = heap.pop();
    if (heap.length) {
      heap[0] = last;
      down();
    }
    return top;
  };

  for (const head of lists) if (head) push([head.val, head]);

  const dummy = new ListNode(0);
  let curr = dummy;

  while (heap.length) {
    const node = pop()[1];
    curr.next = node;
    curr = curr.next;
    if (node.next) push([node.next.val, node.next]);
  }

  return dummy.next;
}

maxHeap (lower half)
minHeap (upper half)

function addNum(num):
    push to appropriate heap
    balance sizes

function findMedian():
    if sizes equal: return (maxHeap.peek() + minHeap.peek()) / 2
    else: return maxHeap.peek()

class MedianFinder {
    PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
    PriorityQueue<Integer> min = new PriorityQueue<>();

    public void addNum(int num) {
        if (max.isEmpty() || num <= max.peek()) max.offer(num);
        else min.offer(num);

        if (max.size() > min.size() + 1) min.offer(max.poll());
        if (min.size() > max.size()) max.offer(min.poll());
    }

    public double findMedian() {
        if (max.size() == min.size())
            return (max.peek() + min.peek()) / 2.0;
        return max.peek();
    }
}

import heapq

class MedianFinder:
    def __init__(self):
        self.max = []   # lower half (negated)
        self.min = []   # upper half

    def add_num(self, num):
        if not self.max or num <= -self.max[0]:
            heapq.heappush(self.max, -num)
        else:
            heapq.heappush(self.min, num)

        if len(self.max) > len(self.min) + 1:
            heapq.heappush(self.min, -heapq.heappop(self.max))
        if len(self.min) > len(self.max):
            heapq.heappush(self.max, -heapq.heappop(self.min))

    def find_median(self):
        if len(self.max) == len(self.min):
            return (-self.max[0] + self.min[0]) / 2.0
        return -self.max[0]

class MedianFinder {
    priority_queue<int> max;                                    // lower half
    priority_queue<int, vector<int>, greater<int>> min;         // upper half
public:
    void addNum(int num) {
        if (max.empty() || num <= max.top()) max.push(num);
        else min.push(num);

        if (max.size() > min.size() + 1) { min.push(max.top()); max.pop(); }
        if (min.size() > max.size())     { max.push(min.top()); min.pop(); }
    }

    double findMedian() {
        if (max.size() == min.size())
            return (max.top() + min.top()) / 2.0;
        return max.top();
    }
};

class MedianFinder {
  constructor() {
    this.max = []; // lower half, stored NEGATED (min-heap mechanics)
    this.min = []; // upper half
  }
  #up(i) {
    const h = this.cur;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (h[p] <= h[i]) break;
      [h[p], h[i]] = [h[i], h[p]];
      i = p;
    }
  }
  #down(i = 0) {
    const h = this.cur;
    for (;;) {
      const l = 2 * i + 1,
        r = l + 1;
      let m = i;
      if (l < h.length && h[l] < h[m]) m = l;
      if (r < h.length && h[r] < h[m]) m = r;
      if (m === i) break;
      [h[m], h[i]] = [h[i], h[m]];
      i = m;
    }
  }
  #push(heap, v) {
    this.cur = heap;
    heap.push(v);
    this.#up(heap.length - 1);
  }
  #pop(heap) {
    this.cur = heap;
    const top = heap[0],
      last = heap.pop();
    if (heap.length) {
      heap[0] = last;
      this.#down();
    }
    return top;
  }
  addNum(num) {
    if (!this.max.length || num <= -this.max[0]) this.#push(this.max, -num);
    else this.#push(this.min, num);

    if (this.max.length > this.min.length + 1)
      this.#push(this.min, -this.#pop(this.max));
    if (this.min.length > this.max.length)
      this.#push(this.max, -this.#pop(this.min));
  }
  findMedian() {
    if (this.max.length === this.min.length)
      return (-this.max[0] + this.min[0]) / 2;
    return -this.max[0];
  }
}