Bagaimana untuk melaksanakan algoritma jenis timbunan menggunakan Python?

Bagaimana untuk menggunakan Python untuk melaksanakan algoritma isihan timbunan?

Isihan timbunan ialah algoritma pengisihan berdasarkan timbunan binari, yang mengambil kesempatan daripada sifat pokok binari yang lengkap. Timbunan boleh dibahagikan kepada dua jenis: timbunan maks dan timbunan min Timbunan maks memerlukan nilai nod induk lebih besar daripada atau sama dengan nilai nod anaknya, manakala timbunan min memerlukan nilai nod induk. adalah kurang daripada atau sama dengan nilai nod anaknya. Dalam algoritma isihan timbunan kami menggunakan timbunan maks.

Berikut ialah langkah dan contoh kod khusus untuk menggunakan Python untuk melaksanakan jenis timbunan:

Langkah 1: Bina timbunan maksimum
Dalam proses membina timbunan maksimum, kita perlu Laraskan struktur timbunan supaya nilai setiap nod induk adalah lebih besar daripada atau sama dengan nilai nod anaknya.

Pertama, kami mentakrifkan fungsi heapify untuk melaksanakan proses pelarasan timbunan. Fungsi ini menerima tiga parameter: timbunan senarai timbunan, saiz timbunan dan indeks nod induk yang akan dilaraskan.

def heapify(heap, size, parent):
    largest = parent
    left = 2 * parent + 1
    right = 2 * parent + 2

    if left < size and heap[left] > heap[largest]:
        largest = left

    if right < size and heap[right] > heap[largest]:
        largest = right

    if largest != parent:
        heap[parent], heap[largest] = heap[largest], heap[parent]
        heapify(heap, size, largest)

Seterusnya, kami mentakrifkan fungsi build_heap untuk membina timbunan maksimum. Fungsi ini menerima senarai sebagai hujah dan membina timbunan maks berdasarkan elemen dalam senarai.

def build_heap(heap):
    size = len(heap)

    for i in range(size // 2 - 1, -1, -1):
        heapify(heap, size, i)

Langkah 2: Isih timbunan
Selepas membina timbunan maks, kita boleh menggunakan sifat timbunan maks untuk mengisih. Idea pengisihan timbunan adalah untuk menukar elemen teratas timbunan (nilai maksimum) dengan elemen terakhir setiap kali, laraskan bahagian atas timbunan, kemudian keluarkan nilai maksimum, dan laraskan semula sehingga hanya terdapat satu elemen tertinggal dalam timbunan.

Berikut ialah langkah dan contoh kod khusus untuk mengisih menggunakan algoritma isihan timbunan:

def heap_sort(heap):
    size = len(heap)

    build_heap(heap)

    for i in range(size - 1, 0, -1):
        heap[0], heap[i] = heap[i], heap[0]
        heapify(heap, i, 0)

Langkah 3: Uji kod
Sekarang, kita boleh menggunakan beberapa ujian data untuk Mengesahkan bahawa kod kami adalah betul.

if __name__ == "__main__":
    # 测试数据
    data = [4, 10, 3, 5, 1]

    heap_sort(data)

    print("排序结果:", data)

Jalankan kod di atas, hasil output ialah: hasil pengisihan: [1, 3, 4, 5, 10], menunjukkan bahawa algoritma pengisihan timbunan adalah betul.

Ringkasan:
Isihan timbunan ialah algoritma isihan yang cekap dengan kerumitan masa O(nlogn). Mengambil kesempatan daripada sifat pokok binari yang lengkap bagi timbunan, kita boleh mencapai ini dengan membina timbunan maksimum dan melakukan pengisihan timbunan. Menggunakan bahasa Python, kita boleh melaksanakan algoritma isihan timbunan dengan menulis fungsi pelarasan timbunan (heapify), fungsi binaan timbunan maksimum (build_heap), dan fungsi isihan timbunan (heap_sort). Kod ujian membantu kami mengesahkan bahawa pelaksanaan kami adalah betul.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma jenis timbunan menggunakan Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!