tugas select dalam select

tTransaksiPenjualanBuku

tMasterPelanggan

tMasterBuku

soal no 1 : tampilkan nama buku yg penerbitnya penebar swdaya dan oxford

jawab : select nama_buku from tMasterBuku where code in(select code from tMasterBuku where Penerbit='Penebar Swadaya' or penerbit='oxford');

output :

soal no 2 : Tampilkan buku yang belum laku terjual

jawab : SELECT distinct code, nama_buku FROM tMasterBuku WHERE code NOT IN (SELECT type FROM tTransaksiPenjualanBuku);

output :

soal no 3 Berapa jumlah buku yang dibeli octo siswardhono?

jawab:
select sum(qty) from tTransaksiPenjualanBuku where id_pelanggan in (select id_pelanggan from tMasterPelanggan1 where nama_pelanggan='octo siswardhono');

output:

soal no 4 : Tampilkan transaksi/besarnya harga buku yang dijual pada tanggal 21 Mei 2000?

select Harga from tTransaksiPenjualanBuku where type = any(select type from tTransaksiPenjualanBuku where tanggal_penjualan='21-05-2000');

output:



soal no 5 : tampilkan harga buku yang dibeli oleh adi kurniawan

select harga from tTransaksiPenjualanBuku where id_pelanggan in(select id_pelanggan from tMasterPelanggan where nama_pelanggan = 'adi kurniawan')

output:
soal no 6: tampilkan jumlah halaman dari buku yang belum laku

jawab : select halaman from tMasterBuku where code not in (select type from tTransaksiPenjualanBuku)

output :

soal no 7 : tampilkan nama pengarang yang dibeli oleh id_pelanggan 'p006'

jawab : select pengarang from tMasterBuku where code in (select type from tTransaksiPenjualanBuku where id_pelanggan ='P006');

output :

soal no 8 : tampilkan nama buku yang harganya lebih dar 60000

jawab : SELECT nama_buku FROM tMasterBuku WHERE code IN(SELECT type FROM tTransaksiPenjualanBuku WHERE harga >='60000');

output :

soal no 9 : tampilkan nama pelanggan yang membeli buku yang harganya lebih dari = 50000

jawab : select nama_pelanggan from tMasterPelanggan where id_pelanggan in (select id_pelanggan from tTransaksiPenjualanBuku where harga >='50000')

output :

soal no 10 : tampilkan alamat pelanggan yang melakukan transaksi pembelian pada tanggal 20 maret 2012

jawab : select alamat_pelanggan from tMasterPelanggan1 where id_pelanggan in (select id_pelanggan from tTransaksiPenjualanBuku where tanggal_penjualan = '20-03-2012')

output :

JAVA JOB

Konsep OOP

class - kumpulan atas definisi data dan fungsi-fungsi dalam suatu unit untuk suatu tujuan tertentu. Sebagai contoh 'class of dog' adalah suatu unit yang terdiri atas definisi-definisi data dan fungsi-fungsi yang menunjuk pada berbagai macam perilaku/turunan dari anjing. Sebuah class adalah dasar dari modularitas dan struktur dalam pemrograman berorientasi object. Sebuah class secara tipikal sebaiknya dapat dikenali oleh seorang non-programmer sekalipun terkait dengan domain permasalahan yang ada, dan kode yang terdapat dalam sebuah class sebaiknya (relatif) bersifat mandiri dan independen (sebagaimana kode tersebut digunakan jika tidak menggunakan OOP). Dengan modularitas, struktur dari sebuah program akan terkait dengan aspek-aspek dalam masalah yang akan diselesaikan melalui program tersebut. Cara seperti ini akan menyederhanakan pemetaan dari masalah ke sebuah program ataupun sebaliknya.

Objek

Dalam dunia nyata ataupun dalam sebuah program, sebuah objek memiliki dua karakteristik yaitu state dan behaviour. State adalah keadaan dari sebuah objek, seperti mobil memiliki state warna, model, tahun pembuatan, kondisi, dll. Sedang behaviour adalah kelakuan dari objek tersebut, seperti mobil dapat melaju, membelok, membunyikan klakson, dll. Objek menyimpan statenya dalam satu atau lebih variabel, dan mengimplementasikan behaviournya dengan metode. Dengan adanya penjelasan di atas, dapat disimpulkan bahwa objek adalah bagian software yang dibentuk dengan variabel-variabel dan metode-metode yang berhubungan dengan variabel tersebut.

Sebuah objek yang dibentuk dari sebuah kelas biasa disebut instans dalam terminologi OOP. Artinya objek tersebut adalah wujud nyata dari sebuah kelas. Variabel dan metode dari instans ini disebut variabel instans dan metode instans. Setiap instans menyimpan variabelnya sendiri-sendiri, jadi nilai variabel untuk tiap instans bisa berbeda.

