Kapan saya ingin menggunakan heap?

Selain jawaban yang jelas dari Antrean Prioritas, kapankah tumpukan akan berguna dalam petualangan pemrograman saya?

Gunakan kapan pun Anda membutuhkan akses cepat ke item terbesar (atau terkecil), karena item itu akan selalu menjadi elemen pertama dalam larik atau di akar pohon.

Namun, sisa larik tetap tidak disortir sebagian. Dengan demikian, akses instan hanya mungkin untuk item terbesar (terkecil). Penyisipan cepat, jadi ini cara yang baik untuk menangani acara atau data yang masuk dan selalu memiliki akses ke yang paling awal / terbesar.

Berguna untuk antrian prioritas, penjadwal (di mana item paling awal diinginkan), dll ...

Heap adalah pohon yang nilai node induknya lebih besar daripada nilai node turunannya.

Jika Anda menganggap heap sebagai pohon biner yang disimpan dalam urutan linier berdasarkan kedalaman, dengan simpul akar terlebih dahulu (kemudian anak dari simpul itu berikutnya, kemudian anak dari simpul itu selanjutnya); maka anak-anak dari sebuah node pada indeks N berada pada 2N + 1 dan 2N + 2. Properti ini memungkinkan akses cepat menurut indeks. Dan karena heap dimanipulasi dengan menukar node, ini memungkinkan pengurutan di tempat.

Heaps adalah struktur yang dimaksudkan untuk memungkinkan akses cepat ke min atau max .

Tetapi mengapa Anda menginginkan itu? Anda bisa memeriksa setiap entri yang ditambahkan untuk melihat apakah itu yang terkecil atau terbesar. Dengan cara ini Anda selalu memiliki yang terkecil atau terbesar dalam waktu konstan O(1).

Jawabannya adalah karena heaps memungkinkan Anda untuk menarik yang terkecil atau terbesar dan dengan cepat mengetahui yang terkecil atau terbesar NEXT . Itulah mengapa disebut Antrian Prioritas.

Contoh dunia nyata (bukan dunia yang sangat adil):

Misalkan Anda memiliki rumah sakit tempat pasien dirawat berdasarkan usia mereka. Yang tertua selalu dihadiri pertama, tidak peduli kapan dia masuk antrian.

Anda tidak bisa hanya melacak yang tertua karena jika Anda menariknya keluar, Anda tidak akan tahu yang tertua berikutnya. Untuk mengatasi masalah rumah sakit ini, Anda menerapkan tumpukan maksimal . Heap ini, menurut definisi, diurutkan sebagian. Ini berarti Anda tidak dapat mengurutkan pasien berdasarkan usianya, tetapi Anda tahu bahwa yang paling tua selalu berada di atas, sehingga Anda dapat menarik pasien keluar dalam waktu yang konstan O(1)dan menyeimbangkan kembali tumpukan dalam waktu log O(log N).

Contoh yang lebih canggih:

Misalkan Anda memiliki urutan bilangan bulat dan Anda ingin melacak median. Median adalah angka yang berada di tengah-tengah larik terurut.

Contoh:

[1, 2, 5, 7, 23, 27, 31]

Dalam kasus di atas, 7adalah median karena larik yang berisi bilangan yang lebih kecil [1, 2, 5]berukuran sama dengan larik yang berisi bilangan yang lebih besar [23, 27, 31]. Biasanya, jika array memiliki jumlah elemen ganjil, median adalah rata-rata aritmatika dari 2 elemen di tengahnya, misalnya (5 + 7)/2.

Sekarang, bagaimana Anda melacak median? Dengan memiliki 2 heap , satu min heap berisi angka yang lebih kecil dari median saat ini dan max heap yang berisi angka lebih besar dari median saat ini. Sekarang, jika tumpukan ini selalu seimbang, 2 tumpukan akan berisi jumlah elemen yang sama atau salah satunya akan memiliki 1 elemen lebih banyak dari yang lain, paling banyak.

Saat Anda menambahkan elemen baru ke urutan, jika angkanya lebih kecil dari median saat ini, Anda menambahkannya ke min heap, jika tidak, Anda menambahkannya ke heap maks. Sekarang, jika heap tidak seimbang (satu heap memiliki lebih dari 1 elemen lebih banyak dari yang lain), Anda menarik sebuah elemen dari heap terbesar dan menambahkan ke yang terkecil. Sekarang mereka seimbang.

Karakteristik heap adalah bahwa ia merupakan struktur yang memelihara data semi-berurutan; dengan demikian, ini adalah pertukaran yang baik antara biaya pemeliharaan pesanan lengkap dan biaya pencarian melalui kekacauan acak. Karakteristik tersebut digunakan pada banyak algoritma, seperti pemilihan, pengurutan, atau klasifikasi.

Karakteristik lain yang berguna dari sebuah heap adalah ia dapat dibuat di tempat dari sebuah array!

Juga bagus untuk algoritma seleksi (menemukan min atau max)

kapan pun Anda mengurutkan daftar sementara, Anda harus mempertimbangkan tumpukan.

Anda dapat menggunakan minHeap atau maxHeap saat Anda ingin mengakses elemen terkecil dan terbesar.