Rumah >pembangunan bahagian belakang >Tutorial Python >Apakah senario penggunaan timbunan dan baris gilir keutamaan dalam Python?
Apakah senario penggunaan timbunan dan baris gilir keutamaan dalam Python?
Heap ialah struktur pokok binari khas yang sering digunakan untuk mengekalkan koleksi dinamik dengan cekap. Modul heapq dalam Python menyediakan pelaksanaan timbunan dan boleh melaksanakan operasi timbunan dengan mudah.
Barisan keutamaan juga merupakan struktur data khas Berbeza daripada baris gilir biasa, setiap elemennya mempunyai keutamaan yang berkaitan dengannya. Elemen keutamaan tertinggi dikeluarkan dahulu. Modul heapq dalam Python juga boleh melaksanakan fungsi baris gilir keutamaan.
Di bawah ini kami memperkenalkan beberapa senario khusus menggunakan timbunan dan baris gilir keutamaan, dan memberikan contoh kod yang berkaitan.
import heapq def top_k_smallest(nums, k): heap = [] for num in nums: heapq.heappush(heap, num) if len(heap) > k: heapq.heappop(heap) return heap nums = [5, 3, 8, 2, 7, 1, 9] k = 3 result = top_k_smallest(nums, k) print(result) # 输出 [3, 2, 1]
import heapq def merge_sorted_arrays(arrays): result = [] pq = [] for array in arrays: if array: heapq.heappush(pq, (array[0], array)) while pq: smallest, array = heapq.heappop(pq) result.append(smallest) if array[1:]: heapq.heappush(pq, (array[1], array[1:])) return result arrays = [[1, 3, 5], [2, 4, 6], [0, 7, 8]] result = merge_sorted_arrays(arrays) print(result) # 输出 [0, 1, 2, 3, 4, 5, 6, 7, 8]
import heapq def median(nums): min_heap = [] max_heap = [] for num in nums: if len(max_heap) == 0 or num <= -max_heap[0]: heapq.heappush(max_heap, -num) else: heapq.heappush(min_heap, num) if len(max_heap) > len(min_heap) + 1: heapq.heappush(min_heap, -heapq.heappop(max_heap)) elif len(min_heap) > len(max_heap): heapq.heappush(max_heap, -heapq.heappop(min_heap)) if len(max_heap) > len(min_heap): return -max_heap[0] elif len(min_heap) > len(max_heap): return min_heap[0] else: return (-max_heap[0] + min_heap[0]) / 2 nums = [4, 2, 5, 7, 1, 8, 3, 6] result = median(nums) print(result) # 输出 4.5
Di atas ialah beberapa senario penggunaan biasa dan kod sampel timbunan dan baris gilir keutamaan dalam Python. Timbunan dan baris gilir keutamaan ialah beberapa struktur data yang biasa digunakan, dan menguasai penggunaannya sangat membantu untuk menyelesaikan beberapa masalah yang rumit.
Atas ialah kandungan terperinci Apakah senario penggunaan timbunan dan baris gilir keutamaan dalam Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!