Class Dan Atribut

Class adalah cetak biru atau rancangan dari sebuah object. Object adalah instansiasi atau perwujudan dari sebuah class, sebuah class dapat di instan menjadi satu atau lebih object, sebuah class tidak dapat digunakan untuk menyimpan, memanipulasi dan menampilkan data. Kita bisa melakukan proces-proses tersebut terhadap object.

Didalam class terdapat atribut atribut. Atribut adalah segala sesuatu yang berhubungan dengan objek. Misal didalam class rumah yang didalamnya maka atribut atributnya adalah kayunya, warnanya, pintunya, teras, luas dll.

Sedangkan Metohode adalah hal hal yang dapat dilakukan oleh class, dalam pemrogaman prosecural methode dapat diartikan sebagai f uction atau procedure. dalam contoh class rumah diatas, methodenya adalah tempat bernaung.

Package

Dalam rangka manajemen class, class-class yang secara fungsional sejenis bisa dikelompokkan kedalam suatu wadah atau kedalam suatu folder. ada banyak package bawaan java, sepeti java.awt, javax.swing. java.io, java.util. Namun demikian user diperbolehkan untuk membuat package sendiri. isi dari sebuah packagw adalah semua file class yang siap pakai.

Pewarisan

Terminologi asing untuk pewarisan adalah inheritance. Mungkin dalam literatur lain kita akan sering menjumpai istilah ini. Secara gamblang, pewarisan berarti sebuah kelas mewarisi state dan behaviour dari kelas lain. Sebagai contoh, sebuah kelas RumahMewah akan mewarisi state dan behaviour dari kelas Rumah. Begitu juga dengan kelas RumahSederhana. Kelas RumahMewah dan RumahSederhana disebut subkelas, atau kelas anak, dari kelas Rumah, yang disebut superkelas, atau kelas induk. Seluruh subkelas akan mewarisi (inherits) state dan behaviour dari superkelasnya. Dengan begitu, semua subkelas dari superkelas yang sama akan memiliki state dan behaviour yang sama. Namun, masing-masing subkelas bisa menambah sendiri state atau behaviournya.

Dalam kasus tertentu subkelas mungkin memiliki implementasi behaviour yang berbeda dengan superkelasnya. Hal seperti ini disebut override. Tingkat pewarisan tidak hanya terbatas pada dua tingkatan. Kita bisa terus memperpanjang tingkat pewarisan ini sepanjang yang kita butuhkan. Dengan begitu, subkelas-subkelas yang dibuat akan lebih khusus dan lebih terspesialisasi. Namun terdapat batasan pewarisan dalam Java yang disebut single inheritance. Artinya sebuah kelas hanya dapat mewarisi sifat dari satu dan hanya satu superkelas saja. Dalam beberapa bahasa pemrograman berorientasi objek lain, yang berlaku adalah multiple inheritance. Artinya sebuah kelas dapat mewarisi sifat dari beberapa superkelas sekaligus.

Dalam Java, terdapat kelas Object yang merupakan superkelas dari semua kelas dalam Java, baik yang builtin ataupun yang kita buat sendiri, lansung maupun tidak langsung. Karena itu sebuah variabel bertipe Object akan dapat menyimpan referensi ke objek apapun dalam bahasa Java. Kelas Object ini memiliki behaviour yang dibutuhkan semua objek untuk dapat dijalankan di Java Virtual Machine. Manfaat penggunaan konsep pewarisan antara lain: pertama, kita dapat menggunakan kembali kelas-kelas yang kita buat (sebagai superkelas) dan membuat kelas-kelas baru berdasar superkelas tersebut dengan karakteristik yang lebih khusus dari behaviour umum yang dimiliki superkelas. Kedua, kita dapat membuat superkelas yang hanya mendefinisikan behaviour namun tidak memberi implementasi dari metode-metode yang ada. Hal ini berguna jika kita ingin membuat semacam template kelas. Kelas semacam ini disebut kelas abstrak, karena behaviournya masih abstrak dan belum diimplementasikan. Subkelas-subkelas dari kelas semacam ini, yang disebut kelas konkret, mengimplementasikan behaviour abstrak tersebut sesuai dengan kebutuhan masing-masing.

F. Polimorfisme

Polimorfisme secara bahasa dapat diartikan memiliki banyak bentuk. Konsep ini terdapat dalam bahasa pemrograman seperti konstruktor yang memiliki beberapa bentuk. Selain konstruktor, konsep ini juga berlaku bagi metode. Metode atau konstruktor dapat memiliki banyak bentuk dalam arti memiliki nama yang sama namun dengan argumen yang berbeda atau dengan return type yang berbeda.

Array

