Sorting, Binary Search & Heap

Kenapa ini penting

Tiga alat ini menjawab pertanyaan yang sangat sering muncul: "bagaimana mengurutkan?", "bagaimana mencari dengan cepat di data terurut?", dan "bagaimana mendapatkan k elemen terbesar/terkecil tanpa mengurutkan semuanya?". Di dunia nyata, kamu memakai ketiganya: mengurutkan tabel di dashboard, mencari versi pertama yang membawa bug dengan git bisect (itu binary search!), dan menampilkan "top 10 produk terlaris" dari jutaan transaksi (itu heap).

Ada satu masalah khusus untuk pengguna JavaScript: JS tidak punya heap atau priority queue bawaan. Python punya heapq dan Java punya PriorityQueue, tapi kamu harus menulis sendiri. Interviewer biasanya mengizinkan kamu berkata "assume I have a min-heap with push and pop", tapi tidak selalu. Karena itu kamu wajib bisa menulis heap sendiri dalam 5-10 menit tanpa melihat catatan.

Analogi heap: antrean UGD rumah sakit. Pasien tidak dilayani berdasarkan siapa yang datang duluan, tapi siapa yang paling darurat. Setiap ada pasien baru, perawat cukup menaruhnya di posisi yang tepat relatif terhadap yang lain, tanpa mengurutkan ulang seluruh ruang tunggu.

Konsep inti

Sorting di JavaScript

• arr.sort() tanpa comparator mengurutkan sebagai string: [10, 9, 1, 100].sort() menghasilkan [1, 10, 100, 9]. Selalu pakai (a, b) => a - b untuk angka.
• sort mengubah array asli (mutating). toSorted (ES2023) mengembalikan salinan; aman dipakai di Node 20+ dan browser modern.
• Sejak ES2019 spesifikasi mewajibkan sort stabil: elemen dengan kunci sama mempertahankan urutan aslinya.
• Kompleksitas: O(n log n). Kalau solusimu mengurutkan, solusimu paling cepat O(n log n).

Kamu jarang diminta menulis algoritma sort dari nol, tapi merge sort layak dikuasai karena idenya (bagi dua, selesaikan, gabungkan) muncul di banyak soal lain.

Binary search: tiga template

Binary search terkenal mudah dijelaskan tapi gampang salah di detail. Gunakan template yang konsisten:

Template ketiga yang paling sering membuat kandidat terkesan: kamu tidak mencari di array, tapi di rentang jawaban. Syaratnya: ada fungsi feasible(x) yang monoton (kalau x layak, semua yang lebih besar juga layak). Contoh: Koko eating bananas, kapasitas minimum kapal, waktu minimum.

Heap

Binary heap adalah binary tree lengkap yang disimpan di array. Untuk indeks i: induk di (i - 1) >> 1, anak kiri 2i + 1, anak kanan 2i + 2. Di min-heap, setiap induk ≤ anaknya, jadi minimum selalu di data[0].

Pola top-k: untuk k terbesar, pakai min-heap berukuran k. Setiap elemen baru di-push; kalau ukuran melebihi k, pop yang terkecil. Di akhir, heap berisi k terbesar dan peek adalah yang ke-k. Kompleksitas O(n log k), lebih baik dari sort O(n log n) kalau k jauh lebih kecil dari n.

Contoh percakapan interview: kalau JS tidak punya heap

Interviewer: "Find the k most frequent elements."

Candidate: "I'll count frequencies with a hash map first, which is O(n). Then I need the top k. Sorting all unique values would be O(m log m), where m is the number of unique values. A min-heap of size k gives O(m log k), which is better when k is small. JavaScript doesn't have a built-in priority queue. Would you like me to implement one, or can I assume a heap with push and pop?"

Interviewer: "Assume it exists for now. If we have time, implement it."

Candidate: "Great. I'll write the main logic first, then come back to the heap."

Pertanyaan "should I implement it or can I assume it?" adalah langkah cerdas: kamu menunjukkan bahwa kamu tahu cara menulisnya, sambil menghemat waktu untuk bagian yang paling penting. Ada juga alternatif O(n) yang bisa kamu sebut untuk top-k frequent: bucket sort berdasarkan frekuensi (array berukuran n+1, indeks = frekuensi). Menyebut dua pendekatan beserta trade-off-nya adalah poin plus, meskipun kamu hanya menulis salah satunya.

Untuk binary search, kalimat yang perlu kamu latih: "My invariant is that the answer is always within lo and hi. Each step cuts the range in half, so it's O(log n)." Kalau kamu bisa menyatakan invariant, kamu juga bisa membuktikan loop-mu berhenti dan tidak melewatkan jawaban.

Contoh kode

