My first Magazine pemrograman-kompetitif-dasar | Page 118

10 Struktur Data NonLinear
Pak Blangkon, sahabat karib Pak Dengklek, sering mengunjungi Pak Dengklek untuk mem-
beli batu akik. Sebagai penggemar berat batu akik, ia hanya tertarik dengan batu akik
paling berharga. Pak Blangkon akan meminta Pak Dengklek menunjukkan harga tertinggi
yang ada, dan apabila disukai, batu tersebut akan dibeli. Pak Dengklek kadang-kadang
kewalahan, karena batu akik yang ia miliki bisa jadi sangat banyak sehingga pencarian batu
paling berharga menjadi repot. Ia meminta bantuan Anda untuk melakukan pencatatan atas
batu yang dimiliki dan melayani Pak Blangkon secara efisien.
Bantulah Pak Dengklek!
Contoh
Misalkan:
• simpan(x) menyatakan Pak Dengklek membawa pulang batu akik seharga x.
• lihat() menyatakan Pak Blangkon ingin tahu harga tertinggi untuk batu akik yang dimiliki
Pak Dengklek pada saat ini.
• jual() menyatakan Pak Dengklek menjual batu akik dengan harga tertinggi kepada Pak
Blangkon.
Berikut contoh operasinya dan perilaku yang diharapkan:
•
•
•
•
•
•
simpan(5), harga-harga batu akik yang disimpan: [5].
simpan(7), harga-harga batu akik yang disimpan: [5, 7].
simpan(3), harga-harga batu akik yang disimpan: [5, 7, 3].
lihat(), laporkan bahwa 7 merupakan harga tertinggi dari batu akik yang disimpan.
jual(), harga-harga batu akik yang tersisa: [5, 3].
lihat(), laporkan bahwa 5 merupakan harga tertinggi dari batu akik yang disimpan.
Mari kita mulai dengan solusi sederhana. Solusi paling mudah adalah membuat sebuah
array dan variabel yang menunjukkan posisi terakhir elemen pada array . Untuk setiap operasi
simpan(x), isikan nilai x pada elemen array yang ditunjuk, geser variabel penunjuk ke belakang,
lalu urutkan data secara menaik. Operasi lihat() dapat dilayani dengan mengembalikan elemen
terbesar yang dipastikan berada di paling belakang array . Operasi jual() dapat dilayani dengan
menggeser variabel penunjuk ke depan, sehingga elemen terbesar kini tidak dianggap berada di
dalam array .
Misalkan N menyatakan banyaknya elemen yang terisi pada array . Jika pengurutan yang
digunakan adalah quicksort , maka operasi simpan(x) berlangsung dalam O(N log N). Operasi
lihat() dan jual() berlangsung dalam O(1). Perhatikan bahwa pengurutan akan lebih efisien jika
digunakan insertion sort, sehingga kompleksitas simpan(x) menjadi O(N). Kompleksitas dari
solusi sederhana ini ditunjukkan pada Tabel 10.1.
Tabel 10.1: Kompleksitas solusi Hobi Batu Akik dengan solusi sederhana.
Operasi
Dengan insertion sort
simpan(x)
O(N)
lihat()
O(1)
jual()
O(1)
Solusi sederhana ini tidak efisien ketika banyak dilakukan operasi add(x). Kita akan mempe-
lajari bagaimana heap mengatasi masalah ini secara efisien.
108