Program yang cukup besar pasti membutuhkan banyak variable. kita bisa saja mendeklarasikan variable tersebut satu per satu. misalkan kita membutuhkan 5 variable dengan tipe integer, kita bisa mendeklarasikanya dengan int a , b, c, d, e;. ini masih sangat kecil, bagaimana kalau kita membutuhkan 100 variable ? ini pasti jadi tidak efisien. maka kita bisa menggunakan array.

Tetapi sebelum kita memutuskan untuk mengggunakan array, kita juga harus meneliti apakah data data tersebut akan di akses secara berurut? jika ya maka kita bisa menggunakan array, tapi data data tersebut tidak akan diakses secara berurut, sebaiknya di deklarasikan sendiri sendiri.

Cara mendeklarasikan array :

int [] arr = new int[10];

Hak Akses

OOP memberikan beberapa tipe hak akses terhadap variable (atribut), methode bahkan class. Tipe tipe hak akses tersebut yaitu Public, Private, atau Protected. Ini adalah salah satu bagian terpenting dari OOP, sehingga programmer yang hendak belajar OOP wajib memahami konsep pengaksesan data ini dalam OOP.

UML from Java

tugas java II :

membuat contoh UML

Istilah Istilah Sistem Basis Data Dalam Tabel Relasional

RELASI

Relasi dapat juga diartikan sebagai tabel dengan baris-baris dan kolom yang menjadi penyusunya. Elemen relasi adalah baris baris (tupel) dalam tabel bersebut. Baris atau tupel ini serupa dengan record dalam file. tupel tupel ini dapat muncul dengan sembarang urutan dalam relasi, dan tupel tupel ini tidak mungkin atau tidak boleh muncul lebih dari satu kali, karena setiap baris atau tupel adalah unik. Sehingga relasi dapat juga di katakan sebagai himpunan tupel yang unik. Oleh karena dia merupakan himpunan tupel tupel, sehingga urutan menjadi tidak dipermasalahkan selayaknya teori himpunan dalam matimatika.

ATRIBUT

Atribut merupakan kolom pada sebuah relasi. Setiap entitas pasti memiliki aribut yang mendeskripsikan karakter dari entitas tersebut. Penentuan atau pemilihan atribut-atribut yang relevan bagi sebuah entitas merupakan hal penting dalam pembentukan model data.

TUPEL

Tupel dapat diartikan sebagai baris dalam relasi, atau dapat juga disebut sagai record dalam file. Setiap tupel adalah unik, berdasarkan kunci tertendu, tidak boleh ada tupel yang sama berada dalam suatu relasi. Satu record mewakili satu data atau informasi tentang seseorang, misalnya : NPM,nama mahasiswa, alamat, kota, dll.

DOMAIN

Domain adalah himpunan nilai yang valid yang terdapat dalam suatu atribut. Setiap atribut dalam basis data relasional didefinisikan terhadap suatu domain.

DERAJAT

Derajat merupakan jumlah atribut-atribut yang ada dalam suatu relasi.

CARDINALITY

Merupakan jumlah tupel yang ada dalam suatu relasi. cardinality relasi akan berubah ketika tupel ditambah atau dikurangi. Nilai cardinality adalah kondisi suatu saat dari relasi.

CONTOH GAMBAR:

Tugas Tentang Candidate & Alternate Key

Candidate Keys

Dalam model relasional dari database , kunci kandidat dari sebuah hubungan adalah minimal superkey untuk hubungan itu, yaitu, satu set atribut sehingga relasi tidak memiliki dua berbeda tupel dengan nilai yang sama untuk atribut-atribut ini tidak ada subset yang tepat dari atribut yang berlaku. Sejak relasi tidak berisi duplikat tupel, himpunan semua atributnya adalah superkey jika nilai NULL tidak digunakan. Ini berarti bahwa setiap hubungan akan memiliki minimal satu kunci kandidat. Peserta kunci relasi memberitahu kita semua cara yang mungkin kita dapat mengidentifikasi tupel nya. Dengan demikian mereka merupakan konsep penting untuk desain skema database . Untuk alasan praktis RDBMSs biasanya membutuhkan bahwa untuk setiap relasi salah satu kunci calon yang dinyatakan sebagai kunci utama , yang berarti bahwa dianggap sebagai cara yang lebih disukai untuk mengidentifikasi tupel individu. Asing kunci , misalnya, biasanya diperlukan untuk referensi seperti primary key dan tidak ada satu kunci kandidat lainnya.

Alternative Keys

Dalam konteks database relasional , kunci alternatif (atau tombol sekunder) adalah setiap kunci kandidat yang tidak dipilih menjadi primary key (PK) .