// Jebakan sort bawaan JS: default membandingkan sebagai STRING
console.log([10, 9, 1, 100].sort(), [10, 9, 1, 100].sort((a, b) => a - b));
// → [ 1, 10, 100, 9 ] [ 1, 9, 10, 100 ]

// Sort objek dengan beberapa kunci: umur turun, lalu nama naik
const people = [{ n: 'Budi', age: 30 }, { n: 'Ani', age: 25 }, { n: 'Cici', age: 30 }];
console.log(people.toSorted((a, b) => b.age - a.age || a.n.localeCompare(b.n)).map(p => p.n).join(','));
// → Budi,Cici,Ani

// Merge sort O(n log n)
function mergeSort(a) {
  if (a.length <= 1) return a;
  const mid = a.length >> 1, L = mergeSort(a.slice(0, mid)), R = mergeSort(a.slice(mid));
  const out = []; let i = 0, j = 0;
  while (i < L.length && j < R.length) out.push(L[i] <= R[j] ? L[i++] : R[j++]);   // <= menjaga stabilitas
  return out.concat(L.slice(i), R.slice(j));
}
console.log(mergeSort([5, 2, 9, 1, 5, 6]), mergeSort([]), mergeSort([1]));
// → [ 1, 2, 5, 5, 6, 9 ] [] [ 1 ]

// Template 1: cari nilai persis
function binarySearch(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1; else hi = mid - 1;
  }
  return -1;
}
console.log(binarySearch([-1, 0, 3, 5, 9, 12], 9), binarySearch([-1, 0, 3, 5, 9, 12], 2), binarySearch([], 1));
// → 4 -1 -1

// Template 2: lower bound = indeks pertama dengan nums[i] >= target
function lowerBound(nums, target) {
  let lo = 0, hi = nums.length;          // hi eksklusif
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] < target) lo = mid + 1; else hi = mid;
  }
  return lo;
}
console.log(lowerBound([1, 2, 2, 2, 5], 2), lowerBound([1, 2, 2, 2, 5], 3), lowerBound([1, 2, 2, 2, 5], 9));
// → 1 4 5

// Template 3: binary search on answer, Koko eating bananas
function minEatingSpeed(piles, h) {
  const hoursAt = k => piles.reduce((s, p) => s + Math.ceil(p / k), 0);
  let lo = 1, hi = Math.max(...piles);
  while (lo < hi) { const mid = (lo + hi) >> 1; if (hoursAt(mid) <= h) hi = mid; else lo = mid + 1; }
  return lo;
}
console.log(minEatingSpeed([3, 6, 7, 11], 8), minEatingSpeed([30, 11, 23, 4, 20], 5), minEatingSpeed([30, 11, 23, 4, 20], 6));
// → 4 30 23

// Min-heap buatan sendiri (JS tidak punya heap/priority queue bawaan)
class MinHeap {
  constructor(compare = (a, b) => a - b) { this.data = []; this.compare = compare; }
  get size() { return this.data.length; }
  peek() { return this.data[0]; }
  push(x) {
    const d = this.data; d.push(x); let i = d.length - 1;
    while (i > 0) {                                   // sift up
      const p = (i - 1) >> 1;
      if (this.compare(d[i], d[p]) >= 0) break;
      [d[i], d[p]] = [d[p], d[i]]; i = p;
    }
  }
  pop() {
    const d = this.data; if (!d.length) return undefined;
    const top = d[0], last = d.pop();
    if (d.length) {
      d[0] = last; let i = 0;
      while (true) {                                  // sift down
        const l = 2 * i + 1, r = l + 1; let s = i;
        if (l < d.length && this.compare(d[l], d[s]) < 0) s = l;
        if (r < d.length && this.compare(d[r], d[s]) < 0) s = r;
        if (s === i) break;
        [d[i], d[s]] = [d[s], d[i]]; i = s;
      }
    }
    return top;
  }
}
const h = new MinHeap(); for (const x of [5, 3, 8, 1, 9, 2]) h.push(x);
const drained = []; while (h.size) drained.push(h.pop());
console.log(drained);
// → [ 1, 2, 3, 5, 8, 9 ]

// Kth largest: simpan heap ukuran k -> O(n log k)
function findKthLargest(nums, k) {
  const heap = new MinHeap();
  for (const n of nums) { heap.push(n); if (heap.size > k) heap.pop(); }
  return heap.peek();
}
console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2), findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4), findKthLargest([7], 1));
// → 5 4 7

// Top K frequent elements
function topKFrequent(nums, k) {
  const freq = new Map(); for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1);
  const heap = new MinHeap((a, b) => a[1] - b[1]);       // [nilai, frekuensi]
  for (const entry of freq) { heap.push(entry); if (heap.size > k) heap.pop(); }
  const out = []; while (heap.size) out.push(heap.pop()[0]);
  return out.reverse();                                   // paling sering duluan
}
console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2), topKFrequent([1], 1), topKFrequent([4, 4, 5, 5, 5, 6], 1));
// → [ 1, 2 ] [ 1 ] [ 5 ]

