Tutorial Struktur Data Tumpukan

Data adalah sekumpulan nilai. Data dapat dikumpulkan dan dimasukkan secara berturut-turut, atau di lajur, atau di meja atau dalam bentuk pohon. Struktur data bukan hanya penempatan data dalam bentuk apa pun. Dalam pengkomputeran, struktur data adalah salah satu format ini, ditambah hubungan antara nilai, ditambah operasi (fungsi) yang dilakukan pada nilai. Anda semestinya sudah mempunyai pengetahuan asas mengenai struktur data pokok sebelum datang ke sini, kerana konsep di sana, akan digunakan di sini dengan sedikit atau tanpa penjelasan. Sekiranya anda tidak mempunyai pengetahuan itu, baca tutorial bertajuk, Tutorial Struktur Data Pokok untuk Pemula, di pautan, https: // linuxhint.com / tree_data_structure_tutorial_beginners /. Selepas itu, teruskan membaca tutorial ini.Struktur data timbunan adalah pokok binari yang lengkap atau hampir lengkap, di mana anak setiap nod sama atau lebih kecil nilainya daripada nilai induknya. Sebagai alternatif, ia adalah pokok di mana nilai ibu bapa sama dengan atau lebih kecil daripada nilai mana-mana anak-anaknya. Nilai (datum) pokok juga dipanggil kunci.

Ilustrasi Struktur Data Tumpukan

Terdapat dua jenis timbunan: timbunan maksimum dan timbunan min. Struktur timbunan maksimum adalah di mana nilai maksimum adalah akar, dan nilainya menjadi lebih kecil apabila pokok diturunkan; mana-mana ibu bapa sama ada nilainya atau lebih besar daripada mana-mana anak terdekatnya. Struktur timbunan min adalah di mana nilai minimum adalah akar, dan nilainya menjadi lebih besar apabila pokok diturunkan; mana-mana ibu bapa sama dengan atau lebih kecil nilainya daripada salah satu anak terdekatnya. Dalam rajah berikut, yang pertama adalah timbunan maksimum dan yang kedua adalah timbunan min:

Untuk kedua timbunan, perhatikan bahawa untuk sepasang anak, tidak menjadi masalah sama ada yang berada di sebelah kiri adalah nilai yang lebih besar. Baris di tingkat di pokok, tidak semestinya diisi dari minimum hingga maksimum, dari kiri; ia juga tidak semestinya diisi dari maksimum ke minimum, dari kiri.

Mewakili Tumpukan dalam Array

Agar perisian menggunakan timbunan dengan mudah, timbunan harus ditunjukkan dalam array. Tumpukan maksimum di atas, yang ditunjukkan dalam array ialah:

89, 85, 87, 84, 82, 79, 73, 80, 81,,, 65, 69

Ini dilakukan bermula dengan nilai root sebagai nilai pertama bagi array. Nilai terus diletakkan dengan membaca pokok dari kiri ke kanan, dari atas ke bawah. Sekiranya elemen tidak ada, kedudukannya dalam array dilangkau. Setiap nod mempunyai dua anak. Sekiranya nod berada di indeks (kedudukan) n, anak pertamanya dalam array berada di indeks 2n + 1, dan anak seterusnya berada di indeks 2n + 2. 89 berada di indeks 0; anak pertamanya, 85 berada di indeks 2 (0) + 1 = 1 sementara anak keduanya berada di indeks 2 (0) + 2 = 2. 85 berada di indeks 1; anak pertamanya, 84, berada di indeks 2 (1) + 1 = 3 sementara anak keduanya, 82 berada di indeks 2 (1) + 2 = 4. 79 berada di indeks 5; anak pertamanya, 65 berada di indeks 2 (5) + 1 = 11 sementara anak keduanya berada di indeks 2 (5) + 2 = 12. Rumus diterapkan pada elemen-elemen lain dalam tatasusunan.