Sebagai contoh, sebuah database relasional dengan tabel "karyawan" dapat memiliki atribut seperti "employee_id", "national_insurance_number", dan seterusnya. Dalam hal ini, baik "employee_id" dan "national_insurance_number" berfungsi sebagai pengidentifikasi unik untuk karyawan tertentu, dan dengan demikian bisa dibilang digunakan untuk kunci primer. Oleh karena itu, keduanya disebut kandidat kunci "". Jika, misalnya, "national_insurance_number" dipilih sebagai kunci utama, "employee_id" akan menjadi kunci alternatif.

Data manipulation Language & Data Definition Language

DML adalah suatu keluarga bahasa komputer yang digunakan oleh program komputer dan / atau pengguna database untuk menyisipkan, menghapus dan update data dalam database . Read-only query, yaitu SELECT , data ini dapat dianggap sebagai salah satu bagian dari DML atau di luar itu, tergantung pada konteksnya.

Saat ini bahasa manipulasi data yang paling populer adalah yang dari SQL , yang digunakan untuk mengambil dan memanipulasi data dalam database relasional. Bentuk lain dari DML adalah yang digunakan oleh IMS / DLI, CODASYL database (seperti IDMS ), dan lain-lain.
Modifikasi data terdiri dari: penambahan (insert), pembaruan (update) dan penghapusan (delete).
1.Penambahan Data
Instruksi SQL untuk melakukan penambahan data adalah menggunakan syntax:
INSERT INTO [(field1, field2, …)]
VALUES (field1 [,field2, …]) | SQL-SELECT
Keterangan
-  nama tabel yang akan ditambahkan datanya
-[(field1, field2, …)] field-field di dalam tabel yang akan diisikan nilainya
-VALUES (nilai1 [,nilai2, …]) | SQL-SELECT  nilai yang diisikan
Jika mengisikan sebuah data tunggal saja yang tidak diambil dari tabel lain, gunakan:
VALUES (nilai1 [,nilai2, …])
Contoh
Untuk mengisikan data pada tabel penerbit:
INSERT INTO penerbit (PN_ID, PN_Nama) 
VALUES (91, 'CV Angkasa')

2.Mengubah Data
Instruksi SQL untuk melakukan perubahan data adalah menggunakan syntax:
UPDATE
SET = [ , = , …]
[WHERE ]
Keterangan
-  nama tabel yang akan ditambahkan datanya
-SET = [,=,... ]  nilai baru yang akan diisikan pada field tertentu
-[WHERE ]  filter yang berlaku untuk menentukan data mana saja yang diupdate

Contoh
Untuk melakukan update tertentu, yakni memberikan keterangan dg isian ‘Buku TA’ untuk semua koleksi yang berjenis buku TA (KL_TK_ID=4):
UPDATE koleksi SET KL_Keterangan = 'Buku TA'
WHERE KL_TK_ID=4

3.Menghapus Data
Instruksi SQL untuk menghapus data adalah menggunakan syntax:
DELETE FROM
[WHERE ]
Keterangan
-  nama tabel yang akan ditambahkan datanya
-[WHERE ]  filter yang berlaku untuk menentukan data mana saja yang dihapus

Contoh
Untuk menghapus seluruh koleksi yang berjenis buku TA (idJenisKoleksi=4)
DELETE FROM koleksi WHERE KL_TK_ID=4

DDL adalah bahasa komputer untuk mendefinisikan struktur data . Istilah pertama kali diperkenalkan sehubungan dengan Codasyl model database, mana skema database ditulis dalam Data Definisi Bahasa menggambarkan catatan, ladang, dan "set" yang membentuk pengguna Data Model . Awalnya itu disebut subset dari SQL, tetapi sekarang digunakan dalam pengertian generik untuk merujuk ke bahasa formal untuk menggambarkan data atau struktur informasi, seperti skema XML. jenis lainnya kalimat DDL di SQL merupakan laporan untuk mendefinisikan integritas referensial hubungan, biasanya diimplementasikan sebagai primer kunci dan kunci asing tag di beberapa kolom tabel.
Contoh DDL:
Buatlah sebuah tabel barang yang atributnya kode barang, dan nama barang. Tulislah syntax DDL-nya, lalu dengan syntax alter table, tambahkan primary key pada kode barang. Dan tambahkan atribut jumlah barang pada tabel barang. Lalu, buatlah tabel pembelian dengan atribut id pembelian, id barang (merupakan foreign key dari tabel barang), jumlah barang barang transaksi, dan tanggal!

Membuat tabel barang dengan atribut kode barang dan nama barang :
CREATE TABLE BARANG(
KODE_BARANG CHAR(8),
NAMA_BARANG VARCHAR2(25)
);
Menambahkan primary key pada kode barang :
ALTER TABLE BARANG
ADD CONSTRAINT PK_BARANG PRIMARY KEY (KODE_BARANG)
Menambahkan atribut jumlah barang :
ALTER TABLE BARANG
ADD JUMLAH BARANG (NUMBER)
Membuat tabel pembelian :
CREATE TABLE PEMBELIAN (
ID_BELI CHAR(8),
KODE_BARANG CHAR(8),
JUMLAH_TRANSAKSI NUMBER,
TANGGAL DATE,
CONSTRAINT PK_PEMBELIAN PRIMARY KEY (ID_BELI),
CONSTRAINT FK_PEMBELIAN FOREIGN KEY (KODE_BARANG) REFERENCES BARANG(KODE_BARANG)
);
Aturan untuk proses update : berlaku pada proses pengubahan data di parent table.

