Dalam Python, timbunan ialah alat berkuasa untuk mengurus koleksi elemen dengan cekap di mana anda sering memerlukan akses pantas kepada item terkecil (atau terbesar).
Modul heapq dalam Python menyediakan pelaksanaan algoritma baris gilir timbunan, juga dikenali sebagai algoritma baris gilir keutamaan.
Panduan ini akan menerangkan asas timbunan dan cara menggunakan modul heapq serta memberikan beberapa contoh praktikal.
Timbunan ialah struktur data berasaskan pokok khas yang memenuhi sifat timbunan:
Dalam Python, heapq melaksanakan timbunan min, bermakna elemen terkecil sentiasa berada di akar timbunan.
Timbunan amat berguna apabila anda memerlukan:
Modul heapq menyediakan fungsi untuk melaksanakan operasi timbunan pada senarai Python biasa.
Begini cara anda boleh menggunakannya:
Untuk mencipta timbunan, anda mulakan dengan senarai kosong dan gunakan fungsi heapq.heappush() untuk menambah elemen:
import heapq heap = [] heapq.heappush(heap, 10) heapq.heappush(heap, 5) heapq.heappush(heap, 20)
Selepas operasi ini, timbunan akan menjadi [5, 10, 20], dengan elemen terkecil pada indeks 0.
Elemen terkecil boleh diakses tanpa mengeluarkannya dengan hanya merujuk timbunan[0]:
smallest = heap[0] print(smallest) # Output: 5
Untuk mengalih keluar dan mengembalikan elemen terkecil, gunakan heapq.heappop():
smallest = heapq.heappop(heap) print(smallest) # Output: 5 print(heap) # Output: [10, 20]
Selepas operasi ini, timbunan melaraskan secara automatik dan elemen terkecil seterusnya mengambil kedudukan akar.
Jika anda sudah mempunyai senarai elemen, anda boleh menukarnya menjadi timbunan menggunakan heapq.heapify():
numbers = [20, 1, 5, 12, 9] heapq.heapify(numbers) print(numbers) # Output: [1, 9, 5, 20, 12]
Selepas timbunan, nombor akan menjadi [1, 9, 5, 12, 20], mengekalkan sifat timbunan.
Fungsi heapq.merge() membolehkan anda menggabungkan berbilang input yang diisih ke dalam satu output yang diisih:
heap1 = [1, 3, 5] heap2 = [2, 4, 6] merged = list(heapq.merge(heap1, heap2)) print(merged) # Output: [1, 2, 3, 4, 5, 6]
Ini menghasilkan [1, 2, 3, 4, 5, 6].
Anda juga boleh menggunakan heapq.nlargest() dan heapq.nsmallest() untuk mencari n elemen terbesar atau terkecil dalam set data:
numbers = [20, 1, 5, 12, 9] largest_three = heapq.nlargest(3, numbers) smallest_three = heapq.nsmallest(3, numbers) print(largest_three) # Output: [20, 12, 9] print(smallest_three) # Output: [1, 5, 9]
terbesar_tiga ialah [20, 12, 9] dan terkecil_tiga ialah [1, 5, 9].
Satu kes penggunaan biasa untuk timbunan ialah melaksanakan baris gilir keutamaan, di mana setiap elemen mempunyai keutamaan dan elemen dengan keutamaan tertinggi (nilai terendah) disampaikan dahulu.
import heapq class PriorityQueue: def __init__(self): self._queue = [] self._index = 0 def push(self, item, priority): heapq.heappush(self._queue, (priority, self._index, item)) self._index += 1 def pop(self): return heapq.heappop(self._queue)[-1] # Usage pq = PriorityQueue() pq.push('task1', 1) pq.push('task2', 4) pq.push('task3', 3) print(pq.pop()) # Outputs 'task1' print(pq.pop()) # Outputs 'task3'
Dalam contoh ini, tugasan disimpan dalam baris gilir keutamaan dengan keutamaan masing-masing.
Tugas dengan nilai keutamaan terendah sentiasa muncul dahulu.
Modul heapq dalam Python ialah alat yang berkuasa untuk mengurus data dengan cekap yang perlu mengekalkan susunan disusun berdasarkan keutamaan.
Sama ada anda sedang membina baris gilir keutamaan, mencari elemen terkecil atau terbesar atau hanya memerlukan akses pantas kepada elemen minimum, timbunan menyediakan penyelesaian yang fleksibel dan cekap.
Dengan memahami dan menggunakan modul heapq, anda boleh menulis kod Python yang lebih cekap dan bersih, terutamanya dalam senario yang melibatkan pemprosesan data masa nyata, tugas penjadualan atau mengurus sumber.
Atas ialah kandungan terperinci Memahami Modul heapq Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!