Struktur Data - Heap

Heap dapat dianggap sebagai struktur data pohon sederhana, namun heap biasanya menggunakan salah satu dari dua strategi:

  1. min heap; atau
  2. max heap

Setiap strategi menentukan sifat-sifat pohon dan nilainya. Jika Anda memilih strategi min heap maka setiap ‘parent node’ akan memiliki nilai ≤ daripada ‘children’. Misalnya, node pada root pohon akan memiliki nilai terkecil di pohon. Kebalikannya ‘true’ untuk heap max strategi. Dalam pembahasan kita kali ini kita harus mengasumsikan bahwa heap menggunakan strategi min heap kecuali dinyatakan lain.

Tidak seperti struktur data pohon lainnya, sebuah heap umumnya diimplementasikan sebagai array, bukan serangkaian node yang masing-masing memiliki referensi ke node lain. Simpul secara konseptual sama, namun, memiliki paling banyak dua children. Gambar (a) dibawah berikut menunjukkan bagaimana pohon (bukan struktur data heap) (12 7 6 3 2 9 ) akan direpresentasikan sebagai array. Array pada Gambar tersebut merupakan hasil dari hanya menambahkan nilai dalam mode top-to-bottom, dari kiri ke kanan.

box1

Gambar (a) Array representasi struktur data pohon sederhana

Pada gambar (b) menunjukkan panah ke anak kiri dan kanan langsung dari setiap nilai dalam array.

box2

Gambar (b): Children langsung dari node dalam representasi array dari struktur data pohon

  1. Vector
  2. ArrayList
  3. List

Gambar (a) tidak menjelaskan bagaimana kita menangani penambahan referensi null ke heap. Ini bervariasi dari satu kasus ke kasus lain; kadang-kadang nilai nol dilarang sepenuhnya; dalam kasus lain kita dapat memperlakukan mereka sebagai lebih kecil daripada nilai non-nol, atau memang lebih besar daripada nilai non-nol.

Karena kita menggunakan array, maka memerlukan beberapa cara untuk menghitung indeks parent node, dan children dari suatu simpul. Ekspresi yang diperlukan untuk ini ditetapkan sebagai berikut untuk node pada indeks:

  1. (index - 1)/2 (parent index)
  2. 2 * index + 1 (left child)
  3. 2 * index + 2 (right child)

box3

Pada gambar (a) menunjukkan kalkulasi right child dari 12 (2*0+2) Sedangkan (b) kalkulasi index parent dari 3 ((3-1)/2)

Untuk Insertion atau penyisipan pada heap, kita akan merancang suatu algoritma untuk penyisipan heap sederhana, tetapi kita harus memastikan bahwa urutan heap dipertahankan setelah setiap penyisipan. Umumnya ini adalah operasi pasca-penyisipan. Memasukkan nilai ke free slot berikutnya dalam array sederhana: kita hanya perlu melacak indeks bebas berikutnya dalam array sebagai penghitung, dan menghapusnya setelah setiap penyisipan. Inserting nilai ke dalam heap adalah bagian pertama dari algoritma;

Dalam kasus min-heap ordering, mengharuskan kita untuk menukar nilai-nilai parent dan child jika nilai child adalah < nilai parent. Kita harus melakukan ini untuk setiap subtree yang mengandung nilai yang baru saja kita insert.

box3 box3 box3 box3

Proses diatas mengubah struktur data pohon menjadi pasangan array-nya. Efisiensi waktu proses untuk penyisipan heap adalah O(log n). Running time item dari memverifikasi urutan heap sebagai bagian pertama dari algoritma (penyisipan yang sebenarnya ke dalam array) adalah O(1).

Deletion atau atau penghapusan, Sama halnya dengan penyisipan, penghapusan item memastikan bahwa heap ordering dilakukan diawetkan dimana Algoritme untuk penghapusan memiliki tiga langkah:

  1. Temukan indeks nilai yang akan dihapus
  2. letakkan nilai terakhir di heap pada lokasi indeks item yang akan dihapus
  3. verifikasi heap ordering untuk setiap subtree yang digunakan untuk memasukkan nilai

Gambar berikut menunjukkan Remove algoritma secara visual, menghapus 1 dari heap berisi nilai 1, 3, 9, 12, dan 13. Pada Gambar tersebut Anda dapat mengasumsikan bahwa kita telah menetapkan bahwa backing array dari heap harus memiliki kapasitas awal delapan.

box3 box3 box3

(Menghapus Item dari heap)

Sedangkan Searching pada heap hanya masalah melintasi item dalam array heap secara berurutan, sehingga operasi ini memiliki kompleksitas waktu berjalan O (n). Searching dapat dianggap sebagai salah satu yang menggunakan ‘breadth first traversal’ untuk mengunjungi node dalam heap untuk memeriksa keberadaan item tertentu.