Update cascade : pembaruan sebuah baris data diikuti dengan pembaruan baris data pada child table yang terelasikan
Update restrict : mencegah proses pembaruan data jika terdapat baris data di child table yang terelasikan
Update ignore : mengabaikan referensi. Boleh memperbarui data pada parent, tapi tidak memperbarui data yang berelasi pada child table.
Aturan untuk delete : berlaku pada proses modifikasi di parent table.

Delete cascade : menghapus seluruh baris data pada child table yg terelasikan
Delete restrict : mencegah penghapusan jika terdapat baris data yang berelasi pada child table
Delete ignore : mengabaikan referensi. Boleh menghapus data, dan tidak ada efeknya bagi child table.
Aturan untuk insert : berlaku pada proses penambahan data pada child table.

Insert restrict : tidak boleh menambah data pada child table, jika nilai yang dimasukkan pada kolom yang berelasi tidak terdapat pada parent tablenya.
Insert ignore : mengabaikan referensi. Boleh menambah data pada child, walaupun nilai yang dimasukkan pada kolom yang berelasi tidak terdapat pada parent table

Jurnal Heap

Penerapan heap tree dalam heap sort dan penggunaannya

Studi Kasus pada Penggunaan heap sort menggunakan algoritma

Adi Kurniawan¹, Mery Anggraini², Deniel Christ Evhant M³

Program Studi Sarjana Tekhnik Informatika

Fakultas Ilmu Komputer, Universitas Pembangunan Nasional

adink16_donuts@yahoo.com, merycute59@yahoo.com, christ_evhant@yahoo.co.id.

Abstract

Mahasiswa Teknik Informatika dan orang-orang lain yang berkecimpung dalam bidang pemrograman (programming) sering sekali menghadapi masalah pengurutan dalam membangun sebuah program aplikasi. Misalnya saja dalam membangun sebuah aplikasi pengolah data mahasiswa, programmer akan dihadapkan pada masalah pengurutan data mahasiswa berdasarkan atribut tertentu, seperti nama, NIM, nilai, dan sebagainya. Di dalam bidang Teknik Informatika sendiri terdapat banyak sekali jenis-jenis algoritma pengurutan yang dapat digunakan untuk memecahkan masalah pengurutan tersebut, di antaranya adalah bubble sort, merge sort, insertion

sort, quick sort, dan selection sort, serta masih banyak lagi jenis algoritma pengurutan lainnya. Oleh karena itu, teknik dan kejelian untuk memilih algoritma pengurutan yang tepat dan sesuai dengan permasalahan pengurutan yang dihadapi sangat diperlukan karena masing-masing algoritma pengurutan tersebut memiliki karakteristik yang berbeda-beda. Penulis memilih untuk mengangkat tema Heap Sort dalam makalah ini sebab heap sort merupakan salah satu algoritma pengurutan yang memiliki kompleksitas waktu asimptotik terbaik. Selain itu juga, heap sort menerapkan teknik yang unik di dalam memecahkan masalah pengurutan, yaitu dengan menggunakan heap tree. Pada makalah ini akan dibahas dan dianalisis heap tree dan kegunaanya dalam heap sort, serta contoh sederhana mengenai cara penerapan algoritma pengurutan heap sort dalam memecahkan suatu masalah pengurutan.

Kata kunci: algoritma pengurutan, mangkus, kompleksitas waktu asimptotik, heap sort, heap tree.

Pendahuluan

Untuk memecahkan masalah pengurutan dalam membangun suatu program aplikasi, dibutuhkan algoritma pengurutan. Di dalam bidang Teknik Informatika terdapat banyak sekali jenis-jenis algoritma pengurutan yang dapat digunakan untuk memecahkan masalah pengurutan.

Pengurutan data (data sorting) merupakan bagian dari pengolahan data informasi. Dari data-data yang telah didapat, ada kalanya data tersebut harus diurutkan terlebih dahulu berdasarkan aturan yang lebih dulu ditentukan. Berdasarkan nilai maupun alphabet misalnya.

Metode-metode pengurutan data pun ada berbagai jenis. Mulai dari binary sort, insertion sort, merge sort, heap sort dll. Penggunaan metode mana yang akan dipakai nantinya tergantung dari jenis maupun kuantitas data yang diolah.