Susunan seperti itu, di mana makna elemen dan hubungan antara elemen, yang tersirat oleh kedudukan elemen, disebut Struktur Data Tersirat.

Struktur data tersirat untuk timbunan min di atas adalah:

65, 68, 70, 73, 71, 83, 84,,, 79, 80,,, 85, 89

Tumpukan maksimum di atas adalah pokok binari lengkap tetapi bukan pokok binari penuh. Itulah sebabnya beberapa lokasi (kedudukan) kosong dalam array. Untuk pokok binari penuh, tiada lokasi akan kosong dalam tatasusunan.

Sekarang, jika timbunan adalah pokok yang hampir lengkap, misalnya, jika nilai 82 hilang, maka susunannya adalah:

89, 85, 87, 84,, 79, 73, 80, 81,,, 65, 69

Dalam keadaan ini, tiga lokasi kosong. Walau bagaimanapun, formula masih boleh digunakan.

Operasi

Struktur data adalah format data (e.g. pokok), ditambah hubungan antara nilai, ditambah operasi (fungsi) yang dilakukan pada nilai. Untuk timbunan, hubungan yang merangkumi keseluruhan timbunan adalah, bahawa ibu bapa mestilah sama atau lebih besar nilainya daripada anak-anak, untuk timbunan maksimum; dan ibu bapa mestilah sama atau kurang nilainya daripada anak-anak, untuk timbunan min. Hubungan ini dipanggil harta timbunan. Operasi timbunan dikelompokkan di bawah tajuk Penciptaan, Asas, Dalaman dan Pemeriksaan. Ringkasan operasi timbunan berikut:

Ringkasan Operasi Tumpukan

Terdapat operasi perisian tertentu yang biasa dengan timbunan, seperti berikut:

Penciptaan Tumpukan

create_heap: Membuat timbunan bermaksud membentuk objek yang mewakili timbunan. Dalam bahasa C, anda boleh membuat timbunan dengan jenis objek struktur. Salah satu anggota struktur akan menjadi susunan timbunan. Anggota selebihnya akan berfungsi (operasi) untuk timbunan. Create_heap bermaksud membuat timbunan kosong.

Heapify: Susunan timbunan adalah susunan (disusun) sebahagian yang disusun. Heapify bermaksud, menyediakan susunan timbunan dari susunan yang tidak disusun - lihat perincian di bawah.

Gabungan: Ini bermaksud, membentuk timbunan gabungan dari dua timbunan yang berbeza - lihat perincian di bawah. Kedua timbunan itu mestilah timbunan maksimum atau timbunan min kedua. Tumpukan baru sesuai dengan harta timbunan, sementara timbunan asli disimpan (tidak dipadamkan).

Meld: Ini bermaksud, gabungkan dua timbunan jenis yang sama untuk membentuk yang baru, mengekalkan pendua - lihat perincian di bawah. Tumpukan baru sesuai dengan harta timbunan, sementara timbunan asli musnah (terhapus). Perbezaan utama antara penggabungan dan penggabungan adalah, bahawa untuk penggabungan, satu pokok sesuai sebagai subtree ke akar pohon yang lain, yang memungkinkan nilai pendua pada pohon baru, sementara untuk penggabungan, pohon timbunan baru terbentuk, menghapus pendua. Tidak perlu mengekalkan dua timbunan asli dengan peleburan.

Operasi Tumpukan Asas

find_max (find_min): Cari nilai maksimum dalam array timbunan maksimum dan kembalikan salinannya, atau cari nilai minimum dalam susunan timbunan minimum dan kembalikan salinannya.

Sisipkan: Tambahkan elemen baru ke susunan timbunan, dan susun semula susunan supaya sifat timbunan rajah dikekalkan.

extract_max (extract_min): Cari nilai maksimum dalam array timbunan maksimum, alih keluar dan kembalikannya; atau cari nilai minimum dalam susunan timbunan min, keluarkan dan kembalikannya.

