295. Find Median from Data Stream☆

class MedianFinder {
  // low = max-heap (smaller half), high = min-heap (larger half).
  // We keep |low| === |high|, or |low| === |high| + 1.
  private low: MaxHeap = new MaxHeap();
  private high: MinHeap = new MinHeap();

  addNum(num: number): void {
    // 1. Route by value so low always holds the smaller numbers.
    if (this.low.size === 0 || num <= this.low.peek()) this.low.push(num);
    else this.high.push(num);

    // 2. Rebalance so the two sizes differ by at most one.
    if (this.low.size > this.high.size + 1) {
      this.high.push(this.low.pop());
    } else if (this.high.size > this.low.size) {
      this.low.push(this.high.pop());
    }
  }

  findMedian(): number {
    if (this.low.size === this.high.size) {
      // Even count: average the two middle elements (the heap tops).
      return (this.low.peek() + this.high.peek()) / 2;
    }
    // Odd count: low carries the extra element, so its top IS the median.
    return this.low.peek();
  }
}

class Twitter {
  private static ts = 0;                      // global monotonic timestamp
  private tweets = new Map<number, { tweetId: number; time: number }[]>();
  private following = new Map<number, Set<number>>();

  postTweet(userId: number, tweetId: number): void {
    if (!this.tweets.has(userId)) this.tweets.set(userId, []);
    this.tweets.get(userId)!.push({ tweetId, time: Twitter.ts++ });
  }

  getNewsFeed(userId: number): number[] {
    // Collect latest tweet from every followee (plus self)
    const peers = new Set([userId, ...(this.following.get(userId) ?? [])]);
    // Min-heap keyed by time (max-10 merge via a max-heap simulation)
    // We use a simple sorted merge of per-user pointers for clarity.
    type Cursor = { list: { tweetId: number; time: number }[]; idx: number };
    const cursors: Cursor[] = [];
    for (const uid of peers) {
      const list = this.tweets.get(uid) ?? [];
      if (list.length > 0) cursors.push({ list, idx: list.length - 1 });
    }

    const result: number[] = [];
    while (result.length < 10 && cursors.length > 0) {
      // pick the cursor with the largest time (max-heap by time)
      let best = 0;
      for (let i = 1; i < cursors.length; i++) {
        if (cursors[i].list[cursors[i].idx].time >
            cursors[best].list[cursors[best].idx].time) {
          best = i;
        }
      }
      const cur = cursors[best];
      result.push(cur.list[cur.idx].tweetId);
      if (cur.idx === 0) {
        cursors.splice(best, 1);   // exhausted this user's list
      } else {
        cur.idx--;
      }
    }
    return result;
  }

  follow(followerId: number, followeeId: number): void {
    if (!this.following.has(followerId)) this.following.set(followerId, new Set());
    this.following.get(followerId)!.add(followeeId);
  }

  unfollow(followerId: number, followeeId: number): void {
    this.following.get(followerId)?.delete(followeeId);
  }
}

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

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