Python - Yığınlar

Yığın, her bir ana düğümün alt düğümünden daha az veya ona eşit olduğu özel bir ağaç yapısıdır. Sonra buna Min Yığın denir. Her bir ana düğüm, alt düğümünden büyükse veya ona eşitse, buna maksimum yığın denir. Daha yüksek ağırlığa sahip kuyruk maddesine işlemede daha fazla öncelik verildiği öncelik sıralarını uygulamak çok kullanışlıdır. Yığınlar hakkında ayrıntılı bir tartışma burada web sitemizde mevcuttur. Veri yapısında yeniyseniz lütfen önce onu inceleyin. Bu bölümde, python kullanarak yığın veri yapısının uygulanmasını göreceğiz.

Yığın Oluşturun

Bir yığın, python'un heapq adlı dahili kitaplığı kullanılarak oluşturulur. Bu kütüphane, yığın veri yapısı üzerinde çeşitli işlemleri gerçekleştirmek için ilgili işlevlere sahiptir. Aşağıda bu işlevlerin bir listesi bulunmaktadır.

  • heapify - Bu işlev, normal bir listeyi bir yığına dönüştürür. Ortaya çıkan yığında, en küçük öğe 0 dizin konumuna itilir. Ancak geri kalan veri öğelerinin sıralanması gerekmez.
  • heappush - Bu işlev, geçerli öbeği değiştirmeden öbeğe bir öğe ekler.
  • heappop - Bu işlev, yığından en küçük veri öğesini döndürür.
  • heapreplace - Bu işlev, en küçük veri öğesini işlevde sağlanan yeni bir değerle değiştirir.

Yığın Oluşturmak

Yığın, basitçe öbekleme işleviyle bir öğe listesi kullanılarak oluşturulur. Aşağıdaki örnekte, bir eleman listesi sağlıyoruz ve öbekleme işlevi, en küçük elemanı ilk konuma getiren elemanları yeniden düzenler.

import heapq

H = [21,1,45,78,3,5]
# Use heapify to rearrange the elements
heapq.heapify(H)
print(H)

Yukarıdaki kod çalıştırıldığında, aşağıdaki sonucu verir -

[1, 3, 5, 78, 21, 45]

Yığın içine ekleme

Bir yığına bir veri öğesi eklemek, öğeyi her zaman son dizine ekler. Ancak, yeni eklenen öğeyi yalnızca değeri en küçükse ilk dizine getirmek için öbekleme işlevini tekrar uygulayabilirsiniz. Aşağıdaki örnekte 8 sayısını ekliyoruz.

import heapq
H = [21,1,45,78,3,5]
# Covert to a heap
heapq.heapify(H)
print(H)
# Add element
heapq.heappush(H,8)
print(H)

Yukarıdaki kod çalıştırıldığında, aşağıdaki sonucu verir -

[1, 3, 5, 78, 21, 45]
[1, 3, 5, 78, 21, 45, 8]

Yığından çıkarılıyor

Bu işlevi kullanarak öğeyi ilk dizinden kaldırabilirsiniz. Aşağıdaki örnekte, işlev her zaman 1. dizin konumundaki öğeyi kaldıracaktır.

import heapq

H = [21,1,45,78,3,5]
# Create the heap

heapq.heapify(H)
print(H)

# Remove element from the heap
heapq.heappop(H)

print(H)

Yukarıdaki kod çalıştırıldığında, aşağıdaki sonucu verir -

[1, 3, 5, 78, 21, 45]
[3, 21, 5, 78, 45]

Bir Yığın İçinde Değiştirme

Yığın değiştirme işlevi her zaman yığının en küçük öğesini kaldırır ve yeni gelen öğeyi herhangi bir sıra ile sabitlenmemiş bir yere ekler.

import heapq

H = [21,1,45,78,3,5]
# Create the heap

heapq.heapify(H)
print(H)

# Replace an element
heapq.heapreplace(H,6)
print(H)
[1, 3, 5, 78, 21, 45]
[3, 6, 5, 78, 21, 45]