delete_max (delete_min): Cari simpul akar timbunan maksimum, yang merupakan elemen pertama bagi array timbunan maksimum, keluarkannya tanpa perlu mengembalikannya; atau cari simpul akar timbunan min, yang merupakan elemen pertama bagi susunan timbunan min, alih keluar tanpa perlu mengembalikannya;

Ganti: Cari node akar sama ada timbunan, lepaskan dan gantikan dengan yang baru. Tidak kira sama ada akar lama dikembalikan.

Operasi Tumpukan Dalaman

kenaikan_kunci (penurunan_kunci): Meningkatkan nilai mana-mana simpul untuk timbunan maksimum dan menyusun semula supaya harta timbunan dikekalkan, atau menurunkan nilai simpul mana-mana untuk timbunan minimum dan susun semula agar harta timbunan dikekalkan.

Padam: hapus sebarang nod, kemudian susun semula, supaya harta timbunan dikekalkan untuk timbunan maksimum atau timbunan min.

shift_up: gerakkan simpul ke dalam timbunan maksimum atau min-timbunan selama yang diperlukan, susun semula untuk mengekalkan harta timbunan.

shift_down: gerakkan node ke bawah dalam timbunan maksimum atau min-long selama diperlukan, susun semula untuk mengekalkan harta timbunan.

Pemeriksaan Tumpukan

Saiz: Ini mengembalikan bilangan kunci (nilai) dalam timbunan; ia tidak termasuk lokasi kosong susunan timbunan. Tumpukan dapat ditunjukkan dengan kod, seperti dalam rajah, atau dengan array.

kosong: Ini mengembalikan Boolean true jika tidak ada simpul dalam timbunan, atau Boolean false jika timbunan itu mempunyai sekurang-kurangnya satu simpul.

Menyaring timbunan

Terdapat sift-up dan sift down:

Peningkatan: Ini bermaksud menukar nod dengan induknya. Sekiranya harta timbunan tidak berpuas hati, tukar ibu bapa dengan ibu bapa sendiri. Teruskan dengan cara ini sehingga harta timbunan berpuas hati. Prosedurnya mungkin sampai ke akar.

Ayak-Turun: Ini bermaksud menukar simpul bernilai besar dengan yang lebih kecil dari dua anaknya (atau satu anak untuk timbunan hampir lengkap). Sekiranya harta timbunan tidak berpuas hati, tukar simpul bawah dengan simpul yang lebih kecil daripada dua anaknya sendiri. Teruskan dengan cara ini sehingga harta timbunan berpuas hati. Prosedur mungkin mencapai sehelai daun.

Menguatkan

Heapify bermaksud menyusun susunan yang tidak disusun agar harta tumpukan berpuas hati dengan timbunan maksimum atau timbunan minimum. Ini bermaksud mungkin terdapat beberapa lokasi kosong dalam array baru. Algoritma asas untuk menumpuk timbunan maksimum atau timbunan minimum adalah seperti berikut:

- jika simpul akar lebih ekstrem daripada salah satu nod anak, maka tukarlah akar dengan simpul anak yang kurang ekstrem.

- Ulangi langkah ini dengan simpul anak-anak dalam Skema Melintasi Pohon Pra-Pesanan.

Pokok terakhir adalah pokok timbunan yang memenuhi harta timbunan. Tumpukan boleh ditunjukkan sebagai rajah pokok atau dalam susunan. Timbunan yang dihasilkan adalah sebatang pokok yang disusun separa, i.e. sebilangan yang disusun separa.

Butiran Operasi Tumpukan

Bahagian artikel ini memberikan perincian operasi timbunan.

Penciptaan Butiran Tumpukan

buat_heap

Lihat di atas!

menimbun

Lihat di atas

bergabung

Sekiranya timbunan menyusun,

89, 85, 87, 84, 82, 79, 73, 80, 81,,, 65, 69

