Sifat Heap dan Representasi Array
Pahami struktur complete-binary-tree yang disimpan sebagai array, turunkan rumus indeks induk/anak, dan visualisasikan operasi sift-up serta sift-down.
Sifat Heap dan Representasi Array adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 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.
Apa Itu Tumpukan?
Tumpukan adalah pohon biner lengkap khusus yang memenuhi properti tumpukan: dalam tumpukan minimum, setiap parent lebih kecil dari atau sama dengan anak-anaknya; dalam tumpukan maksimum, setiap parent lebih besar dari atau sama dengan anak-anaknya. Properti ini menjamin bahwa elemen minimum (atau maksimum) selalu berada di akar, sehingga memungkinkan akses O(1) ke elemen ekstrem. Tumpukan adalah struktur data yang mendasari antrean prioritas.
# Min-heap example:
# 1
# / \
# 3 2
# / \ / \
# 7 4 5 6
# Every parent <= its children
# Root (1) is always the minimum
# Max-heap example:
# 9
# / \
# 7 8
# / \ / \
# 3 4 5 6
# Every parent >= its children
# Root (9) is always the maximum
print('Heap property: parent dominates all descendants')Struktur Pohon Biner Lengkap
Tumpukan disimpan sebagai pohon biner lengkap—semua tingkat terisi penuh kecuali mungkin tingkat terakhir, yang diisi dari kiri ke kanan. Struktur ini memungkinkan representasi larik yang elegan tanpa ruang terbuang dan tanpa penunjuk. Sifat lengkap ini memastikan bahwa tinggi tumpukan selalu floor(log₂ n), sehingga operasi push dan pop terjamin memiliki kompleksitas O(log n).
# Complete binary tree properties:
# 1. All levels filled except possibly the last
# 2. Last level filled from LEFT to right
# 3. For n nodes: height = floor(log2(n))
# NOT complete (last level not left-filled):
# 1
# / \
# 2 3
# \
# 4 <- right child without left sibling
# Valid complete binary tree with 4 nodes:
# 1
# / \
# 2 3
# /
# 4
print('Complete BT: height = floor(log2(n)) always')Representasi Larik Tumpukan
Struktur pohon biner lengkap memungkinkan tumpukan disimpan dalam larik biasa tanpa penunjuk apa pun. Untuk simpul pada indeks i (dengan indeks dimulai dari 0), parent-nya berada pada (i-1) // 2, anak kirinya pada 2i+1, dan anak kanannya pada 2i+2. Aritmetika bilangan bulat ini menggantikan penelusuran menggunakan penunjuk dan membuat tumpukan sangat efisien terhadap cache.
# Array representation (0-indexed):
# Index: 0 1 2 3 4 5 6
# Array: [1, 3, 2, 7, 4, 5, 6]
# Tree: 1 (index 0)
# / \
# 3 2 (indices 1, 2)
# / \ / \
# 7 4 5 6 (indices 3,4,5,6)
# Index formulas (0-based):
def parent(i): return (i - 1) // 2
def left_child(i): return 2 * i + 1
def right_child(i): return 2 * i + 2
heap = [1, 3, 2, 7, 4, 5, 6]
print('Parent of index 3:', parent(3), '-> value', heap[parent(3)])
print('Left child of 1:', left_child(1), '-> value', heap[left_child(1)])Pengayakan ke Atas: Memulihkan Tumpukan Setelah Penyisipan
Pengayakan ke atas (juga disebut penggelembungan ke atas atau heapify ke atas) digunakan setelah menyisipkan elemen baru di akhir larik tumpukan. Bandingkan elemen baru dengan parent-nya; jika properti tumpukan dilanggar, tukar keduanya dan lanjutkan ke atas. Ulangi sampai elemen berada pada posisi yang benar atau mencapai akar. Operasi ini berjalan dalam O(log n) karena tinggi pohon adalah O(log n).
def sift_up(heap, i):
while i > 0:
p = (i - 1) // 2 # parent index
if heap[p] > heap[i]: # min-heap: parent should be smaller
heap[p], heap[i] = heap[i], heap[p]
i = p
else:
break # heap property restored
# Demonstrate: insert 0 into an existing min-heap
heap = [1, 3, 2, 7, 4, 5, 6]
heap.append(0) # add at end
print('Before sift-up:', heap)
sift_up(heap, len(heap) - 1)
print('After sift-up:', heap) # 0 should bubble to rootPengayakan ke Bawah: Memulihkan Tumpukan Setelah Pop
Pengayakan ke bawah (heapify ke bawah) digunakan setelah menghapus akar. Pindahkan elemen terakhir ke akar, lalu dorong elemen tersebut ke bawah dengan menukarnya berulang kali dengan anak yang lebih kecil (untuk tumpukan minimum) sampai properti tumpukan dipulihkan. Operasi ini juga berjalan dalam O(log n). Pengayakan ke atas dan pengayakan ke bawah merupakan blok pembangun semua operasi tumpukan.
def sift_down(heap, i, n):
while True:
smallest = i
l = 2 * i + 1 # left child
r = 2 * i + 2 # right child
if l < n and heap[l] < heap[smallest]:
smallest = l
if r < n and heap[r] < heap[smallest]:
smallest = r
if smallest == i:
break # already in correct position
heap[i], heap[smallest] = heap[smallest], heap[i]
i = smallest
heap = [1, 3, 2, 7, 4, 5, 6]
# Pop min: move last to root, then sift-down
heap[0] = heap[-1]
heap.pop()
print('After move last to root:', heap)
sift_down(heap, 0, len(heap))
print('After sift-down:', heap) # valid min-heap againMembangun Tumpukan dari Larik: Algoritme Floyd
Menyisipkan n elemen satu per satu secara naif memerlukan O(n log n). Algoritme heapify Floyd membangun tumpukan dalam O(n) dengan menerapkan pengayakan ke bawah pada setiap simpul non-daun, dimulai dari simpul non-daun terakhir (indeks n//2 - 1) dan bergerak mundur menuju akar. Simpul daun sudah merupakan tumpukan yang valid secara sederhana, jadi kita hanya perlu memperbaiki simpul internal—itulah sebabnya total pekerjaannya berjumlah O(n), bukan O(n log n).
def build_heap(arr):
n = len(arr)
# Start from last non-leaf node: index n//2 - 1
for i in range(n // 2 - 1, -1, -1):
sift_down(arr, i, n)
return arr
arr = [5, 3, 8, 1, 9, 2, 7]
print('Before:', arr)
build_heap(arr)
print('After (min-heap):', arr) # root should be 1
# Why O(n)? Most nodes are near the bottom (leaves).
# Level k from bottom has ~n/2^k nodes, each needing
# at most k swaps. Sum = n * sum(k/2^k) = O(n).Pengurutan Tumpukan Menggunakan Tumpukan Berbasis Larik
Pengurutan tumpukan berjalan dalam O(n log n) dengan ruang tambahan O(1). Tahap 1: bangun tumpukan maksimum dari larik dalam O(n). Tahap 2: ekstrak nilai maksimum berulang kali dengan menukar akar dengan elemen terakhir yang belum terurut, lalu melakukan pengayakan ke bawah pada tumpukan yang ukurannya telah dikurangi. Setelah n ekstraksi, larik terurut secara menaik. Algoritme di tempat ini menunjukkan bagaimana representasi larik memungkinkan pengurutan tanpa mengalokasikan struktur data terpisah.
def sift_down_max(arr, i, n):
while True:
largest = i
l, r = 2*i+1, 2*i+2
if l < n and arr[l] > arr[largest]: largest = l
if r < n and arr[r] > arr[largest]: largest = r
if largest == i: break
arr[i], arr[largest] = arr[largest], arr[i]
i = largest
def heap_sort(arr):
n = len(arr)
# Build max-heap
for i in range(n // 2 - 1, -1, -1):
sift_down_max(arr, i, n)
# Extract elements one by one
for end in range(n - 1, 0, -1):
arr[0], arr[end] = arr[end], arr[0] # move max to end
sift_down_max(arr, 0, end)
arr = [5, 3, 8, 1, 9, 2, 7]
heap_sort(arr)
print(arr) # [1, 2, 3, 5, 7, 8, 9]Tumpukan Minimum vs Tumpukan Maksimum
Tumpukan minimum memiliki elemen terkecil di akar; operasi pop selalu menghasilkan nilai minimum. Tumpukan maksimum memiliki elemen terbesar di akar; operasi pop selalu menghasilkan nilai maksimum. Keduanya memiliki struktur dan operasi yang sama—hanya arah perbandingannya yang berbeda. Modul heapq Python hanya mengimplementasikan tumpukan minimum, jadi Anda harus menegasikan nilai untuk menyimulasikan tumpukan maksimum.
import heapq
# Python heapq is a MIN-HEAP
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 3)
print('Min-heap min:', heapq.heappop(min_heap)) # 1
# Simulate MAX-HEAP by negating values
max_heap = []
for val in [5, 1, 3]:
heapq.heappush(max_heap, -val) # negate on push
print('Max-heap max:', -heapq.heappop(max_heap)) # 5 (negate on pop)
# For tuples: heapq sorts by first element
print(min_heap, max_heap)Ringkasan Kompleksitas Operasi Tumpukan
Semua operasi tumpukan diturunkan dari pengayakan ke atas dan pengayakan ke bawah, yang keduanya memiliki kompleksitas O(log n). Push: append + pengayakan ke atas = O(log n). Pop: tukar akar dengan elemen terakhir + pengayakan ke bawah = O(log n). Peek: akses indeks 0 = O(1). Bangun tumpukan: O(n) melalui algoritme Floyd. Pengurutan tumpukan: O(n log n). Kompleksitas ini menjadikan tumpukan struktur ideal ketika Anda berulang kali membutuhkan nilai minimum atau maksimum dari koleksi dinamis.
# Heap complexity summary:
# Operation | Time | Space
# --------------|------------|-------
# Push | O(log n) | O(1)
# Pop (min/max) | O(log n) | O(1)
# Peek | O(1) | O(1)
# Build from n | O(n) | O(1) in-place
# Heap sort | O(n log n) | O(1)
# nlargest(k,n) | O(n log k) | O(k)
import heapq
data = [5, 3, 8, 1, 9, 2, 7]
print('Top 3 largest:', heapq.nlargest(3, data)) # [9, 8, 7]
print('Top 3 smallest:', heapq.nsmallest(3, data)) # [1, 2, 3]Pola Praktis Tumpukan dalam Wawancara
Tumpukan menyelesaikan berbagai masalah wawancara dengan pola umum: pertahankan antrean prioritas yang berisi k kandidat saat memproses n elemen dalam aliran data. Elemen dengan frekuensi tertinggi sebanyak k, titik yang paling dekat dengan titik asal sebanyak k, dan penjadwal tugas semuanya menggunakan pola ini. Kenali pola ini ketika Anda melihat: “diberikan aliran n item, pertahankan k yang terbaik”—situasi ini selalu membutuhkan tumpukan berukuran k, dengan total time O(n log k).
import heapq
# Top-K closest points to origin using a max-heap of size k
def k_closest(points, k):
# Use max-heap (negate distance) of size k
heap = []
for x, y in points:
dist = -(x*x + y*y) # negate for max-heap
heapq.heappush(heap, (dist, x, y))
if len(heap) > k:
heapq.heappop(heap) # remove farthest
return [[x, y] for _, x, y in heap]
points = [[1,3], [-2,2], [5,8], [0,1]]
print(k_closest(points, 2)) # 2 closest to originPertukaran antara Tumpukan dan Larik Terurut
Pilih tumpukan ketika Anda hanya memerlukan akses berulang ke nilai minimum atau maksimum dan koleksinya berubah secara dinamis. Pilih larik terurut ketika Anda memerlukan akses acak berdasarkan indeks atau kueri rentang. Kelemahan tumpukan adalah pencarian elemen sembarang memerlukan O(n); kelebihannya adalah penyisipan/penghapusan dalam O(log n) dan akses minimum/maksimum dalam O(1). Larik terurut memerlukan O(n) untuk penyisipan, tetapi pencarian melalui pencarian biner memerlukan O(log n).
# Trade-off comparison:
# Structure | insert | delete_min | search | range_query
# --------------|---------|------------|--------|------------
# Min-heap | O(logn) | O(logn) | O(n) | O(n)
# Sorted array | O(n) | O(n) | O(logn)| O(logn+k)
# BST (balanced)| O(logn) | O(logn) | O(logn)| O(logn+k)
# Hash map | O(1) | O(1) | O(1) | O(n)
# Interview heuristic:
# 'Find minimum repeatedly from dynamic collection' -> HEAP
# 'Binary search or range query' -> sorted array or BST
# 'Fast lookup by key' -> hash map
print('Heap = dynamic collection with priority access')Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini, Anda mempelajari: properti tumpukan dan struktur pohon biner lengkap, representasi larik dengan rumus indeks parent/anak, serta pengayakan ke atas dan pengayakan ke bawah sebagai blok pembangun semua operasi tumpukan, termasuk pembangunan O(n) Floyd. Selanjutnya, kita akan mengimplementasikan heapify dan menjelajahi modul heapq Python.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Sifat Heap dan Representasi Array” gratis?
Ya — teks lengkap “Sifat Heap dan Representasi Array” 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 “Sifat Heap dan Representasi Array”?
Pahami struktur complete-binary-tree yang disimpan sebagai array, turunkan rumus indeks induk/anak, dan visualisasikan operasi sift-up serta sift-down. 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 1 dari 4.
Berapa lama pelajaran “Sifat Heap dan Representasi Array” 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