215. Kth Largest Element in an Array☆

function kClosest(points: number[][], k: number): number[][] {
  // Max-heap stored as an array: root holds the FARTHEST point among our k best.
  const heap: number[][] = [];

  const dist2 = (p: number[]) => p[0] * p[0] + p[1] * p[1];

  const swap = (i: number, j: number) => {
    [heap[i], heap[j]] = [heap[j], heap[i]];
  };

  const siftUp = (i: number) => {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (dist2(heap[parent]) < dist2(heap[i])) {
        swap(parent, i);
        i = parent;
      } else break;
    }
  };

  const siftDown = (i: number, size: number) => {
    while (true) {
      let largest = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < size && dist2(heap[l]) > dist2(heap[largest])) largest = l;
      if (r < size && dist2(heap[r]) > dist2(heap[largest])) largest = r;
      if (largest === i) break;
      swap(i, largest);
      i = largest;
    }
  };

  for (const p of points) {
    heap.push(p);
    siftUp(heap.length - 1);

    if (heap.length > k) {
      // Root is the farthest; replace it with the last element and sift down.
      heap[0] = heap.pop()!;
      siftDown(0, heap.length);
    }
  }

  return heap;
}

type Building = [left: number, right: number, height: number];
type KeyPoint = [x: number, height: number];

// A tiny max-heap of heights with lazy deletion (no decrease-key needed).
class MaxHeap {
  private a: number[] = [];
  private toDelete = new Map<number, number>(); // height -> pending removals

  push(h: number): void {
    this.a.push(h);
    let i = this.a.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.a[parent] >= this.a[i]) break;
      [this.a[parent], this.a[i]] = [this.a[i], this.a[parent]];
      i = parent;
    }
  }

  // Mark a height for removal; it is purged once it reaches the top.
  remove(h: number): void {
    this.toDelete.set(h, (this.toDelete.get(h) ?? 0) + 1);
  }

  // Lazily discard stale tops, then report the live max (0 = ground).
  top(): number {
    while (this.a.length > 0) {
      const h = this.a[0];
      const pending = this.toDelete.get(h) ?? 0;
      if (pending === 0) return h;
      if (pending === 1) this.toDelete.delete(h);
      else this.toDelete.set(h, pending - 1);
      this.popRoot();
    }
    return 0;
  }

  private popRoot(): void {
    const last = this.a.pop()!;
    if (this.a.length === 0) return;
    this.a[0] = last;
    let i = 0;
    const n = this.a.length;
    for (;;) {
      const l = 2 * i + 1;
      const r = 2 * i + 2;
      let big = i;
      if (l < n && this.a[l] > this.a[big]) big = l;
      if (r < n && this.a[r] > this.a[big]) big = r;
      if (big === i) break;
      [this.a[big], this.a[i]] = [this.a[i], this.a[big]];
      i = big;
    }
  }
}

function getSkyline(buildings: Building[]): KeyPoint[] {
  // Build sweep events: a start lowers x first, ties broken to add tall first.
  const events: Array<[x: number, h: number]> = [];
  for (const [l, r, h] of buildings) {
    events.push([l, -h]); // start: negative height marks an "add"
    events.push([r, h]);  // end: positive height marks a "remove"
  }
  // Sort by x; at equal x, process by signed height so adds beat removes and
  // a taller start is handled before a shorter one.
  events.sort((a, b) => (a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]));

  const result: KeyPoint[] = [];
  const heap = new MaxHeap();
  let prevMax = 0; // current skyline height to the left of this x

  for (const [x, signedH] of events) {
    if (signedH < 0) heap.push(-signedH); // a building begins
    else heap.remove(signedH);            // a building ends

    const curMax = heap.top();
    if (curMax !== prevMax) {
      // The running max changed here -> this x is a key point.
      result.push([x, curMax]);
      prevMax = curMax;
    }
  }

  return result;
}

function lastStoneWeight(stones: number[]): number {
  // Max-heap (simulated with a max-first comparator via a custom MinHeap inverted).
  // Here we implement a simple binary max-heap inline for clarity.
  const heap: number[] = [];

  function push(val: number): void {
    heap.push(val);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p] >= heap[i]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  }

  function pop(): number {
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let max = i;
        if (l < heap.length && heap[l] > heap[max]) max = l;
        if (r < heap.length && heap[r] > heap[max]) max = r;
        if (max === i) break;
        [heap[i], heap[max]] = [heap[max], heap[i]];
        i = max;
      }
    }
    return top;
  }

  for (const s of stones) push(s);

  while (heap.length > 1) {
    const y = pop(); // heaviest
    const x = pop(); // second heaviest
    if (y !== x) push(y - x); // leftover fragment
  }

  return heap.length === 0 ? 0 : heap[0];
}

function findKthLargest(nums: number[], k: number): number {
  // Min-heap of size k — the root is always the kth largest seen so far.
  const heap: number[] = [];

  function push(val: number): void {
    heap.push(val);
    let i = heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (heap[p] > heap[i]) { [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; }
      else break;
    }
  }

  function pop(): number {
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let s = i;
        if (l < heap.length && heap[l] < heap[s]) s = l;
        if (r < heap.length && heap[r] < heap[s]) s = r;
        if (s === i) break;
        [heap[i], heap[s]] = [heap[s], heap[i]]; i = s;
      }
    }
    return top;
  }

  for (const n of nums) {
    push(n);                          // add every element
    if (heap.length > k) pop();       // evict the minimum when over-full
  }
  return heap[0];                     // root = kth largest
}