


Apakah senario penggunaan timbunan dan baris gilir keutamaan dalam Python?
Oct 28, 2023 am 08:56 AMApakah 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.
- Mencari masalah K Teratas
Mencari elemen k terbesar atau terkecil dalam satu jujukan ialah masalah biasa, seperti mencari nombor k terbesar pertama atau nombor k terkecil pertama. Masalah ini boleh diselesaikan dengan mudah menggunakan timbunan saiz k atau barisan keutamaan.
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]
- Gabung tatasusunan
Gabungkan berbilang nombor tersusun untuk membentuk tatasusunan adalah masalah biasa. Ia boleh dilaksanakan menggunakan baris gilir keutamaan Setiap kali, elemen terkecil dikeluarkan dari setiap tatasusunan dan dimasukkan ke dalam baris gilir keutamaan, dan kemudian elemen dalam baris gilir dibawa keluar.
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]
- Cari median
Mencari median jujukan ialah masalah klasik. Ini boleh dicapai menggunakan dua longgokan, longgokan maks untuk separuh pertama jujukan dan longgokan min untuk separuh kedua jujukan. Memastikan saiz dua timbunan sama atau berbeza dengan satu, median boleh diambil di bahagian atas timbunan.
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!

Artikel Panas

Alat panas Tag

Artikel Panas

Tag artikel panas

Notepad++7.3.1
Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6
Alat pembangunan web visual

SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Topik panas

Perbezaan dan senario penggunaan antara Redis dan MongoDB

Perbezaan dan senario penggunaan antara Redis dan Elasticsearch

Penjelasan terperinci pelaksanaan baris gilir keutamaan dalam Redis

Apakah perbezaan antara timbunan dan timbunan

Deque dalam Python: Melaksanakan baris gilir dan susunan yang cekap

Perbezaan antara timbunan dan timbunan

Timbunan dan baris gilir keutamaan dalam C++

Apakah perbezaan antara java heap dan stack
