Bagaimanakah timbunan dan baris gilir keutamaan dilaksanakan dalam Python?

Bagaimanakah timbunan dan baris gilir keutamaan dilaksanakan dalam Python?

Timbunan dan baris gilir keutamaan ialah struktur data yang biasa digunakan dalam sains komputer. Dalam Python, kita boleh menggunakan modul heapq untuk melaksanakan timbunan dan barisan keutamaan.

Timbunan ialah sejenis pokok binari lengkap Dalam timbunan, nilai setiap nod induk adalah lebih kecil (atau lebih besar) daripada nilai nod anaknya Timbunan sedemikian dipanggil timbunan akar kecil (atau akar besar timbunan). Dalam Python, timbunan boleh diwakili oleh senarai. Modul heapq Python menyediakan beberapa kaedah untuk memanipulasi timbunan.

Pertama, kita perlu menggunakan kaedah heapq.heapify() untuk menukar senarai kepada heap. Berikut ialah contoh:

import heapq

heap = [4, 1, 3, 5, 2]
heapq.heapify(heap)
print(heap)

Hasil output ialah: [1, 2, 3, 5, 4], menunjukkan bahawa senarai telah ditukar menjadi timbunan akar kecil.

Untuk menambah elemen pada timbunan, anda boleh menggunakan kaedah heapq.heappush(). Berikut ialah contoh:

import heapq

heap = [1, 2, 3, 5, 4]
heapq.heappush(heap, 6)
print(heap)

Hasil output ialah: [1, 2, 3, 5, 4, 6], menunjukkan bahawa 6 telah ditambah dengan betul pada timbunan.

Untuk mengeluarkan elemen terkecil (atau terbesar) daripada timbunan, anda boleh menggunakan kaedah heapq.heappop(). Berikut ialah contoh:

import heapq

heap = [1, 2, 3, 5, 4, 6]
min_element = heapq.heappop(heap)
print(min_element)
print(heap)

Hasil keluaran ialah: 1 dan [2, 4, 3, 5, 6], menunjukkan bahawa elemen terkecil telah muncul dengan betul.

Dalam baris gilir keutamaan, setiap elemen mempunyai keutamaan yang sepadan Elemen dengan keutamaan yang lebih tinggi dialih keluar daripada baris gilir terlebih dahulu. Dalam Python, kita boleh menggunakan modul heapq untuk melaksanakan baris gilir keutamaan.

Pertama, kita perlu membuat senarai kosong untuk mewakili baris gilir keutamaan. Kemudian kita boleh menggunakan kaedah heapq.heappush() untuk memasukkan elemen ke dalam baris gilir mengikut keutamaannya. Berikut ialah contoh:

import heapq

queue = []
heapq.heappush(queue, (1, "apple"))
heapq.heappush(queue, (3, "banana"))
heapq.heappush(queue, (2, "cherry"))

print(queue)

Hasil keluarannya ialah: [(1, 'epal'), (3, 'pisang'), (2, 'ceri')], menunjukkan bahawa elemen telah dimasukkan dengan betul ke dalam beratur mengikut keutamaan tengahnya.

Untuk mengeluarkan elemen keutamaan tertinggi daripada baris gilir keutamaan, anda boleh menggunakan kaedah heapq.heappop(). Berikut ialah contoh:

import heapq

queue = [(1, 'apple'), (3, 'banana'), (2, 'cherry')]

highest_priority_element = heapq.heappop(queue)
print(highest_priority_element)
print(queue)

Hasil keluarannya ialah: (1, 'epal') dan [(2, 'ceri'), (3, 'pisang')], menunjukkan bahawa elemen dengan keutamaan tertinggi telah muncul naik dengan betul.

Di atas ialah pelaksanaan asas timbunan dan baris gilir keutamaan dalam Python. Dengan menggunakan modul heapq, kami boleh dengan mudah melaksanakan timbunan dan baris gilir keutamaan serta melaksanakan operasi yang berkaitan.

Atas ialah kandungan terperinci Bagaimanakah timbunan dan baris gilir keutamaan dilaksanakan dalam Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!