Heap sort, algoritma pengurutan, merupakan salah satu metode pengurutan yang sering digunakan. Melalui jurnal ini akan dibahas teknik pencarian ini beserta kelebihan dan kekurangannya.

Oleh karena itu, teknik untuk memilih algoritma pengurutan yang tepat, sesuai dengan kebutuhan, dan mangkus sangat diperlukan karena masing-masing algoritma pengurutan memiliki karakteristik yang berbedabeda. Heap sort merupakan salah satu contoh algoritma pengurutan yang memiliki kompleksitas waktu asimptotik terbaik serta menerapkan teknik yang unik/khas di dalam memecahkan masalah pengurutan, yaitu dengan menggunakan heap tree.

Heap

Pengertian Heap

Pohon 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 minheap.

• 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.

Gambar : Contoh dari max heap


Jenis-jenis Heap :

1. Binary heap : Binary heap adalah heap yang dibuat dengan menggunakan pohon biner.
2. Binomial heap : Binomial heap adalah heap yang dibuat dengan menggunakan pohon binomial. Pohon binomial bila didefinisikan secara rekursif adalah:

• Sebuah pohon binomial dengan tinggi 0 adalah simpul tunggal
• Sebuah pohon binomial dengan tinggi k mempunyai sebuah simpul akar yang anak-anaknya adalah akar-akar pohonpohon binomial dengan tinggi k-1,k- 2,…,2,1,0.

Gambar : pohon-pohon binomial dengan tinggi (order) 0 s/d 3

3. Fibonacci Heap

Fibonacci heap adalah kumpulan pohon yang membentuk minimum heap. Pohon dalam struktur data ini tidak memiliki bentuk yang tertentu dan pada kasus yang ekstrim heap ini memiliki semua elemen dalam pohon yang berbeda atau sebuah pohon tunggal dengan tinggi n. Keunggulan dari Fibonacci heap adalah ketika menggabungkan heap cukup dengan menggabungkan dua list pohon.

Gambar : Contoh Fibonacci heap

Perbandingan kompleksitas jenis-jenis heap

Tabel 1. Perbandingan macam-macam heap

Heap Sort

Heap Sort adalah sebuah algoritma pengurutan yang paling lambat dari algoritma yang memiliki kompleksitas O(n log n). Tetapi tidak seperti algoritma Merge Sort dan Quick Sort, algoritma Heap Sort tidak memerlukan rekursif yang besar atau menggunakan banyak tabel (array). Oleh karena itu, Heap Sort adalah pilihan yang baik untuk sebuah kumpulan data yang besar.

Algoritma ini bekerja dengan menentukan elemen terbesar (atau terkecil) dari sebuah daftar elemen, dan diletakkan pada akhir (atau awal) dari daftar tersebut. Heap sort menyelesaikan sebuah pengurutan menggunakan struktur data yang disebut heap.

Algoritma ini dimulai dengan membangun sebuah array heap dengan membangun tumpukan dari kumpulan data, lalu memindahkan data terbesar ke bagian belakang dari sebuah tabel hasil. Setelah itu, array heap dibangun kembali, kemudian mengambil elemen terbesar untuk diletakkan di sebelah item yang telah dipindahkan tadi. Hal ini diulang sampai array heap habis.

Jadi secara umum, algoritma ini memerlukan dua buah tabel; satu tabel untuk menyimpan heap, dan satu tabel lainnya untuk menyimpan hasil. Walaupun lebih lambat dari Merge Sort atau Quick Sort, algoritma ini cocok untuk digunakan pada data yang berukuran besar.

1. Algoritma Heapify

Algoritma Heapify adalah membangun sebuah heap dari bawah ke atas, secara berturut-turut berubah ke bawah untuk membangun heap. Permasalahan pertama yang harus kita pertimbangkan dalam melakukan operasi heapify adalah dari bagian mana kita harus memulai. Bila kita mencoba operasi heapify dari akar maka akan terjadi operasi runut-naik seperti algoritma bubble sort yang akan menyebabkan kompleksitas waktu yang ada akan berlipat ganda. Sebuah versi lain adalah membangun heap secara atas-bawah dan berganti-ganti ke atas untuk secara konseptual lebih sederhana untuk ditangani. Versi ini mulai dengan sebuah heap kosong dan secara berturut-turut memasukkan data. Versi lainnya lagi adalah dengan membentuk pohon heap-pohon heap mulai dari subtree-subtree yang paling bawah. Jika subtree-subtree suatu simpul sudah membentuk heap maka pohon dari simpul tersebut mudah dijadikan pohon heap dengan mengalirkannya ke bawah. Setelah diuji, maka ide yang paling efisien adalah versi yang terakhir, yang kompleksitas algoritmanya pada kasus terburuk adalah O(n), sedangkan versi membentuk heap tree-heap tree dari atas ke bawah kompleksitas nya O(n log n).

