973. K Closest Points to Origin☆

function topKFrequent(words: string[], k: number): string[] {
  // 1) Count every word in one pass.
  const freq = new Map<string, number>();
  for (const w of words) {
    freq.set(w, (freq.get(w) ?? 0) + 1);
  }

  // 2) Size-k MIN-heap. The "smallest" entry is the one we want to
  //    evict first: lower frequency loses; on a tie, the
  //    LEXICOGRAPHICALLY LARGER word loses (so it sinks to the top).
  const worseThan = (a: string, b: string): boolean =>
    freq.get(a)! < freq.get(b)! ||
    (freq.get(a)! === freq.get(b)! && a > b);

  const heap: string[] = []; // binary min-heap kept at <= k entries
  const up = (i: number) => {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (!worseThan(heap[i], heap[p])) break;
      [heap[i], heap[p]] = [heap[p], heap[i]];
      i = p;
    }
  };
  const down = (i: number) => {
    const n = heap.length;
    for (;;) {
      let s = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < n && worseThan(heap[l], heap[s])) s = l;
      if (r < n && worseThan(heap[r], heap[s])) s = r;
      if (s === i) break;
      [heap[i], heap[s]] = [heap[s], heap[i]];
      i = s;
    }
  };

  for (const w of freq.keys()) {
    heap.push(w);
    up(heap.length - 1);
    if (heap.length > k) {        // overflow: drop the worst entry
      [heap[0], heap[heap.length - 1]] = [heap[heap.length - 1], heap[0]];
      heap.pop();
      down(0);
    }
  }

  // 3) Heap holds the k best, worst-first. Pop all, then reverse.
  const res: string[] = [];
  while (heap.length) {
    res.push(heap[0]);
    heap[0] = heap[heap.length - 1];
    heap.pop();
    down(0);
  }
  return res.reverse();
}

class KthLargest {
  private heap: number[] = [];
  private k: number;

  constructor(k: number, nums: number[]) {
    this.k = k;
    for (const n of nums) this.add(n);
  }

  add(val: number): number {
    this._heapPush(val);
    if (this.heap.length > this.k) this._heapPop();
    return this.heap[0];   // min of the k-heap = kth largest overall
  }

  // --- min-heap helpers ---
  private _heapPush(val: number): void {
    this.heap.push(val);
    let i = this.heap.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.heap[parent] <= this.heap[i]) break;
      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
      i = parent;
    }
  }

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

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 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;
}