Binary Heap dan Priority Queue

Kembali ke struktur data hirarkis, terdapat satu struktur binary tree yang bernama binary heap. Suatu binary heap adalah binary tree yang didalamnya tersimpan data dengan cara pengurutan tertentu: dalam binary heap dengan kaidah “minheap” data pada setiap parent dalam tree harus tidak boleh lebih besar dari data pada anak-anaknya. Dengan demikian root dari tree berisi bilangan terkecil dari semua bilangan dalam tree. Dalam binary heap dengan kaidah “maxheap”, parent tidak boleh lebih kecil dari anak-anaknya sehingga root berisi bilangan terbesar dari semua bilangan dalam tree.

Semantara itu, dalam kuliah mengenai struktur hirarkis dibahas definisi complete binary tree. Suatu complete binary tree adalah suatu binary tree yang memiliki bentuk khusus sehingga menjadi satu-satunya binary tree yang dapat direpresentasikan hanya dengan array tanpa kehilangan informasi strukturnya (siapa ayah, siapa anak-akannya, dapat diketahui melalui fungsi antara indeks di dalam array tsb).

Konsep binary heap ini dikombinasikan dengan konsep complete binary tree tersebut menghasilkan suatu struktur priority queue yang memiliki performance O(log n). Tanpa itu, suatu priority queue memerlukan operasi O(n), ie. , dengan sorted array memerlukan enqueue O(n) dequeue O(1) atau unsorted array memerlukan enqueue O(1) dan dequeue O(n). Yang menarik, perbaikan performance dari O(n) menjadi O(log n) hanya pada konsep abstraksinya saja semetara representasinya tetap sama-sama dengan array.

Operasi enqueue (menginsert data ke dalam queue) pada struktur ini bisa mencapai O(log n) dengan suatu proses PercolateUp dan operasi dequeue (meremove data terkecil untuk minheap / data terbesar untuk maxheap) dengan proses PercolateDown. Kedua algoritma ini beriterasi secara worse case antara root dengan leaf tanpa mengganggu node-node lainnya.

Manfaat selain sebagai suatu priority queue, struktur ini mengilhami algoritma sorting yang bernama heapsort yang memiliki performance O(n log n) seanding dengan quicksort dan mergesort. Heapsort mengurutkan data mirip seperti selection-sort namun jika selection-sort melakukan pencarian data minimum secara sikuensial (O(n)) pada data , heapsort hanya melakukan dequeue secara O(log n). Di awal  priority queue yang semula berisi semua data yang tersusun membentuk heap dengan suatu proses heapify yang bersifat O(n log n).

Selain itu, terdapat sejumlah manfaat lainnya yaitu dalam struktur pendukung proses external data sorting.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s