Jadi, algoritma utama heapify adalah melakukan iterasi mulai dari internal simpul paling kanan bawah(pada representasi larik, adalah elemen yang berada di indeks paling besar) hingga akar, kemudian kearah kiri dan naik ke level di atasnya, dan seterusnya hingga mencapai akar (sebagai larik [0..N-1]). Oleh karena itu, iterasi dilakukan mulai dari j= N/2 dan berkurang satu-satu hingga mencapai j=0. Pada simpul internal tersebut, pemeriksaan hanya dilakukan pada simpul anaknya langsung (tidak pada level-level lain di bawahnya). Pada saat iterasi berada di level yang lebih tinggi, subtreesubtree selalu sudah membentuk heap. Jadi, kasus yang paling buruk adalah restrukturisasi hanya akan mengalirkan simpul tersebut kearah bawah. Dengan demikian, heapify versi ini melakukan sebanyak N/2 kali iterasi, dan pada kasus yang paling buruk akan melakukan iterasi sebanyak ²log(N) kali.

2. Algoritma Remove
Algoritma remove ini menukar akar (yang berisi nilai maksimum) dari heap dengan elemen terakhir. Secara logika, simpul yang berada paling kanabawah dipindahkan ke akar untuk menggantikan simpul akar yang akan diambil.

3. Algoritma Reheapify

Algoritma reheapify ini melakukan pembuatan ulang heap dari atas ke bawah seperti halnya iterasi terakhir dari algoritma metoda heapify. Perbedaan antara metode heapify dengan metode reheapify ada pada iterasi yang dilakukan oleh kedua algoritma tersebut. Algoritma metode reheapify ini hanya melakukan iterasi terakhir dari algoritma heapify. Hal ini disebabkan baik subtree kiri maupun subtree kanannya sudah merupakan heap, sehingga tidak perlu dilakukan iterasi lengkap seperti algoritma heapify. Dan setelah reheapify maka simpul yang akan diiterasikan berikutnya akan berkurang satu.

Penerapan Algoritma Pengurutan Heap Sort

Salah satu contoh penerapan algoritma pengurutan (sorting algorithm) heap sort adalah sebagai berikut: Misalkan terdapat suatu array bilangan bulat yang terdiri dari sepuluh buah anggota dengan nilai data 11, 9, 8, 27, 16, 25, 12, 13, 34, dan 43. Kita akan mengurutkan data diatas dengan menggunakan heapsort. Pertama-tama, array di atas dapat dipandang sebagai suatu Complete Binary Tree (CBT) sebagai berikut:

Selanjutnya algoritma metoda heapify dilakukan dengan iterasi dari subtree node ke-4, ke-3, dan seterusnya berturut-turut hingga mencapai root (akar). Iterasi dilakukan mulai dari node ke-4 karena N/2 dalam contoh di atas adalah 5. Dan elemen kelima dari array memiliki nilai indeks 4 sebab indeks array biasanya diawali dari 0. Penerapan algoritma metoda heapify terhadap Complete Binary Tree (CBT) pada contoh di atas menghasilkan operasi-operasi pertukaran sebagai berikut:

1. Subtree node ke-4: pertukaran 16 dengan 43

2. Subtree node ke-3: pertukaran 27 dengan 34

3. Subtree node ke-2: pertukaran 8 dengan 25

4. Subtree node ke-1: pertukaran 9 dengan 43, lalu pertukaran 9 dengan 16

5. Subtree node ke-0: pertukaran 11 dengan 43, lalu pertukaran 11 dengan 34, serta akhirnya pertukaran 11 dengan 27 Perubahan-perubahan (pertukaran) tersebut dapat digambarkan sebagai berikut:

Semua perubahan di atas terjadi dalam array yang bersangkutan, sehingga pada akhirnya diperoleh tree terakhir yang merupakan heap tree. Sementara itu, dalam iterasi yang melakukan/menerapkan algoritma metoda remove( ) dan algoritma metoda reheapify() akan terjadi pemrosesan berikut:

1. Setelah 43 di-remove dan 9 menggantikan posisi yang ditinggalkan oleh 43, maka terjadi reheapify: penukaran 9 dengan 34, 9 dengan 27, dan 9 dengan 13.

dan data yang telah terurut adalah 43.

2. Setelah 34 di-remove dan 11 menggantikan posisi yang ditinggalkan oleh 34, maka terjadi reheapify: penukaran 11 dengan 27, dan 11 dengan 16.

dan data yang telah terurut adalah 34, 43.

3. Setelah 27 di-remove dan 9 menggantikan posisi yang ditinggalkan oleh 27, maka terjadi reheapify: penukaran 9 dengan 25, dan 9 dengan 12.

dan data yang telah terurut adalah 27, 34, 43.

