KATA PENGANTAR

Dengan menyebut nama Allah SWT yang maha pengasih lagi maha penyayang, kami panjatkan
puja dan puji syukur atas kehadirat-Nya, yang melimpahkan Rahmat, Inayah, Taufik, serta
Hidayahnya sehingga saya dapat menyelesaikan penyusunan makalah ini dalam bentuk maupun isinya
yang sangat sederhana. Semoga makalah ini dapat dipergunakan sebagai salah satu acuan, petunjuk
maupun pedoman bagi pembaca.

Harapan saya semoga makalah ini membantu menambah pengetahuan dan pengalaman bagi para
pembaca, sehingga saya dapat memperbaiki bentuk maupun isi makalah ini sehingga kedepannya
lebih baik.

Makalah ini saya akui masih banyak kekurangan karena pengalaman yang saya miliki sangat
kurang. Oleh karena itu saya harapkan kepada para pembaca untuk memberikan masukan-masukan
yang bersifat membangun untuk kesempurnaan makalah ini.

Sukorejo, 14 Juli 2019

Penyusun

Struktur Data | Algorithma Heap Sort | Sistem Informasi | Universitas Ibrahimy Sukorejo 1
 DAFTAR ISI

HALAMAN JUDUL

KATA PENGANTAR..............................................................................................1

DAFTAR ISI..........................................................................................................2

PENDAHULUAN...................................................................................................3

PEMBAHASAN....................................................................................................4

Algoritma Heap Sort..............................................................................4

PENUTUP............................................................................................................18

Daftar Pustaka........................................................................................18

Struktur Data | Algorithma Heap Sort | Sistem Informasi | Universitas Ibrahimy Sukorejo 2
 Pendahuluan

Algoritma Heap Sort adalah sebuah metode sorting (pengurutan) angka pada sebuah
array dengan cara menyerupai binary tree, yaitu dengan cara memvisualisasikan sebuah array
menjadi sebuah binary tree yang nantinya pada binary tree tersebut nilai pada masing-masing
index array akan diurutkan. Pada heap sort terdapat 3 bagian yaitu Node, Edge, dan leaf
dimana node itu adalah setiap index yang berada pada array, edge adalah garis yang
menghubungkan tiap node dan leaf adalah setiap node yang tidak memiliki child node (node
turunan). Selain itu juga ada yang bernama root yaitu node awal pada sebuah heap.

Untuk lebih jelasnya, penulis akan memaparkan lebih detail (insyaallah) pada
halaman selanjutnya.

Struktur Data | Algorithma Heap Sort | Sistem Informasi | Universitas Ibrahimy Sukorejo 3
 Pembahasan

Algoritma Heap Sort

Heap sort adalah sebuah metode sorting (pengurutan) angka pada sebuah array dengan
cara menyerupai binary tree, yaitu dengan cara memvisualisasikan sebuah array menjadi
sebuah binary tree yang nantinya pada binary tree tersebut nilai pada masing-masing index
array akan diurutkan. Pada heap sort terdapat 3 bagian yaitu Node, Edge, dan leaf dimana
node itu adalah setiap index yang berada pada array, edge adalah garis yang menghubungkan
tiap node dan leaf adalah setiap node yang tidak memiliki child node (node turunan). Selain
itu juga ada yang bernama root yaitu node awal pada sebuah heap, berikut adalah ilustrasi
dari bagian yang dimiliki oleh heap :

Heap tree terbagi menjadi 2 jenis yaitu Max-Heap dan Min-Heap, dimana max-heap
adalah kondisi heap tree yang memiliki nilai tertinggi berada di node root dan setiap child
node memiliki nilai yang lebih kecil dari nilai yang dimiliki parent nodenya. Sedangkan pada
min-heap adalah kondisi kebalikan dengan max-heap, pada min-heap nilai terkecil berada di
node root dan setiap child node memiliki nilai yang lebih besar dari nilai yang dimiliki parent
nodenya. Pada metode heap sort jenis heap tree yang digunakan adalah Max-Heap.

Dan untuk memvisualisasikan sebuah array menjadi sebuah heap tree adalah dengan cara
mencari node root terlebih dahulu yaitu node pertama node pertama sebuah heap tree adalah
index pertama di array yaitu index 0 akan tetapi pada heap tree node awal berada di posisi 1
berbeda dengan array yang memiliki index awal yaitu index 0. Setelah node root telah
ditemukan maka sekarang tinggal mencari child node dari node root dan child node terbagi
menjadi 2 yaitu left child dan right child dan untuk mencari left child, right child, dan parent
digunakan rumus sebagai berikut :

         Left Child : 2i (Contoh : Left child dari 1 adalah 2 x 1 = 2)

Struktur Data | Algorithma Heap Sort | Sistem Informasi | Universitas Ibrahimy Sukorejo 4
         Right Child : 2i + 1 (Contoh : Right Child dari 1 adalah (2 x 1) + 1 = 3)
         Parent : └ i/2 ┘ (Contoh : Parent dari 3 adalah 3 / 2 = 1 )

