İçeriğe atla
ΣDSA Patterns
Menü
KalıplarProblemlerŞablonlarYol haritasıKaynaklarTekrarlarHakkında
Dil
EnglishTürkçe

Heap ve Top K

Rehber 1 / 6 · Yol 1 / 6

ÖncekiSonraki →

Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Hardheap-top-k

Merge k Sorted Lists

Problem (yeniden ifade)

k adet sıralı bağlı listeyi tek bir sıralı listede birleştir.

Sezgi

Min-heap ile k listenin güncel head’leri arasından her zaman en küçüğünü al.

Yaklaşımlar

Head'lerin min-heap'i

Tested only
Time O(N log k)Space O(k)

Fikir. (val, liste indeksi / düğüm) heap’i; min’i pop et, next’ini push et.

Yürüyüş. [[1,4,5],[1,3,4],[2,6]] → 1→1→2→3→4→4→5→6.

Trade-off. Heap vs böl-ve-yönet birleştirme.

Solution
export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

export function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  const heap: ListNode[] = [];
  const push = (n: ListNode) => {
    heap.push(n);
    heap.sort((a, b) => a.val - b.val);
  };
  for (const h of lists) if (h) push(h);
  const dummy = new ListNode(0);
  let cur = dummy;
  while (heap.length) {
    const n = heap.shift()!;
    cur.next = n;
    cur = n;
    if (n.next) push(n.next);
  }
  return dummy.next;
}

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

export function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  const heap: ListNode[] = [];
  const push = (n: ListNode) => {
    heap.push(n);
    heap.sort((a, b) => a.val - b.val);
  };
  for (const h of lists) if (h) push(h);
  const dummy = new ListNode(0);
  let cur = dummy;
  while (heap.length) {
    const n = heap.shift()!;
    cur.next = n;
    cur = n;
    if (n.next) push(n.next);
  }
  return dummy.next;
}

Şablon bağlantısı

Heap ile k-yönlü birleştirme.

İkili birleştirme

Tested only
Time O(N log k) typical with divide-conquer; O(Nk) if left-foldSpace O(1) extra

Fikir. İki sıralı listeyi tekrar tekrar birleştir. Heap versiyonu k-yönlü için daha temiz; ikili birleştirme merge öğretmek için uygundur.

Trade-off. Mülakatlarda k-yönlü birleştirme netliği için heap tercih edilir.

Solution
export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

function mergeTwo(a: ListNode | null, b: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);
  let cur = dummy;
  while (a && b) {
    if (a.val <= b.val) {
      cur.next = a;
      a = a.next;
    } else {
      cur.next = b;
      b = b.next;
    }
    cur = cur.next;
  }
  cur.next = a ?? b;
  return dummy.next;
}

/** Merge lists left-to-right with two-list merge. */
export function mergeKListsPairwise(lists: Array<ListNode | null>): ListNode | null {
  let acc: ListNode | null = null;
  for (const h of lists) acc = mergeTwo(acc, h);
  return acc;
}

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

function mergeTwo(a: ListNode | null, b: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);
  let cur = dummy;
  while (a && b) {
    if (a.val <= b.val) {
      cur.next = a;
      a = a.next;
    } else {
      cur.next = b;
      b = b.next;
    }
    cur = cur.next;
  }
  cur.next = a ?? b;
  return dummy.next;
}

/** Merge lists left-to-right with two-list merge. */
export function mergeKListsPairwise(lists: Array<ListNode | null>): ListNode | null {
  let acc: ListNode | null = null;
  for (const h of lists) acc = mergeTwo(acc, h);
  return acc;
}

Yansıma