dan

89, 85, 84, 73, 79, 80, 83, 65, 68, 70, 71

digabungkan, hasilnya tanpa pendua mungkin,

89, 85, 87, 84, 82, 83, 81, 80, 79, 73, 68, 65, 69, 70, 71

Setelah diayak. Perhatikan bahawa dalam kumpulan pertama, 82 tidak mempunyai anak. Dalam susunan yang dihasilkan, ia berada di indeks 4; dan lokasinya di indeks 2 (4) + 1 = 9 dan 2 (4) + 2 = 10 kosong. Ini bermakna ia juga tidak mempunyai anak dalam rajah pokok baru. Dua timbunan yang asal tidak boleh dihapuskan kerana maklumatnya tidak terdapat dalam timbunan baru (susunan baru). Algoritma asas untuk menggabungkan timbunan jenis yang sama adalah seperti berikut:

- Gabung satu array ke bahagian bawah tatasusunan yang lain.

- Heapify menghilangkan pendua, memastikan bahawa simpul yang tidak mempunyai anak di timbunan asal, masih tidak mempunyai anak di timbunan baru.

menyatu

Algoritma untuk mencampurkan dua timbunan jenis yang sama (sama ada dua max- atau dua min-) adalah seperti berikut:

- Bandingkan dua nod akar.

- Jadikan akar yang kurang ekstrem dan sisa pokoknya (subtree), anak kedua dari akar ekstrem.

- Ayak anak yang sesat dari akar subtree yang ekstrem itu, ke bawah pada subtree yang ekstrem.

Tumpukan yang dihasilkan masih sesuai dengan harta timbunan, sementara timbunan yang asli musnah (terhapus). Tumpukan asli dapat dimusnahkan kerana semua maklumat yang mereka miliki masih ada di timbunan baru.

Operasi Tumpukan Asas

cari_max (cari_min)

Ini bermaksud untuk mencari nilai maksimum dalam array timbunan maksimum dan mengembalikan salinannya, atau mencari nilai minimum dalam susunan timbunan minimum dan mengembalikan salinannya. Susunan timbunan mengikut definisi sudah memenuhi harta timbunan. Jadi, kembalikan salinan elemen pertama array.

masukkan

Ini bermaksud menambahkan elemen baru ke susunan timbunan, dan menyusun semula susunan supaya harta timbunan rajah dikekalkan (puas). Algoritma untuk melakukan ini untuk kedua-dua jenis timbunan adalah seperti berikut:

- Andaikan pokok binari penuh. Ini bermaksud susunan harus diisi di hujung dengan lokasi kosong jika perlu. Jumlah simpul timbunan penuh ialah 1, atau 3 atau 7 atau 15 atau 31, dll.; terus menggandakan dan menambah 1.

- Letakkan simpul di lokasi kosong yang paling sesuai dengan magnitud, menjelang akhir timbunan (menjelang akhir susunan timbunan). Sekiranya tidak ada lokasi kosong, mulailah baris baru dari kiri bawah.

- Angkat jika perlu, sehingga harta tumpukan berpuas hati.

ekstrak_max (ekstrak_min)

Cari nilai maksimum dalam susunan timbunan maksimum, alih keluar dan kembalikannya; atau cari nilai minimum dalam susunan timbunan min, keluarkan dan kembalikannya. Algoritma untuk extract_max (extract_min) adalah seperti berikut:

- Keluarkan nod akar.

- Ambil (buang) simpul paling kanan bawah (simpul terakhir dalam array) dan letakkan di akar.

- Angkat dengan sewajarnya, sehingga harta tumpukan berpuas hati.

delete_max (delete_min)

Cari simpul akar timbunan maksimum, yang merupakan elemen pertama bagi susunan timbunan maksimum, alih keluar tanpa perlu mengembalikannya; atau cari simpul akar timbunan min, yang merupakan elemen pertama bagi susunan timbunan min, alih keluar tanpa perlu mengembalikannya. Algoritma untuk menghapus simpul akar adalah seperti berikut:

- Keluarkan nod akar.

- Ambil (buang) simpul paling kanan bawah (simpul terakhir dalam array) dan letakkan di akar.

- Angkat dengan sewajarnya, sehingga harta tumpukan berpuas hati.

ganti

Cari node akar sama ada timbunan, lepaskan dan gantikan dengan yang baru. Tidak kira sama ada akar lama dikembalikan. Ayak ke bawah jika sesuai, sehingga harta timun berpuas hati.

Operasi Tumpukan Dalaman

meningkatkan_kunci (penurunan_kunci)

Tingkatkan nilai mana-mana simpul untuk timbunan maksimum dan susun semula sehingga sifat timbunan dikekalkan, atau turunkan nilai sebarang simpul untuk timbunan minimum dan susun semula sehingga harta timbunan dikekalkan. Angkat ke atas atau ke bawah mengikut kesesuaian, sehingga harta tumpukan berpuas hati.

padam

Keluarkan simpul minat, kemudian susun semula, supaya harta timbunan dikekalkan untuk timbunan maksimum atau timbunan min. Algoritma untuk menghapus nod adalah seperti berikut:

- Keluarkan titik minat.

- Ambil (buang) simpul paling kanan bawah (simpul terakhir dalam array) dan letakkan di indeks nod yang dikeluarkan. Sekiranya nod yang dihapus berada di baris terakhir, maka ini mungkin tidak diperlukan.

- Angkat ke atas atau ke bawah mengikut kesesuaian, sehingga harta tumpukan berpuas hati.

shift_up

Pindahkan simpul ke dalam timbunan maksimum atau timbunan minimum selama diperlukan, susun semula untuk mengekalkan harta timbunan - angkat.

beralih ke bawah

Pindahkan simpul ke bawah dalam timbunan maksimum atau timbunan minimum selama diperlukan, susun semula untuk mengekalkan harta timbunan - ayakan ke bawah.

Pemeriksaan Tumpukan

ukuran

Lihat di atas!

kosong

Lihat di atas!

Kelas timbunan yang lain

Tumpukan yang dijelaskan dalam artikel ini boleh dianggap sebagai timbunan utama (umum). Terdapat kelas timbunan lain. Walau bagaimanapun, dua yang harus anda ketahui di luar ini adalah Binary Heap dan d-ary Heap.

Timbunan binari

Timbunan binari serupa dengan timbunan utama ini, tetapi dengan lebih banyak kekangan. Khususnya, timbunan binari mestilah pokok yang lengkap. Jangan mengelirukan antara pokok yang lengkap dan pokok yang penuh.

timbunan d-ary

Timbunan binari adalah timbunan 2 ary. Tumpukan di mana setiap simpul mempunyai 3 anak adalah timbunan 3-ary. Tumpukan di mana setiap simpul mempunyai 4 anak adalah timbunan 4-ary, dan seterusnya. Tumpukan d-ary mempunyai kekangan lain.

Kesimpulannya

Tumpukan adalah pokok binari yang lengkap atau hampir lengkap, yang memenuhi harta timbunan. Harta tumpukan mempunyai 2 alternatif: untuk timbunan maksimum, ibu bapa mestilah sama atau lebih besar nilainya daripada anak terdekat; untuk timbunan min, ibu bapa mestilah sama atau kurang nilainya daripada anak-anak terdekat. Tumpukan dapat ditunjukkan sebagai pohon atau dalam array. Apabila ditunjukkan dalam array, simpul root adalah simpul pertama array; dan jika nod berada di indeks n, anak pertama dalam array berada di indeks 2n + 1 dan anak seterusnya berada di indeks 2n + 2. Tumpukan mempunyai operasi tertentu yang dilakukan pada tatasusunan.

Chrys