Heapify, Push, dan Pop dari Awal
Implementasikan heapify-up untuk push dan heapify-down untuk pop, lalu bangun heap dari array tak terurut dalam O(n) menggunakan algoritma Floyd.
Heapify, Push, dan Pop dari Awal adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Membangun Kelas MinHeap
Mengimplementasikan tumpukan dari awal menunjukkan penguasaan mekanisme dasarnya dan terkadang ditanyakan dalam wawancara tingkat senior. Sebuah kelas MinHeap membungkus larik dan menyediakan operasi push, pop, peek, dan size. Secara internal, kelas ini mempertahankan properti tumpukan dengan memanggil pengayakan ke atas setelah push dan pengayakan ke bawah setelah pop. Memahami implementasi ini membuat modul heapq Python sepenuhnya transparan.
class MinHeap:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
self._sift_up(len(self._data) - 1)
def pop(self):
if len(self._data) == 1:
return self._data.pop()
min_val = self._data[0]
self._data[0] = self._data.pop() # move last to root
self._sift_down(0)
return min_val
def peek(self):
return self._data[0] if self._data else None
def size(self):
return len(self._data)
def _parent(self, i): return (i - 1) // 2
def _left(self, i): return 2 * i + 1
def _right(self, i): return 2 * i + 2
print('MinHeap class skeleton defined')Mengimplementasikan Pengayakan ke Atas
Pengayakan ke atas membandingkan sebuah simpul dengan parent-nya dan menukarnya ke atas selama properti tumpukan (parent <= child untuk tumpukan minimum) masih dilanggar. Intinya, elemen yang baru disisipkan berada di bagian akhir dan menggelembung ke atas menuju posisi yang benar. Perulangan while berjalan paling banyak floor(log n) kali—setara dengan tinggi pohon. Tetapkan i = parent pada setiap langkah untuk terus bergerak ke atas.
class MinHeap:
def __init__(self):
self._data = []
def _parent(self, i): return (i - 1) // 2
def _left(self, i): return 2 * i + 1
def _right(self, i): return 2 * i + 2
def _sift_up(self, i):
while i > 0:
p = self._parent(i)
if self._data[p] > self._data[i]: # parent > child: swap
self._data[p], self._data[i] = self._data[i], self._data[p]
i = p
else:
break # heap property satisfied
def push(self, val):
self._data.append(val)
self._sift_up(len(self._data) - 1)
h = MinHeap()
for v in [5, 3, 8, 1, 4]:
h.push(v)
print(h._data) # valid min-heapMengimplementasikan Pengayakan ke Bawah
Pengayakan ke bawah mendorong sebuah simpul ke bawah dengan menukarnya berulang kali dengan anak terkecilnya (untuk tumpukan minimum), sampai tidak ada anak yang lebih kecil atau simpul tersebut mencapai daun. Selalu bandingkan dengan kedua anak dan tukar dengan anak yang lebih kecil untuk mempertahankan properti tumpukan. Ingatlah untuk memeriksa bahwa indeks anak berada dalam batas sebelum membandingkan nilai.
def _sift_down(data, i):
n = len(data)
while True:
smallest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and data[l] < data[smallest]:
smallest = l
if r < n and data[r] < data[smallest]:
smallest = r
if smallest == i:
break # already the smallest among i, l, r
data[i], data[smallest] = data[smallest], data[i]
i = smallest
# Test: put a large value at root and sift down
heap = [10, 1, 2, 3, 4, 5, 6]
print('Before sift-down:', heap)
_sift_down(heap, 0)
print('After sift-down:', heap) # 1 should reach top, 10 sinkMenyempurnakan MinHeap dengan Pop
Operasi pop menghapus dan mengembalikan akar (nilai minimum untuk tumpukan minimum). Untuk mempertahankan bentuk pohon biner lengkap, pindahkan elemen terakhir ke posisi akar, lalu lakukan pengayakan ke bawah. Cara ini mencegah terbentuknya celah dalam larik dan menjaga representasinya tetap valid. Kasus khusus: jika hanya tersisa satu elemen, lakukan pop dan kembalikan elemen tersebut secara langsung tanpa pengayakan ke bawah.
class MinHeap:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
i = len(self._data) - 1
while i > 0:
p = (i - 1) // 2
if self._data[p] > self._data[i]:
self._data[p], self._data[i] = self._data[i], self._data[p]
i = p
else: break
def pop(self):
if not self._data: return None
if len(self._data) == 1: return self._data.pop()
result = self._data[0]
self._data[0] = self._data.pop() # last -> root
i, n = 0, len(self._data)
while True:
s, l, r = i, 2*i+1, 2*i+2
if l < n and self._data[l] < self._data[s]: s = l
if r < n and self._data[r] < self._data[s]: s = r
if s == i: break
self._data[i], self._data[s] = self._data[s], self._data[i]
i = s
return result
h = MinHeap()
for v in [5, 3, 8, 1, 4, 2]: h.push(v)
print([h.pop() for _ in range(6)]) # [1,2,3,4,5,8] sortedAlgoritme Heapify Floyd
Algoritme Floyd membangun tumpukan minimum dari larik yang tidak terurut dalam O(n) dengan memanggil pengayakan ke bawah pada setiap simpul non-daun, dimulai dari simpul internal terakhir (n//2 - 1) dan bergerak menuju akar. Daun sudah merupakan tumpukan satu elemen yang valid secara sederhana. Batas time O(n) berasal dari fakta bahwa sebagian besar simpul berada dekat bagian bawah pohon dan hanya perlu melakukan pengayakan ke bawah dalam jarak pendek.
def heapify(arr):
n = len(arr)
# Start from last non-leaf: index n//2 - 1
# Work backward to root (index 0)
for i in range(n // 2 - 1, -1, -1):
# Sift down node at index i
j = i
while True:
s = j
l, r = 2*j+1, 2*j+2
if l < n and arr[l] < arr[s]: s = l
if r < n and arr[r] < arr[s]: s = r
if s == j: break
arr[j], arr[s] = arr[s], arr[j]
j = s
return arr
arr = [9, 7, 5, 3, 1, 8, 2, 4, 6]
print('Before:', arr)
heapify(arr)
print('After (min-heap):', arr) # arr[0] should be 1Mengapa Algoritme Floyd Berkompleksitas O(n)
Bukti O(n): pohon memiliki n/2^(k+1) simpul pada ketinggian k. Setiap simpul pada ketinggian k melakukan paling banyak k pertukaran selama pengayakan ke bawah. Total kerja = jumlah untuk semua ketinggian k: n/2^(k+1) * k. Deret geometris ini konvergen ke O(n). Bandingkan dengan penyisipan satu per satu secara naif: setiap push memerlukan O(log n), sehingga n push memerlukan biaya O(n log n). Algoritme Floyd jelas lebih baik untuk pembangunan secara berkelompok.
import time
import random
# Compare: O(n) heapify vs O(n log n) one-by-one
n = 100000
data = list(range(n, 0, -1)) # reverse sorted = worst case for push
# Method 1: Floyd's O(n)
data1 = data[:]
start = time.time()
for i in range(n // 2 - 1, -1, -1):
j = i
while True:
s = j; l, r = 2*j+1, 2*j+2
if l < n and data1[l] < data1[s]: s = l
if r < n and data1[r] < data1[s]: s = r
if s == j: break
data1[j], data1[s] = data1[s], data1[j]; j = s
print(f'Floyd heapify: {time.time()-start:.4f}s')
# Method 2: One-by-one insertion
import heapq
start = time.time()
heap = []
for x in data: heapq.heappush(heap, x)
print(f'Push one-by-one: {time.time()-start:.4f}s')Push Tumpukan ke dalam Koleksi yang Sudah Ada
heapq.heappushpop dan heapq.heapreplace Python merupakan operasi gabungan yang efisien. heappushpop(heap, item) memasukkan item baru dengan push lalu langsung mengeluarkan nilai terkecil dengan pop—lebih efisien daripada dua pemanggilan terpisah. heapreplace(heap, item) mengeluarkan nilai terkecil dengan pop lalu memasukkan item baru dengan push dalam satu lintasan (item baru harus >= minimum lama agar hasilnya benar). Operasi ini berguna dalam algoritme aliran data untuk elemen dengan peringkat tertinggi sebanyak k.
import heapq
heap = [1, 3, 5, 7, 9]
heapq.heapify(heap)
# heappushpop: push 2, then pop minimum
# More efficient than push + pop separately
result = heapq.heappushpop(heap, 2)
print('heappushpop(2):', result, '| heap:', heap)
# heapreplace: pop minimum, then push new item
# New item does NOT need to be larger (different from heappushpop)
result2 = heapq.heapreplace(heap, 4)
print('heapreplace(4):', result2, '| heap:', heap)
# Use case: maintaining a fixed-size top-k heap
# heappushpop is the standard patternMengimplementasikan MaxHeap dari Awal
MaxHeap membalikkan perbandingan: parent harus lebih besar dari atau sama dengan semua turunannya. Cukup balikkan perbandingan dalam pengayakan ke atas dan pengayakan ke bawah. Alternatifnya, bungkus nilai dalam kelas negasi atau negasikan bilangan bulat seperti yang dilakukan dengan heapq Python. Mengimplementasikannya dari awal menunjukkan bahwa tumpukan minimum dan maksimum memiliki struktur yang sama; satu-satunya perbedaannya adalah operator perbandingan.
class MaxHeap:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
i = len(self._data) - 1
while i > 0:
p = (i - 1) // 2
if self._data[p] < self._data[i]: # FLIP: parent < child = violation
self._data[p], self._data[i] = self._data[i], self._data[p]
i = p
else: break
def pop(self):
if not self._data: return None
if len(self._data) == 1: return self._data.pop()
result = self._data[0]
self._data[0] = self._data.pop()
i, n = 0, len(self._data)
while True:
g = i; l, r = 2*i+1, 2*i+2
if l < n and self._data[l] > self._data[g]: g = l # FLIP
if r < n and self._data[r] > self._data[g]: g = r # FLIP
if g == i: break
self._data[i], self._data[g] = self._data[g], self._data[i]; i = g
return result
h = MaxHeap()
for v in [5, 3, 8, 1, 4, 2]: h.push(v)
print([h.pop() for _ in range(6)]) # [8,5,4,3,2,1]Menghapus Elemen Sembarang dari Tumpukan
Menghapus elemen sembarang (bukan akar) dari tumpukan memerlukan O(log n), tetapi Anda harus mengetahui indeks elemen tersebut. Ganti elemen itu dengan elemen terakhir, hapus elemen terakhir, lalu lakukan pengayakan ke atas atau ke bawah pada elemen pengganti (hanya satu arah yang akan melanggar properti tumpukan). Teknik ini digunakan dalam algoritme Dijkstra dengan penghapusan tertunda dan dalam antrean prioritas yang mendukung operasi penurunan-kunci.
def delete_at_index(heap, i):
n = len(heap)
heap[i] = heap[n - 1]
heap.pop()
if i >= len(heap):
return # deleted the last element
# Try sift-up first
p = (i - 1) // 2
if i > 0 and heap[i] < heap[p]:
while i > 0:
p = (i - 1) // 2
if heap[p] > heap[i]:
heap[p], heap[i] = heap[i], heap[p]; i = p
else: break
else: # sift down
j = i; n2 = len(heap)
while True:
s = j; l, r = 2*j+1, 2*j+2
if l < n2 and heap[l] < heap[s]: s = l
if r < n2 and heap[r] < heap[s]: s = r
if s == j: break
heap[j], heap[s] = heap[s], heap[j]; j = s
heap = [1, 3, 2, 7, 4, 5, 6]
print('Before:', heap)
delete_at_index(heap, 2) # delete element at index 2 (value=2)
print('After:', heap) # 2 removed, heap still validTumpukan untuk Elemen dengan Frekuensi Tertinggi
Elemen dengan Frekuensi Tertinggi sebanyak K (LeetCode #347) menggunakan tumpukan minimum berukuran k. Pertahankan tumpukan minimum yang setiap entrinya berupa (frequency, element). Proses setiap elemen unik: jika tumpukan berisi kurang dari k elemen, lakukan push; jika tidak, apabila frekuensi elemen baru melebihi nilai minimum tumpukan, lakukan pop lalu push. Tumpukan akhir berisi k elemen dengan frekuensi tertinggi dalam time O(n log k).
import heapq
from collections import Counter
def top_k_frequent(nums, k):
count = Counter(nums)
# Min-heap of (frequency, num)
heap = []
for num, freq in count.items():
heapq.heappush(heap, (freq, num))
if len(heap) > k:
heapq.heappop(heap) # remove least frequent
return [num for freq, num in heap]
print(top_k_frequent([1,1,1,2,2,3], 2)) # [1, 2]
print(top_k_frequent([4,4,4,3,3,2,1], 2)) # [4, 3]Penerapan Tumpukan dalam Penjadwalan
Selain pemrograman kompetitif, tumpukan menjadi fondasi sistem penjadwalan di dunia nyata. Penjadwal tugas sistem operasi menggunakan antrean prioritas (tumpukan) untuk selalu menjalankan proses siap dengan prioritas tertinggi. Simulasi berbasis peristiwa memproses peristiwa berdasarkan urutan waktu menggunakan tumpukan minimum dengan waktu peristiwa sebagai kuncinya. Penjadwal paket jaringan memprioritaskan lalu lintas berdasarkan kelas kualitas layanan. Memahami tumpukan memberi Anda model mental untuk semua sistem ini dan secara alami muncul dalam wawancara desain sistem tentang pengantrean dan penjadwalan.
import heapq
# Simple event-driven simulation using a heap
events = [] # (time, event_description)
def schedule(time, event):
heapq.heappush(events, (time, event))
def process_next():
time, event = heapq.heappop(events)
print(f't={time}: {event}')
return time, event
# Schedule events out of order:
schedule(10, 'Send email')
schedule(3, 'Open app')
schedule(7, 'Process request')
schedule(1, 'Start server')
# Process in time order:
while events:
process_next()
# Output: t=1, t=3, t=7, t=10 -- always in time orderPemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Rangkuman Pelajaran
Dalam pelajaran ini Anda mempelajari: MinHeap dan MaxHeap dari nol dengan pergeseran ke atas dan ke bawah, algoritma heapify O(n) milik Floyd dan alasan algoritma ini mengungguli penyisipan satu per satu dengan kompleksitas O(n log n), serta penerapan praktis, termasuk elemen paling sering sejumlah k dan penghapusan berdasarkan indeks. Selanjutnya, kita akan membahas modul heapq Python dan trik tumpukan maksimum.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Heapify, Push, dan Pop dari Awal” gratis?
Ya — teks lengkap “Heapify, Push, dan Pop dari Awal” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Heapify, Push, dan Pop dari Awal”?
Implementasikan heapify-up untuk push dan heapify-down untuk pop, lalu bangun heap dari array tak terurut dalam O(n) menggunakan algoritma Floyd. Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.
Berapa lama pelajaran “Heapify, Push, dan Pop dari Awal” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Sifat Heap dan Representasi Array
- Heapify, Push, dan Pop dari Awal
- heapq Python dan Trik Max-Heap
- Median dari Aliran Data dan Penggabungan K Arah