Heap Sort

            Heap adalah struktur data yang berbentuk pohon yang memenuhi sifat-sifat heap yaitu jika B adalah anak dari A, maka nilai yang tersimpan di simpul A lebih besar atau sama dengan nilai yang tersimpan di simpul B. Hal ini mengakibatkan elemen dengan nilai terbesar selalu berada pada posisi akar, dan heap ini disebut max heap. (Bila perbandingannya diterbalikkan yaitu elemen terkecilnya selalu berada di simpul akar, heap ini disebut adalah min heap). Karena itulah, heap biasa dipakai untuk mengimplementasikan priority queue

Operasi-operasi yang digunakan untuk heap adalah

• Delete-max atau delete-min: menghapus simpul akar dari sebuah max atau min heap.

• Increase-key atau decrease-key: mengubah nilai yang tersimpan di suatu simpul.

• Insert: menambahkan sebuah nilai ke dalam heap.

• Merge: menggabungkan dua heap untuk membentuk sebuah heap baru yang berisi semua elemen pembentuk heap tersebut.

Heap Sort

            HeapSort adalah algoritma pengurutan data berdasarkan perbandingan, dan termasuk golongan selection sort. Walaupun lebih lambat daripada quick sort pada kebanyakan mesin , tetapi heap sort mempunyai keunggulan yaitu kompleksitas algoritma pada kasus terburuk adalah n log n.

            Algoritma pengurutan heap sort ini mengurutkan isi suatu larik masukan dengan memandang larik masukan sebagai suatu Complete Binary Tree (CBT). Setelah itu Complete Binary Tree (CBT) ini dapat dikonversi menjadi suatu heap tree. Setelah itu Complete Binary Tree (CBT) diubah menjadi suatu priority queue.

            Algoritma pengurutan heap dimulai dari membangun sebuah heap dari kumpulan data yang ingin diurutkan, dan kemudian menghapus data yang mempunyai nilai tertinggi dan menempatkan dalam akhir dari larik yang telah terurut. Setelah memindahkan data dengan nilai terbesar, proses berikutnya adalah membangun ulang heap dan memindahkan nilai terbesar pada heap tersebut dan menempatkannya dalam tempat terakhir pada larik terurut yang belum diisi data lain. Proses ini berulang sampai tidak ada lagi data yang tersisa dalam heap dan larik yang terurut penuh. Dalam implementasinya kita membutuhkan dua larik – satu untuk menyimpan heap dan satu lagi untuk menyimpan data yang sudah terurut.
Tetapi untuk optimasi memori, kita dapat menggunakan hanya satu larik saja.
Yaitu dengan cara menukar isi akar dengan elemen terakhir dalam heap tree.
Jika memori tidak menjadi masalah maka dapat tetap menggunakan dua larik yaitu larik masukan dan larik hasil.

Algoritma Untuk Heap Sort

Berikut merupakan algoritma dari heap sort : 

1. Representasikan Heap dengan n elemen dalam sebuah array A[n]

2.      Elemen root tempatkan pada A[1]

3.      Elemen A[2i] adalah node kiri dibawah A[i]

4.      Elemen A[2i+1] adalah node kanan dibawah A[i]

5.      Contoh: array A=[16  14  10  8  7  9  3  2  4  1]  mewakili binary-heap sbb:

6.      Ambil nilai root (terbesar) A[1..n-1] dan pertukarkan dengan elemen terakhir dalam array, A[n]

7.      Bentuk Heap dari (n-1) elemen, dari A[1] hingga A[n-1]

8.      Ulangi langkah 6 dimana indeks terakhir berkurang setiap langkah.

Contoh Heap Sort

Terdapat data 16, 14, 10, 8, 7, 9, 2, 4, 1. Data-data tersebut dimasukkan dalam tree secara langsung dari atas ke bawah dan dari kiri ke kanan.

Selanjutnya dilakukan heap sort seperti pada gambar berikut :

