Konsep dan kod pelaksanaan algoritma isihan timbunan dalam Python

Prasyarat untuk memahami algoritma isihan timbunan ialah mengetahui pokok binari yang lengkap dan struktur data timbunan. Algoritma isihan timbunan menggambarkan tatasusunan sebagai pokok binari yang lengkap, jadi ia juga dipanggil "timbunan".

Prinsip algoritma pengisihan timbunan

1 Menurut atribut timbunan maksimum, item terbesar dalam kumpulan data disimpan dalam nod akar

2 kedudukan ke-n), dan letakkan elemen terakhir item pokok, letakkan di ruang kosong.

3 Kurangkan saiz timbunan sebanyak 1.

4. Timbunkan elemen akar semula

5 Ulangi proses sehingga semua item dalam senarai diisih

Python melaksanakan algoritma isihan timbunan

指定数组arr= 1 12 9 5 6 10

def heapify(arr, n, i):
      largest = i
      l = 2 * i + 1
      r = 2 * i + 2
  
      if l < n and arr[i] < arr[l]:
          largest = l
  
      if r < n and arr[largest] < arr[r]:
          largest = r
  
heapifying
      if largest != i:
          arr[i], arr[largest] = arr[largest], arr[i]
          heapify(arr, n, largest)
  
def heapSort(arr):
      n = len(arr)
  
      for i in range(n//2, -1, -1):
          heapify(arr, n, i)
  
      for i in range(n-1, 0, -1):
          arr[i], arr[0] = arr[0], arr[i]
  
          heapify(arr, i, 0)
  
  arr = [1, 12, 9, 5, 6, 10]
  heapSort(arr)
  n = len(arr)
  print("Sorted array is")
  for i in range(n):
      print("%d " % arr[i], end=&#x27;&#x27;)

.

Atas ialah kandungan terperinci Konsep dan kod pelaksanaan algoritma isihan timbunan dalam Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!