// ─────────────────────────────────────────────────────────────────────────────
// HEAPS (PRIORITY QUEUES)
// ─────────────────────────────────────────────────────────────────────────────
// WHAT   : complete binary tree in an array; root is min (or max); O(log n) push/pop, O(1) peek.
// TELL   : "k largest / smallest", "top k", "kth", "merge k sorted", "running median", "schedule by
//          priority", "closest k", "most frequent first", "min rooms".
// SAY    : min-heap / max-heap, priority queue, sift up (bubble up) / sift down (heapify down),
//          heapify in O(n), two-heap technique, k-way merge, comparator.
// BIG-O  : push/pop O(log n), peek O(1), build from array O(n). "Top k" = O(n log k) with heap of size k.
// NOTE   : JS HAS NO BUILT-IN HEAP. Write this class from memory. Indexing: parent (i-1)>>1, children 2i+1, 2i+2.
// ─────────────────────────────────────────────────────────────────────────────
'use strict';
const assert = require('node:assert/strict');

// ── 1. MinHeap with comparator (cmp(a,b) < 0 => a has higher priority); pass (a,b)=>b-a for a MaxHeap
class Heap {
  #a = []; #cmp;
  constructor(cmp = (a, b) => a - b, items = []) { this.#cmp = cmp; for (const x of items) this.push(x); }
  get size() { return this.#a.length; }
  peek() { return this.#a[0]; }
  push(x) {
    this.#a.push(x);
    let i = this.#a.length - 1; // sift up
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.#cmp(this.#a[i], this.#a[p]) >= 0) break;
      [this.#a[i], this.#a[p]] = [this.#a[p], this.#a[i]];
      i = p;
    }
  }
  pop() {
    const a = this.#a, top = a[0], last = a.pop();
    if (a.length) {
      a[0] = last;
      let i = 0; // sift down
      for (;;) {
        const l = 2 * i + 1, r = l + 1;
        let m = i;
        if (l < a.length && this.#cmp(a[l], a[m]) < 0) m = l;
        if (r < a.length && this.#cmp(a[r], a[m]) < 0) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}
// heapify in O(n): sift-down from (n>>1)-1 to 0 instead of n pushes. Not shown; say it exists.
const h = new Heap();
[5, 3, 8, 1].forEach((x) => h.push(x));
assert.deepEqual([h.pop(), h.pop(), h.pop(), h.pop(), h.pop()], [1, 3, 5, 8, undefined]);
const mx = new Heap((a, b) => b - a, [5, 3, 8]);
assert.equal(mx.peek(), 8);
assert.equal(new Heap().size, 0);

// ── 2. Kth largest element  —  min-heap of size k; pop when size > k; root is answer  —  O(n log k) / O(k)
function findKthLargest(nums, k) {
  const hp = new Heap();
  for (const x of nums) { hp.push(x); if (hp.size > k) hp.pop(); }
  return hp.peek();
}
assert.equal(findKthLargest([3, 2, 1, 5, 6, 4], 2), 5);
assert.equal(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4), 4);
assert.equal(findKthLargest([-1], 1), -1);

// ── 3. Top-k frequent elements  —  freq map, min-heap of [count, val] size k  —  O(n log k) / O(n)
function topKFrequent(nums, k) {
  const f = new Map();
  for (const x of nums) f.set(x, (f.get(x) ?? 0) + 1);
  const hp = new Heap((a, b) => a[0] - b[0]);
  for (const e of f) { hp.push([e[1], e[0]]); if (hp.size > k) hp.pop(); }
  const out = [];
  while (hp.size) out.push(hp.pop()[1]);
  return out.reverse(); // most frequent first
}
assert.deepEqual(topKFrequent([1, 1, 1, 2, 2, 3], 2), [1, 2]);
assert.deepEqual(topKFrequent([1], 1), [1]);
assert.deepEqual(topKFrequent([], 2), []);

// ── 4. Merge k sorted arrays  —  heap of [value, arrayIdx, elemIdx]; pop min, push its successor  —  O(N log k) / O(k)
function mergeK(arrays) {
  const hp = new Heap((a, b) => a[0] - b[0]), out = [];
  arrays.forEach((arr, i) => { if (arr.length) hp.push([arr[0], i, 0]); });
  while (hp.size) {
    const [v, i, j] = hp.pop();
    out.push(v);
    if (j + 1 < arrays[i].length) hp.push([arrays[i][j + 1], i, j + 1]);
  }
  return out;
}
assert.deepEqual(mergeK([[1, 4, 5], [1, 3, 4], [2, 6]]), [1, 1, 2, 3, 4, 4, 5, 6]);
assert.deepEqual(mergeK([[], [1]]), [1]);
assert.deepEqual(mergeK([]), []);

// ── 5. Find median from data stream (two heaps)  —  maxHeap = lower half, minHeap = upper half; keep sizes within 1  —  O(log n) add / O(1) median
class MedianFinder {
  #lo = new Heap((a, b) => b - a); #hi = new Heap();
  addNum(x) {
    this.#lo.push(x);
    this.#hi.push(this.#lo.pop()); // ensure every lo <= every hi
    if (this.#hi.size > this.#lo.size) this.#lo.push(this.#hi.pop()); // lo holds the extra when odd
  }
  findMedian() { return this.#lo.size > this.#hi.size ? this.#lo.peek() : (this.#lo.peek() + this.#hi.peek()) / 2; }
}
const mf = new MedianFinder();
mf.addNum(1); mf.addNum(2);
assert.equal(mf.findMedian(), 1.5);
mf.addNum(3);
assert.equal(mf.findMedian(), 2);
mf.addNum(-10);
assert.equal(mf.findMedian(), 1.5);

// ── 6. K closest points to origin  —  max-heap by distance, size k  —  O(n log k) / O(k)
function kClosest(points, k) {
  const d = ([x, y]) => x * x + y * y;
  const hp = new Heap((a, b) => d(b) - d(a));
  for (const p of points) { hp.push(p); if (hp.size > k) hp.pop(); }
  const out = [];
  while (hp.size) out.push(hp.pop());
  return out.sort((a, b) => d(a) - d(b));
}
assert.deepEqual(kClosest([[1, 3], [-2, 2]], 1), [[-2, 2]]);
assert.deepEqual(kClosest([[3, 3], [5, -1], [-2, 4]], 2), [[3, 3], [-2, 4]]);
assert.deepEqual(kClosest([], 1), []);

// ── 7. Task scheduler (greedy, math form)  —  idle slots = (maxFreq-1)*(n+1) + countOfMax; answer = max(len, that)  —  O(n) / O(26)
//        Heap form: pop up to n+1 most frequent per round, decrement, push back. Same answer; math is faster to write.
function leastInterval(tasks, n) {
  const f = new Map();
  for (const t of tasks) f.set(t, (f.get(t) ?? 0) + 1);
  const maxF = Math.max(...f.values());
  const ties = [...f.values()].filter((c) => c === maxF).length;
  return Math.max(tasks.length, (maxF - 1) * (n + 1) + ties);
}
assert.equal(leastInterval(['A', 'A', 'A', 'B', 'B', 'B'], 2), 8);
assert.equal(leastInterval(['A', 'A', 'A', 'B', 'B', 'B'], 0), 6);
assert.equal(leastInterval(['A'], 5), 1);

// ── 8. Meeting rooms II (min rooms) with heap  —  sort by start; min-heap of end times; pop if top <= start  —  O(n log n) / O(n)
function minMeetingRooms(intervals) {
  const ends = new Heap();
  for (const [s, e] of [...intervals].sort((a, b) => a[0] - b[0])) {
    if (ends.size && ends.peek() <= s) ends.pop(); // reuse a room
    ends.push(e);
  }
  return ends.size;
}
assert.equal(minMeetingRooms([[0, 30], [5, 10], [15, 20]]), 2);
assert.equal(minMeetingRooms([[7, 10], [2, 4]]), 1);
assert.equal(minMeetingRooms([]), 0);

// ── 9. Reorganize string (no two adjacent same)  —  max-heap by count; pop most frequent, hold back previous  —  O(n log 26) / O(26)
function reorganizeString(s) {
  const f = new Map();
  for (const c of s) f.set(c, (f.get(c) ?? 0) + 1);
  const hp = new Heap((a, b) => b[0] - a[0], [...f].map(([c, n]) => [n, c]));
  let out = '', prev = null;
  while (hp.size) {
    const [n, c] = hp.pop();
    out += c;
    if (prev) hp.push(prev);
    prev = n - 1 > 0 ? [n - 1, c] : null;
  }
  return out.length === s.length ? out : '';
}
assert.equal(reorganizeString('aab'), 'aba');
assert.equal(reorganizeString('aaab'), '');
assert.equal(reorganizeString('a'), 'a');

// ── 10. Ugly number II (nth with only factors 2,3,5)  —  min-heap + seen set; pop min, push x*2, x*3, x*5  —  O(n log n) / O(n)
function nthUglyNumber(n) {
  const hp = new Heap(undefined, [1]), seen = new Set([1]); // undefined -> default numeric comparator
  let x = 1;
  for (let i = 0; i < n; i++) {
    x = hp.pop();
    for (const m of [2, 3, 5]) if (!seen.has(x * m)) { seen.add(x * m); hp.push(x * m); }
  }
  return x;
}
assert.equal(nthUglyNumber(10), 12);
assert.equal(nthUglyNumber(1), 1);
assert.equal(nthUglyNumber(15), 24);

console.log('ok: algorithms/heaps.js');