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.

1. 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]

2. 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]

3. 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!