NB : Untuk i adalah posisi node yang ingin dicari left/right childnya atau parent nodenya dan
untuk lambing (└ ┘) adalah floor yaitu pembulatan kebawah missal 3 / 2 = 1,5 dibulatkan
kebawah menjadi 1. Berikut adalah contoh cara memvisualisasikan sebuh array menjadi
sebuah heap tree :

Contoh : Kita memiliki sebuah aray A = 4, 1, 3, 2, 16, 9, 10, 14, 8, 7. Dan untuk
memvisualisasikan array tersebut gunakan rumus yang sudah disediakan dan prosesnya akan
terlihat seperti ini :

Dan hasil heap treenya adalah sebagai berikut :   

Struktur Data | Algorithma Heap Sort | Sistem Informasi | Universitas Ibrahimy Sukorejo 5
 Akan tetapi pada max-heap kondisi heap tree adalah node dengan nilai tertinggi adalah root
dan setiap parent node memiliki nilai yang lebih besar dari child nodenya, dan heap tree yang
terbentuk dari array A tidak memenuhi kondisi max-heap oleh karena itu dibutuhkan metode
untuk membuat heap tree tersebut memiliki kondisi max-heap. Dalam metode sorting heap
sort terdapat 2 metode yang digunakan yaitu Build-Max-Heap dan Max-Heapfy, Build-Max-
Heap adalah metode yang digunakan untuk membuat heap tree diatas memenuhi kondisi dari
max-heap, berikut ini adalah ilustrasi penggunaan metode HeapSort, Build-Max-Heap, dan
Max-Heapfy pada sebuah heap tree :

HeapSort(A)
1.    Deklarasi array A
2.    Deklarasi Elemen
3.    Input elemen array A
4.    Input nilai-nilai elemen array A
5.    Build-Max-Heap(A)
6.    For i = Elemen – 1 selama i > 0
7.    Tukar A[i] dengan A[0]
8.    Elemen – 1
9.    Max-Heapfy(A, 1)
10. End for

Dapat dilihat pada algoritma HeapSort terdapat 2 metode yang dipanggil yaitu Build-Max-
heap dan Max-Heapfy, dan algoritma dari Build-Max-heap adalah :

Build-Max-Heap(A)
1.    For i = (Elemen - 1) / 2 selama i ≥ 0
2.    Max-Heapfy(A, i)
3.    End for

Pada metode Build-Max-Heap terdapat for looping yang membagi 2 jumlah elemen, disini
elemen – 1 karena pada array index awal adalah 0 sedangkan pada heap tree adalah 1, lalu
elemen dibagi 2 dan selama i ≥ 0 maka for looping akan terus berajalan. Dan berikut adalah
metode Max-Heapfy :

Max-Heapfy(A, i)
1.    Deklarasi left = (i + 1) * 2 – 1
2.    Deklarasi right = (i + 1) * 2
3.    Deklarasi largest
4.    if(left < elemen dan A[left] > A[i])
5.    largest = left
6.    end if
7.    else
8.    largest = i
9.    end else

Struktur Data | Algorithma Heap Sort | Sistem Informasi | Universitas Ibrahimy Sukorejo 6
10. if(right < elemen dan A[right] > A[i])
11. largest = right
12. end if
13. if(largest != i)
14. Tukar A[i] dengan A[largest]
15. Max-Heapfy(A, i)
16. end if
 

Sebenarnya metode Max-Heapfy digunakan untuk mengkoreksi posisi dari index yang
dipilih apakah posisinya sudah memenuhi kondisi Max-Heap yaitu tiap node parent harus
memiliki nilai yang lebih tinggi dari nilai yang dimiliki child nodenya, dan dengan metode
Max-Heapfy pengaturan posisi node yang memenuhi kondisi Max-Heap dapat dilakukan.
Maka pada metode Build-Max-Heap banyaknya elemen array dibagi menjadi 2 dan hasil
bagianya itu adalah lokasi index awal yang akan diperiksa apakah sudah memenuhi kondisi
Max-Heap atau belum dan proses pemeriksaan dilakukan oleh metode Max-Heapfy. Berikut
adalah ilustrasi penggunakan metode Build-Max-Heap :

Heap tree awal adalah seperti ini :

Karena pada heap tree jumlah node/elemen ada 10 (kalo di array adalah 9) maka jumlah
elemen di bagi 2 (10 / 2 = 5 atau └ 9 / 2 ┘ = 4) maka yang menjadi variabel i adalah 5 (untuk
heap tree) atau 4 (untuk array) maka ilustrasinya adalah sebagai berikut :

Struktur Data | Algorithma Heap Sort | Sistem Informasi | Universitas Ibrahimy Sukorejo 7
Karena node sebagai parent node sudah memiliki nilai lebih besar dari child nodenya (node
10) maka pertukaran posisi tidak terjadi, selanjutnya adalah lanjut ke index 4 :

Disini ternyata nilai yang dimiliki node 4 lebih kecil dari nilai yang dimiliki child nodenya
(node 8 dan 9) maka pertukaran posisi dilakukan dan hasilnya adalah sebagai berikut :