Perbandingan Heap Sort Dengan Algoritma Pengurutan Lain

            Heapsort hampir setara dengan quick sort, algoritma pengurutan data lain berdasarkan perbandingan yang sangat efisien. Quick sort sedikit lebih cepat, karena cache dan faktor-faktor lain, tetapi pada kasus terburuk kompleksitasnya O(n), yang sangat lambat untuk data yang berukuran sangat besar. Lalu karena heap sort memiliki (N log N) maka sistem yang memerlukan pengamanan yang ketat biasa memakai heap sort sebagai algoritma pengurutannya. Heap sort juga sering dibandingkan dengan merge sort, yang mempunyaikompleksitas algoritma yang sama, tetapi kompleksitas ruang nya (n) yang lebih besar dari heap sort. Heap sort juga lebih cepat pada mesin dengan cache data yang kecil atau lambat

Kompresi Half Byte

Metode kompresi Half Byte merupakan suatu metode kompresi dengan prosesnya adalah memanfaatkan bit sebelah kiri yang sering sama secara berurutan. Misalnya pada suatu file yang berisi data teks bertuliskan ”bilangan”, dalam heksadesimal akan diterjemahkan pada tabel berikut:

Tabel Konversi Heksadesimal

Karakter	Heksadesimal
b	62
i	69
l	6c
a	61
n	6e
g	67
a	61
n	6e

Jika diperhatikan karakter-karakter tersebut memiliki bit sebelah kiri yang sama yaitu ’6’. Gejala seperti inilah yang dimanfaatkan oleh metode kompresi Half Byte.

Saat karakter yang bit kirinya sama secara berderet, maka algoritma ini mengkompres data tersebut diawali dengan ”bit penanda” kemudian bit pertama dari deretan yang sama diikuti dengan pasangan bit kanan dari deretan tersebut dan ditutup dengan bit penanda.

Bit penanda (marker bit, dalam penelitian ini disingkat ‘mb’), berupa suatu byte yang boleh dipilih secara acak asalkan digunakan secara konsisten pada seluruh bit penanda pemampatan. Bit penanda disini berfungsi penanda bahwa karakter selanjutnya adalah karakter pemampatan atau akhir pemampatan. Dalam penelitian ini, penentuan bit penanda dilakukan dengan mencari frekuensi nilai warna yang paling sedikit yang terdapat dalam sebuah citra.

 

Deretan data sebelah kiri merupakan deretan data pada file asli, sedangkan deretan data sebelah kanan merupakan deretan data hasil pemampatan dengan metode Half Byte.

Setelah data nilai dijadikan array 1 dimensi dan telah dirubah menjadi bilangan biner, maka langkah proses kompresi Half Byte dapat dilakukan. Langkah awal ialah membaca data apakah terdapat deretan data yang bit kirinya sama secara berurutan sebanyak tujuh data atau lebih, jika memenuhi lakukan pemampatan. Kemudian berikan bit penanda pada file pemampatan.

 Selanjutnya tambahkan bit kiri data pertama dari file asli dan gabungkan bit kanan karakter yang sama ke file pemampatan. Lalu tutup dengan bit penanda pada file pemampatan.

Contoh kompresi Half Byte dalam bentuk tabel disajikan dalam tabel 3.2, untuk menyederhanakannya maka penulis memproses langsung data bilangan heksadesimal dengan bit penanda ‘ff’. Dari tabel 3.2 data asli berukuran 30 byte dan data hasil kompresi berukuran 25 byte. Dengan demikian proses telah berhasil mengkompresi data sebanyak 5 byte.

Dalam kompresi Half Byte ada beberapa ketentuan selain yang telah ditunjukkan pada tabel 3.2, antara lain (ditunjukkan pada gambar 3.7, 3.8, dan 3.9) :

Ø Bila pada file asli ditemukan nilai yang sama dengan bit penanda, maka dalam file terkompresi hasus dituliskan nilai tersebut sebanyak dua kali secara beruntun.

 

*) Nilai yang ditulis ulang karena sama dengan bit penanda

Ø Bila terjadi penggabungan bit kanan menghasilkan nilai yang sama dengan bit penanda, sehingga nilai tersebut diduga sebagai bit penutup, maka deretan file tersebut tidak dikompresi.

 

*) Nilai hasil kompresi sama dengan bit penanda

Ø Bila banyaknya nilai yang dapat dikompresi berjumlah genap, maka nilai terakhir tidak perlu dikompresi.