Build heap ve sırala

Diziden yığın kurup teker teker çıkararak sıralamayı öğrenirsin.

Build heap ve sırala

Heap sort iki aşamada çalışır. Önce diziyi max-heap yaparız: yaprak olmayan son düğümden köke kadar her i için heapify(arr, n, i) çağrılır. Bu O(n).

Sonra kök (en büyük) son elemanla takas edilir, heap boyutu bir azalır ve kök için heapify çağrılır. Bu n-1 kez tekrarlanır; her biri O(log n).

Toplam: O(n log n). Yerinde çalışır, kararlı değildir.

Kökü sona taşı

Max-heap kurulduğunda kök arr[0] en büyük elemandır. Onu arr[n-1] ile takas ederiz; en büyük eleman doğru yerine yerleşir.

Sonra heap boyutu n-1'e düşürülür ve kök heapify edilir. Bu, ikinci en büyüğü tepeye çıkarır. Tekrar tekrar.

Her takas + heapify, bir elemanı yerine koyar. n adımda dizi sıralanır.

Uygulama Heap sort

heap_sort(arr) yaz. Önce max-heap kur, sonra kökü sona taşıyıp heapify et. arr=[5,2,8,1,9]; heap_sort(arr); print(arr) ile [1, 2, 5, 8, 9] yazdır.

Örnek çözümü göster

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
def heap_sort(arr):
    # Build heap ve sırala
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
arr = [5, 2, 8, 1, 9]
heap_sort(arr)
print(arr)

Kendini test et

Build heap ve sırala: kavramları eşleştir

Build heap

O(n)
Sıralama

O(n log n)
Bellek

O(1) ek
Kararlı

Hayır
Build heap kaç iş yapar?
- O(1)
- O(n^2)
- O(log n)
- O(n)
Cevabı göster

O(n) — O(n)

Takas hedefi

arr[0], arr[i] = arr[i], ____

Cevabı göster

arr[0], arr[i] = arr[i], arr[0]

Sıradaki ders: Özet - Heap sort

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler