Panduan untuk Heaps dengan Python

Pengantar

Bayangkan sebuah bandara yang ramai dengan penerbangan yang lepas landas dan mendarat setiap menitnya. Sama seperti pengontrol lalu lintas udara yang memprioritaskan penerbangan berdasarkan urgensinya, heap membantu kami mengelola dan memproses data berdasarkan kriteria tertentu, memastikan bahwa bagian data yang paling “mendesak” atau “penting” selalu dapat diakses di bagian atas.

Dalam panduan ini, kita akan memulai perjalanan untuk memahami heap dari awal. Kita akan mulai dengan menjelaskan apa itu heap dan properti bawaannya. Dari sana, kita akan mendalami implementasi heaps milik Python, yaitu heapq modul, dan jelajahi serangkaian fungsinya yang kaya. Jadi, jika Anda pernah bertanya-tanya bagaimana cara mengelola kumpulan data dinamis secara efisien yang sering kali memerlukan elemen prioritas tertinggi (atau terendah), Anda siap melakukannya.

Apa itu Tumpukan?

Hal pertama yang ingin Anda pahami sebelum mendalami penggunaan heap adalah apa itu tumpukan. Heap menonjol dalam dunia struktur data sebagai pembangkit tenaga listrik berbasis pohon, khususnya yang ahli dalam hal tersebut menjaga ketertiban dan hierarki. Meskipun mungkin menyerupai pohon biner bagi mata yang tidak terlatih, nuansa struktur dan aturan yang mengaturnya jelas membedakannya.

Salah satu ciri khas heap adalah sifatnya sebagai a pohon biner lengkap. Ini berarti bahwa setiap tingkat pohon, kecuali mungkin yang terakhir, terisi seluruhnya. Dalam level terakhir ini, node terisi dari kiri ke kanan. Struktur seperti ini memastikan bahwa heap dapat direpresentasikan dan dimanipulasi secara efisien menggunakan array atau daftar, dengan posisi setiap elemen dalam array mencerminkan penempatannya di pohon.

Namun esensi sebenarnya dari tumpukan terletak pada tumpukannya pemesanan. Dalam tumpukan maks, nilai simpul mana pun melampaui atau sama dengan nilai turunannya, sehingga menempatkan elemen terbesar tepat di akar. Di sisi lain, a tumpukan minimal beroperasi dengan prinsip yang berlawanan: nilai simpul apa pun kurang dari atau sama dengan nilai turunannya, memastikan elemen terkecil berada di akar.

Seiring kemajuan kita, kita akan mendalami lebih dalam bagaimana properti bawaan heap ini memungkinkan operasi yang efisien dan bagaimana Python heapq modul dengan mulus mengintegrasikan tumpukan ke dalam upaya pengkodean kami.

Karakteristik dan Sifat Tumpukan

Tumpukan, dengan struktur dan prinsip pengurutannya yang unik, menghasilkan serangkaian karakteristik dan properti berbeda yang menjadikannya sangat berharga dalam berbagai skenario komputasi.

Pertama dan terpenting, tumpukan adalah efisien secara inheren. Struktur berbasis pohonnya, khususnya format pohon biner lengkap, memastikan bahwa operasi seperti penyisipan dan ekstraksi elemen prioritas (maksimum atau minimum) dapat dilakukan dalam waktu logaritmik, biasanya O (log n). Efisiensi ini merupakan keuntungan bagi algoritme dan aplikasi yang memerlukan akses sering ke elemen prioritas.

Properti penting lainnya dari tumpukan adalah milik mereka efisiensi memori. Karena heap dapat direpresentasikan menggunakan array atau daftar tanpa memerlukan pointer eksplisit ke node anak atau induk, sehingga menghemat ruang. Posisi setiap elemen dalam array sesuai dengan penempatannya di pohon, sehingga memungkinkan traversal dan manipulasi yang dapat diprediksi dan mudah.

Properti pemesanan heaps, baik sebagai max heap atau min heap, memastikan hal itu root selalu memegang elemen dengan prioritas tertinggi. Pengurutan yang konsisten inilah yang memungkinkan akses cepat ke elemen prioritas utama tanpa harus menelusuri seluruh struktur.

Selain itu, tumpukan adalah serba guna. Meskipun tumpukan biner (di mana setiap orang tua memiliki paling banyak dua anak) adalah yang paling umum, tumpukan dapat digeneralisasikan untuk memiliki lebih dari dua anak, yang dikenal sebagai tumpukan d-ary. Fleksibilitas ini memungkinkan penyesuaian berdasarkan kasus penggunaan dan persyaratan kinerja tertentu.

Terakhir, tumpukan adalah menyesuaikan diri. Setiap kali unsur ditambahkan atau dihilangkan, struktur akan mengatur ulang dirinya sendiri untuk mempertahankan sifat-sifatnya. Penyeimbangan dinamis ini memastikan bahwa heap tetap dioptimalkan untuk operasi intinya setiap saat.

Saat kita mempelajari lebih dalam implementasi dan aplikasi praktis Python, potensi heap yang sebenarnya akan terungkap di hadapan kita.

Jenis Tumpukan

Tidak semua tumpukan diciptakan sama. Bergantung pada urutan dan sifat strukturalnya, heap dapat dikategorikan ke dalam tipe berbeda, yang masing-masing memiliki rangkaian aplikasi dan keunggulannya sendiri. Dua kategori utama adalah tumpukan maks dan tumpukan minimal.

Ciri yang paling membedakan a tumpukan maks adalah nilai dari setiap simpul tertentu lebih besar atau sama dengan nilai turunannya. Hal ini memastikan bahwa elemen terbesar di heap selalu berada di root. Struktur seperti ini sangat berguna ketika ada kebutuhan untuk sering mengakses elemen maksimum, seperti dalam implementasi antrian prioritas tertentu.

Lawan dari max heap, a tumpukan minimal memastikan bahwa nilai dari setiap node yang diberikan kurang dari atau sama dengan nilai dari anak-anaknya. Ini memposisikan elemen terkecil dari heap di root. Min heap sangat berharga dalam skenario di mana elemen terkecil adalah yang paling penting, seperti dalam algoritma yang menangani pemrosesan data real-time.

Di luar kategori utama ini, tumpukan juga dapat dibedakan berdasarkan faktor percabangannya:

Meskipun tumpukan biner adalah yang paling umum, dengan setiap orang tua memiliki paling banyak dua anak, konsep tumpukan dapat diperluas ke node yang memiliki lebih dari dua anak. Di sebuah tumpukan d-ary, setiap node memiliki paling banyak d anak-anak. Variasi ini dapat dioptimalkan untuk skenario tertentu, seperti mengurangi ketinggian pohon untuk mempercepat operasi tertentu.

Tumpukan Binomial adalah himpunan pohon binomial yang didefinisikan secara rekursif. Tumpukan binomial digunakan dalam implementasi antrian prioritas dan menawarkan operasi penggabungan yang efisien.

Dinamakan berdasarkan deret Fibonacci yang terkenal, the tumpukan Fibonacci menawarkan waktu berjalan diamortisasi yang lebih baik untuk banyak operasi dibandingkan dengan tumpukan biner atau binomial. Mereka sangat berguna dalam algoritma optimasi jaringan.

Implementasi Heap Python – The tumpukan Modul

Python menawarkan modul bawaan untuk operasi heap – the heapq modul. Modul ini menyediakan kumpulan fungsi terkait heap yang memungkinkan pengembang mengubah daftar menjadi heap dan melakukan berbagai operasi heap tanpa memerlukan implementasi khusus. Mari selami nuansa modul ini dan bagaimana modul ini memberi Anda kekuatan heap.

Grafik heapq modul tidak menyediakan tipe data heap yang berbeda. Sebaliknya, ia menawarkan fungsi yang berfungsi pada daftar Python biasa, mengubah dan memperlakukannya sebagai tumpukan biner.

Pendekatan ini hemat memori dan terintegrasi secara mulus dengan struktur data Python yang ada.

Itu artinya itu tumpukan direpresentasikan sebagai daftar in heapq. Keindahan dari representasi ini adalah kesederhanaannya – sistem indeks daftar berbasis nol berfungsi sebagai pohon biner implisit. Untuk setiap elemen tertentu pada posisi i, dia:

• Anak Kiri berada pada posisinya 2*i + 1
• Anak Kanan sudah pada posisinya 2*i + 2
• Node Induk berada pada posisinya (i-1)//2

Struktur implisit ini memastikan bahwa tidak diperlukan representasi pohon biner berbasis node yang terpisah, sehingga pengoperasian menjadi mudah dan penggunaan memori menjadi minimal.

Penting untuk dicatat bahwa heapq modul membuat tumpukan minimum secara default. Artinya elemen terkecil selalu berada di akar (atau posisi pertama dalam daftar). Jika Anda membutuhkan tumpukan maksimal, Anda harus membalikkan urutan dengan mengalikan elemen dengan -1 atau gunakan fungsi perbandingan khusus.

Python heapq modul menyediakan serangkaian fungsi yang memungkinkan pengembang melakukan berbagai operasi tumpukan pada daftar.

Pada bagian berikut, kita akan mendalami masing-masing operasi mendasar ini, menjelajahi mekanisme dan kasus penggunaannya.

Cara Mengubah Daftar menjadi Heap

Grafik heapify() function adalah titik awal untuk banyak tugas yang berhubungan dengan heap. Dibutuhkan sebuah iterable (biasanya berupa daftar) dan mengatur ulang elemen-elemennya di tempat untuk memenuhi properti dari min heap:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(data)
print(data)

Ini akan menampilkan daftar yang disusun ulang yang mewakili tumpukan minimum yang valid:

[1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

Cara Menambahkan Elemen ke Heap

Grafik heappush() fungsi memungkinkan Anda memasukkan elemen baru ke dalam heap sambil mempertahankan properti heap:

import heapq heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
print(heap)

Menjalankan kode akan memberi Anda daftar elemen yang mempertahankan properti min heap:

[3, 5, 7]

Cara Menghapus dan Mengembalikan Elemen Terkecil dari Heap

Grafik heappop() fungsi mengekstrak dan mengembalikan elemen terkecil dari heap (root dalam heap min). Setelah dihapus, ini memastikan daftar tetap berupa tumpukan yang valid:

import heapq heap = [1, 3, 5, 7, 9]
print(heapq.heappop(heap))
print(heap)

Ini akan menampilkan elemen terkecil dan daftar sisanya:

1
[3, 7, 5, 9]

Di sini, 1 adalah elemen terkecil dari heap, dan daftar sisanya tetap mempertahankan properti heap, bahkan setelah kami menghapusnya 1.

Cara Mendorong Item Baru dan Memunculkan Item Terkecil

Grafik heappushpop() function adalah operasi gabungan yang mendorong item baru ke heap lalu muncul dan mengembalikan item terkecil dari heap:

import heapq heap = [3, 5, 7, 9]
print(heapq.heappushpop(heap, 4)) print(heap)

Ini akan menampilkan 3, elemen terkecil, dan cetak yang baru heap daftar yang sekarang disertakan 4 sambil mempertahankan properti heap:

3
[4, 5, 7, 9]

Cara Mengganti Item Terkecil dan Push Item Baru

Grafik heapreplace() function memunculkan elemen terkecil dan mendorong elemen baru ke heap, semuanya dalam satu operasi yang efisien:

import heapq heap = [1, 5, 7, 9]
print(heapq.heapreplace(heap, 4))
print(heap)

Ini mencetak 1, elemen terkecil, dan daftar sekarang menyertakan 4 dan mempertahankan properti heap:

1
[4, 5, 7, 9]

Menemukan Berbagai Ekstrem di Tumpukan Python

nlargest(n, iterable[, key]) dan nsmallest(n, iterable[, key]) fungsi dirancang untuk mengambil beberapa elemen terbesar atau terkecil dari sebuah iterable. Mereka bisa lebih efisien daripada mengurutkan seluruh iterable ketika Anda hanya memerlukan beberapa nilai ekstrim. Misalnya, Anda memiliki daftar berikut dan Anda ingin menemukan tiga nilai terkecil dan tiga nilai terbesar dalam daftar:

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

Di sini, nlargest() dan nsmallest() fungsi bisa berguna:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(heapq.nlargest(3, data)) print(heapq.nsmallest(3, data)) 

Ini akan memberi Anda dua daftar – satu berisi tiga nilai terbesar dan yang lainnya berisi tiga nilai terkecil darinya data Daftar:

[9, 6, 5]
[1, 1, 2]

Cara Membangun Tumpukan Kustom Anda

Sedangkan Python heapq modul ini menyediakan seperangkat alat canggih untuk bekerja dengan heap, ada beberapa skenario di mana perilaku min heap default mungkin tidak cukup. Baik Anda ingin mengimplementasikan heap maksimal atau membutuhkan heap yang beroperasi berdasarkan fungsi perbandingan kustom, membuat heap kustom bisa menjadi jawabannya. Mari kita jelajahi cara menyesuaikan tumpukan dengan kebutuhan spesifik.

Menerapkan Max Heap menggunakan heapq

Secara default, heapq menciptakan tumpukan minimal. Namun, dengan trik sederhana, Anda dapat menggunakannya untuk mengimplementasikan max heap. Idenya adalah membalikkan urutan elemen dengan mengalikannya -1 sebelum menambahkannya ke heap:

import heapq class MaxHeap: def __init__(self): self.heap = [] def push(self, val): heapq.heappush(self.heap, -val) def pop(self): return -heapq.heappop(self.heap) def peek(self): return -self.heap[0]

Dengan pendekatan ini, bilangan terbesar (dalam hal nilai absolut) menjadi bilangan terkecil, sehingga memungkinkan heapq berfungsi untuk mempertahankan struktur heap maksimal.

Tumpukan dengan Fungsi Perbandingan Kustom

Terkadang, Anda mungkin memerlukan heap yang tidak hanya membandingkan berdasarkan urutan alami elemen. Misalnya, jika Anda bekerja dengan objek kompleks atau memiliki kriteria pengurutan tertentu, fungsi perbandingan khusus menjadi penting.

Untuk mencapai hal ini, Anda dapat menggabungkan elemen dalam kelas pembantu yang mengesampingkan operator perbandingan:

import heapq class CustomElement: def __init__(self, obj, comparator): self.obj = obj self.comparator = comparator def __lt__(self, other): return self.comparator(self.obj, other.obj) def custom_heappush(heap, obj, comparator=lambda x, y: x < y): heapq.heappush(heap, CustomElement(obj, comparator)) def custom_heappop(heap): return heapq.heappop(heap).obj

Dengan pengaturan ini, Anda dapat menentukan fungsi pembanding khusus apa pun dan menggunakannya dengan heap.

Kesimpulan

Heap menawarkan kinerja yang dapat diprediksi untuk banyak operasi, menjadikannya pilihan yang dapat diandalkan untuk tugas-tugas berbasis prioritas. Namun, penting untuk mempertimbangkan persyaratan dan karakteristik spesifik dari aplikasi yang ada. Dalam beberapa kasus, mengubah implementasi heap atau bahkan memilih struktur data alternatif mungkin menghasilkan kinerja dunia nyata yang lebih baik.

Heap, seperti yang telah kita bahas, lebih dari sekadar struktur data. Mereka mewakili pertemuan efisiensi, struktur, dan kemampuan beradaptasi. Dari properti dasar hingga implementasinya dengan Python heapq modul, heaps menawarkan solusi yang kuat untuk berbagai tantangan komputasi, terutama yang berpusat pada prioritas.

• Konten Bertenaga SEO & Distribusi PR. Dapatkan Amplifikasi Hari Ini.
• PlatoData.Jaringan Vertikal Generatif Ai. Berdayakan Diri Anda. Akses Di Sini.
• PlatoAiStream. Intelijen Web3. Pengetahuan Diperkuat. Akses Di Sini.
• PlatoESG. Karbon, teknologi bersih, energi, Lingkungan Hidup, Tenaga surya, Penanganan limbah. Akses Di Sini.
• PlatoHealth. Kecerdasan Uji Coba Biotek dan Klinis. Akses Di Sini.
• Sumber: https://stackabuse.com/guide-to-heaps-in-python/