Belajar Data Structure - Priority Queue & Binary Heap

#Pendahuluan

Setelah di episode 7 kita memahami hash table — lookup rata-rata O(1) dengan hash function dan collision handling — pada episode ini kita mempelajari priority queue dan binary heap, struktur data di mana akses selalu mengembalikan elemen dengan prioritas tertinggi (atau terendah), bukan yang paling awal dimasukkan seperti queue biasa.

Priority queue bukan hanya konsep teori — ia adalah komponen kritis dari banyak algoritma penting: Dijkstra's shortest path, Huffman coding, task scheduling, dan median streaming. Memahami binary heap sebagai implementasi utama priority queue adalah investasi yang akan membayar berkali-kali di episode selanjutnya.

#Konsep Dasar

#Priority Queue

Priority queue adalah abstraksi di mana setiap elemen memiliki prioritas. Dequeue selalu mengembalikan elemen dengan prioritas tertinggi, bukan yang paling lama dimasukkan.

#Binary Heap

Binary heap adalah implementasi paling umum dari priority queue. Ia adalah complete binary tree yang direpresentasikan sebagai array.

Complete binary tree: semua level terisi penuh kecuali level terakhir, yang terisi dari kiri ke kanan.

#Representasi Array

Untuk node di index i:

• Parent: (i - 1) // 2
• Left child: 2 * i + 1
• Right child: 2 * i + 2

Array:  [1, 3, 5, 7, 9, 8, 6]
Tree:        1
            / \
           3   5
          / \ / \
         7  9 8  6

#Min-Heap vs Max-Heap

• Min-Heap: parent selalu lebih kecil dari children → root adalah minimum
• Max-Heap: parent selalu lebih besar dari children → root adalah maximum

Heap property: untuk setiap node, nilainya harus mempertahankan hubungan (≤ untuk min-heap, ≥ untuk max-heap) dengan children-nya.

#Operasi Binary Heap

#Insert (Bubble Up)

Tambah elemen di akhir array, lalu "bubble up" — bandingkan dengan parent, tukar jika heap property terlanggar, ulangi sampai posisi benar.

Insert dengan bubble up

def insert(heap, value):
    heap.append(value)
    index = len(heap) - 1
    while index > 0:
        parent = (index - 1) // 2
        if heap[index] < heap[parent]:
            heap[index], heap[parent] = heap[parent], heap[index]
            index = parent
        else:
            break

#Extract-Min (Heapify Down)

Ambil root (minimum), pindahkan elemen terakhir ke root, lalu "heapify down" — bandingkan dengan children, tukar dengan yang lebih kecil, ulangi sampai heap property terpenuhi.

Extract-min dengan heapify down

def extract_min(heap):
    if len(heap) == 0:
        raise IndexError("Heap is empty")
    minimum = heap[0]
    heap[0] = heap[-1]
    heap.pop()
    heapify_down(heap, 0)
    return minimum
 
def heapify_down(heap, index):
    smallest = index
    left = 2 * index + 1
    right = 2 * index + 2
 
    if left < len(heap) and heap[left] < heap[smallest]:
        smallest = left
    if right < len(heap) and heap[right] < heap[smallest]:
        smallest = right
 
    if smallest != index:
        heap[index], heap[smallest] = heap[smallest], heap[index]
        heapify_down(heap, smallest)

#Build Heap O(n)

Membangun heap dari array kosong dengan n insert membutuhkan O(n log n). Tetapi jika kalian sudah punya array penuh, bisa diheapify dalam O(n) dengan memulai dari non-leaf nodes dan heapify down ke atas.

#Aplikasi Priority Queue

• Task scheduling: proses dengan prioritas tinggi dijalankan lebih dulu
• Dijkstra's algorithm: selalu proses node dengan jarak terpendek
• Median streaming: gunakan dual heap (min + max)
• Top-K elements: k elemen terbesar/terkecil
• Huffman coding: gabungkan dua node dengan frequensi terkecil

#Perbandingan dengan heapq

Python menyediakan modul heapq yang sudah teroptimasi:

Menggunakan heapq bawaan

import heapq
 
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
 
print(heapq.heappop(heap))
print(heapq.heappop(heap))
print(heapq.heappop(heap))

#Penutup

Inti yang harus dibawa pulang:

• Priority queue = akses elemen dengan prioritas tertinggi/terendah.
• Binary heap = complete binary tree yang direpresentasikan sebagai array.
• Min-heap: root = minimum; max-heap: root = maximum.
• Insert = bubble up O(log n); extract = heapify down O(log n).
• Build heap dari array = O(n).
• Aplikasi: Dijkstra, task scheduling, median streaming, top-K.

Di episode 9 selanjutnya kita akan membahas deque dan circular buffer — double-ended queue dengan O(1) insert/delete di kedua ujung, sliding window maximum menggunakan monotonic deque, serta implementasi circular buffer fixed-size. Ini adalah episode terakhir di Fase 2 sebelum kita masuk ke Trees!