4. Demikian seterusnya dilakukan algoritma metoda remove dan algoritma metoda reheapify hingga tidak ada lagi node yang tersisa. Dan pada akhirnya akan didapatkan hasil data yang telah terurut adalah 8, 9, 11, 12, 13, 16, 25, 27, 34, 43.

Program Heap Sort & Penjelasannya

<#include <>

void restoreHup(int*,int); // pemanggilan fungsi void restoreHup

void restoreHdown(int*,int,int); //pemanggilan fungsi void restoreHdown

void main()

{ // pembuka void main

int a[20],n,i,j,k; // mendeklarasikan bahwa a[20] ,n,i,j,k adalah integer

printf(" Masukkan jumlah element : ");// untuk menampilkan kelayar perintah memasukkan jumlah element

scanf("%d",&n); // untuk mengidentifikasikan nilai yang dimasukkan melalui keyboard

printf(" Masukkan element : "); //untuk menampilkan kelayar perintah untuk memasukkan element

for(i=1;i<=n;i++) //funsi for dimana jika ketentuan untuk i terpenuhi maka progran di bawahnya akan dijalankan

{ // pembuka fungsi for

scanf("%d",&a[i]); // untuk mengidentifikasi array a

restoreHup(a,i); // a , i dalam fungsi restoreHup

} // penutup fungsi for

j=n; // nilai j sama dengan n

for(i=1;i<=j;i++) //funsi for dimana jika ketentuan untuk i terpenuhi maka progran di bawahnya akan dijalankan

{ // pembuka fungsi for

int temp; // temp sebagai integer

temp=a[1]; // temp sama dengan nilai array a yang pertama

a[1]=a[n]; // nilai array a yg ke 1 sama dengan array a yang ke n

a[n]=temp; // nilai array a yang ke n sama dengan nilay temp

n--; // nilai n selalu berkurang 1

restoreHdown(a,1,n); // a , 1, n dalam fungsi restoreHdown

} // penutup fungsi for

n=j; // n sama dengan nilai j

printf(" Here is it... "); // untuk menampilkan perintah ke dalam layar

for(i=1;i<=n;i++) //funsi for dimana jika ketentuan untuk i terpenuhi maka progran di bawahnya akan dijalankan

printf("%4d",a[i]); // untuk menampilkan nilai array ke i ke layar

} // penutup void main

void restoreHup(int *a,int i) // fungsi void restore Hup

{ // pembuka fungsi foid restoreHup

int v=a[i]; // v sama dengan nilai array a yang ke i

while((i>1)&&(a[i/2]

{ // pembuka fungsi while

a[i]=a[i/2]; // nilai array a yang ke i sama dengan nilai array a yang ke i/2

i=i/2; // nilai i sama dengan nilai i/2

} //penutup fungsi while

a[i]=v; // nilai array a yang ke i sama dengan nilai v

} // penutup fungsi while

void restoreHdown(int *a,int i,int n) // fungsi void restoreHdown

{ // pembuka fungsi void restoreHdown

int v=a[i]; // v sama dengan nilai array a yang ke i sebagai integer

int j=i*2;// nilai j sama dengan i kali 2 ialah integer

while(j<=n) // fungsi while akan dijalankan bila ketentuannya terpenuhi

{ // pembuka fungsi while

if((j

j++; // nilai j akan selalu tambah 1

if(a[j]

break;

a[j/2]=a[j]; // nilai array a yang ke j/2 sama dengan nilai array a yang ke j

j=j*2; // nilai j sama dengan nilai j*2

}// penutup fungsi while

a[j/2]=v;// nilai array a yang ke j/2 sama dengan v

}// penutup fungsi void restorehdown

//Suatu program untuk mengimplementasikan Heap Sort>

Hasil Program diatas :

Kesimpulan

• Algoritma pengurutan heap sort dapat digunakan untuk menyelesaikan masalah-masalah pengurutan dalam membangun suatu program aplikasi dengan mangkus.
• Keunggulan algoritma pengurutan heap sort terletak pada kompleksitas waktu asimptotiknya yang sangat baik.
• Meskipun lebih lambat dari algoritma pengurutan data yang lain, algoritma heap sort memiliki kelebihan ketika menangani data dalam skala yang besar/massive. Karena algoritma ini memiliki kelebihan tidak menggunakan banyak tabel, tetapi hanya satu tabel yang dipakai untuk menyimpan hasil dari pengurutan tersebut.

Referensi / Daftar Pustaka

• www.google.com
• http://www.informatika.org/~rinaldi/Matdis/2008-2009/Makalah2008/Makalah0809-046.pdf
• http://www.informatika.org/~rinaldi/Stmik/Makalah/MakalahStmik08.pdf
• http://www.ilmu-komputer.net/algorithms/heap-sort-source-code/

neh bagi yg mw download...