Struktur Data | Algorithma Heap Sort | Sistem Informasi | Universitas Ibrahimy Sukorejo 8
Selanjutnya adalah node 3 :

Disni node 3 memiliki nilai yang lebih kecil dari child nodenya (node 6 dan 7) maka
pertukaran posisi dilakukan antara node 3 dan 7 karena antara node 3, 6, dan 7 node 7 lah
yang memiliki nilai yang paling tinggi. Maka hasilnya adalah sebagai berikut :

Struktur Data | Algorithma Heap Sort | Sistem Informasi | Universitas Ibrahimy Sukorejo 9
  

Selanjutnya adalah node 2 :

Node 2 memiliki nilai yang lebih kecil dari child nodenya (node 4 dan 5) maka pertukaran
posisi dilakukan disini node 5 memiliki nilai yang paling tinggi maka nilai pada index 2
bertukar posisi dengan nilai pada index 5. Maka hasilnya adalah sebagai berikut :

Struktur Data | Algorithma Heap Sort | Sistem Informasi | Universitas Ibrahimy Sukorejo 10
Setelah itu posisi index berubah menjadi pada node 5 dan ternyata disini nilai pada node 5
lebih kecil dari nilai yang berada di child nodenya yaitu node 10 maka perpindahan posisi
kembali dilakukan dan hasilnya terlihat seperti ini :

Selanjutnya posisi index berada di node 1 :

Struktur Data | Algorithma Heap Sort | Sistem Informasi | Universitas Ibrahimy Sukorejo 11
Disini nilai pada index 1 lebih kecil dbandingkan dengan nilai yang dimiliki child nodenya
(node 2 dan 3) maka nilai pada node 1 ditukar dengan nilai pada node 2 karena nilai pada
node 2 adalah nilai tertinggi dari nilai pada 1 dan 3 dan hasilnya adalah :

Setelah pertukaran posisi sekarang posisi i ada di index 2 disini nilai pada index 2 lebih kecil
dibandingkan nila yang dimiliki child nodenya (index 4 dan 5) maka pertukaran posisi
kembali terjadi disini index 4 memiliki nilai tertinggi maka nilai pada indx i ditukar dengan
nilai pada index 4 dan hasilnya adalah sebagai berikut :

Setelah proses tukar posisi selesai maka posisi i adalah di node 4 akan tetapi disini kembali
nilai pada index i lebih kecil dibandingkan dengan nilai yang dimiliki child nodenya (node 9),
maka nilai pada index i ditukar dengan nilai pada index 9 dan hasilnya adalah sebagai
berikut  :

Struktur Data | Algorithma Heap Sort | Sistem Informasi | Universitas Ibrahimy Sukorejo 12
Sampai disini maka proes Build-Max-Heap telah selesai karena masing-masing parent node
memiliki nilai yang lebih besar dari child nodenya, yaitu seperti heap tree berikut :

Setelah proses Build-Max-Heap telah selesai baru lah kita dapat menggunakan metode
HeapSort untuk mengurutkan nilai pada array A. Pada algoritma heapsort setelah melakukan
algoritma Build-Max-Heap nilai pada index terakhir i akan ditukar dengan node 1 atau root
selama i > 0 disini nilai 16 akan ditukar dengan 1 dan jumlah elemen akan dikurangi 1 akan
tetapi setelah perkukaran posisi dilakukan tree heap tidak memenuhi kondisi Max-Heap maka
algoritma Max-Heapfy digunakan dan ilustrasinya adalah sebagai berikut :

Struktur Data | Algorithma Heap Sort | Sistem Informasi | Universitas Ibrahimy Sukorejo 13
Sampai pada tahap ini nilai tertinggi sudah berada di index yang benar index terakhir 10 pada
heap tree dan 9 di array, langkah selanjutnya adalah mengulang cara yang sama dengan for
looping selama i > 0. Berikut adalah ilustrasi lengkapnya :

Struktur Data | Algorithma Heap Sort | Sistem Informasi | Universitas Ibrahimy Sukorejo 14
  

Maka setelah algoritma HeapSort dilakukan nilai-nilai pada array akan terurut dari nilai
terkecil sampai terbesar. A = 1, 2, 3, 4, 7, 8, 9, 10, 14, 16. Dan berikut adalah flowchart untuk
algoritma Heapsort :

Struktur Data | Algorithma Heap Sort | Sistem Informasi | Universitas Ibrahimy Sukorejo 15
Untuk pengimplementasian menggunakan java adalah sebagai berikut:

Struktur Data | Algorithma Heap Sort | Sistem Informasi | Universitas Ibrahimy Sukorejo 16
Struktur Data | Algorithma Heap Sort | Sistem Informasi | Universitas Ibrahimy Sukorejo 17
 Penutup
Daftar Pustaka
http://loserbombti.blogspot.com/2014/07/algoritma-heap-sort.html

Struktur Data | Algorithma Heap Sort | Sistem Informasi | Universitas Ibrahimy Sukorejo 18