// Uji acak: bandingkan heap & lower bound dengan cara "bodoh" yang pasti benar
let ok = true;
for (let t = 0; t < 500; t++) {
  const arr = Array.from({ length: Math.floor(Math.random() * 30) }, () => Math.floor(Math.random() * 50) - 25);
  const hh = new MinHeap(); arr.forEach(x => hh.push(x));
  const out = []; while (hh.size) out.push(hh.pop());
  if (JSON.stringify(out) !== JSON.stringify(arr.toSorted((a, b) => a - b))) ok = false;
  const sorted = arr.toSorted((a, b) => a - b), target = Math.floor(Math.random() * 50) - 25;
  const expected = sorted.findIndex(x => x >= target);
  if (lowerBound(sorted, target) !== (expected === -1 ? sorted.length : expected)) ok = false;
}
console.log('uji acak 500 kasus:', ok ? 'semua lolos' : 'ADA YANG GAGAL');
// → uji acak 500 kasus: semua lolos

Blok terakhir adalah teknik randomized testing (kadang disebut stress test): bandingkan implementasi cepat dengan implementasi lambat yang jelas benar, pada ratusan input acak. Tidak akan kamu tulis di interview 45 menit, tapi sangat berguna saat latihan untuk memastikan heap-mu memang benar sebelum kamu menghafalnya.

Kesalahan umum

1. sort() tanpa comparator untuk angka. Hasilnya urutan string. Cara benar: (a, b) => a - b.
2. Infinite loop di binary search karena memakai lo < hi dengan lo = mid. Cara benar: pilih satu template dan patuhi pasangan kondisi/update-nya.
3. Memakai max-heap untuk k terbesar. Bisa, tapi O(n log n) karena seluruh elemen disimpan. Cara benar: min-heap berukuran k.
4. Lupa kasus heap kosong di pop. Cara benar: kembalikan undefined atau lempar error yang jelas.
5. Mengurutkan input milik pemanggil tanpa bertanya. sort bersifat mutating. Cara benar: toSorted atau [...arr].sort(...), atau tanyakan apakah boleh memodifikasi.

Latihan

1. Mudah, Search Insert Position: indeks tempat target berada atau seharusnya disisipkan di array terurut.
2. Sedang, Search in Rotated Sorted Array: array terurut yang diputar (misalnya [4,5,6,7,0,1,2]), cari indeks target dalam O(log n).
3. Menantang, K Closest Points to Origin: kembalikan k titik terdekat ke (0, 0) memakai heap.

// 1. Search insert position adalah lower bound
console.log(lowerBound([1, 3, 5, 6], 5), lowerBound([1, 3, 5, 6], 2), lowerBound([1, 3, 5, 6], 7), lowerBound([1, 3, 5, 6], 0));
// → 2 1 4 0

// 2. Salah satu sisi mid pasti terurut; cek apakah target ada di sisi itu
function searchRotated(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] === target) return mid;
    if (nums[lo] <= nums[mid]) {                        // sisi kiri terurut
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1; else lo = mid + 1;
    } else {                                            // sisi kanan terurut
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; else hi = mid - 1;
    }
  }
  return -1;
}
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 0), searchRotated([4, 5, 6, 7, 0, 1, 2], 3), searchRotated([1], 0), searchRotated([3, 1], 1));
// → 4 -1 -1 1

// 3. Max-heap berdasarkan jarak (comparator dibalik), ukuran k
function kClosest(points, k) {
  const dist = ([x, y]) => x * x + y * y;            // tidak perlu sqrt untuk membandingkan
  const heap = new MinHeap((a, b) => dist(b) - dist(a));
  for (const p of points) { heap.push(p); if (heap.size > k) heap.pop(); }
  return heap.data.toSorted((a, b) => dist(a) - dist(b));
}
console.log(JSON.stringify(kClosest([[1, 3], [-2, 2]], 1)), JSON.stringify(kClosest([[3, 3], [5, -1], [-2, 4]], 2)));
// → [[-2,2]] [[3,3],[-2,4]]

Ringkasan

• sort default JS membandingkan string; pakai comparator dan toSorted untuk menghindari mutasi.
• Kuasai tiga template binary search: nilai persis, lower bound, dan binary search on answer.
• JS tidak punya heap bawaan; latih menulis min-heap berbasis array dengan sift up/sift down.
• Top-k terbesar = min-heap berukuran k, O(n log k).
• Uji struktur data buatanmu dengan randomized testing melawan solusi brute force.