Python'da Heaps Rehberi

Giriş

Her dakika uçuşların kalkış ve iniş yaptığı hareketli bir havaalanı hayal edin. Tıpkı hava trafik kontrolörlerinin uçuşları aciliyete göre önceliklendirmesi gibi, yığınlar da verileri belirli kriterlere göre yönetmemize ve işlememize yardımcı olarak en "acil" veya "önemli" veri parçasının her zaman en üstte erişilebilir olmasını sağlar.

Bu kılavuzda, yığınları sıfırdan anlamak için bir yolculuğa çıkacağız. Yığınların ne olduğunu ve doğal özelliklerini açığa çıkararak başlayacağız. Oradan Python'un kendi yığın uygulamasına geçeceğiz. heapq modülünü açın ve zengin işlevselliklerini keşfedin. Dolayısıyla, en yüksek (veya en düşük) öncelikli öğeye sıklıkla ihtiyaç duyulan dinamik bir veri kümesini verimli bir şekilde nasıl yöneteceğinizi merak ettiyseniz, bir fırsatla karşı karşıyasınız.

Yığın Nedir?

Yığınların kullanımına dalmadan önce anlamak isteyeceğiniz ilk şey şudur: yığın nedir. A heap, veri yapıları dünyasında ağaç tabanlı bir güç merkezi olarak öne çıkıyor ve özellikle düzeni ve hiyerarşiyi korumak. Deneyimsiz bir göz için ikili bir ağaca benzese de yapısındaki ve yönetim kurallarındaki nüanslar onu açıkça farklı kılıyor.

Bir yığının tanımlayıcı özelliklerinden biri onun doğasıdır. tam ikili ağaç. Bu, belki de sonuncusu hariç, ağacın her seviyesinin tamamen dolu olduğu anlamına gelir. Bu son seviyede düğümler soldan sağa doğru doldurulur. Böyle bir yapı, her bir öğenin dizideki konumu ağaçtaki yerleşimini yansıtacak şekilde, yığınların diziler veya listeler kullanılarak verimli bir şekilde temsil edilebilmesini ve değiştirilebilmesini sağlar.

Ancak bir yığının gerçek özü onun içinde yatmaktadır. sipariş. Bir In maksimum yığın, herhangi bir düğümün değeri, en büyük öğeyi kökte konumlandırarak alt öğelerinin değerlerini aşar veya onlara eşittir. Öte yandan, bir min öbek Bunun tersi prensipte çalışır: Herhangi bir düğümün değeri, alt öğelerinin değerlerinden daha az veya ona eşit olur; bu da en küçük öğenin kökte yer almasını sağlar.

İlerledikçe, yığınların bu doğal özelliklerinin verimli işlemleri nasıl mümkün kıldığını ve Python'un nasıl çalıştığını daha derinlemesine inceleyeceğiz. heapq modül, yığınları kodlama çalışmalarımıza sorunsuz bir şekilde entegre eder.

Yığınların Özellikleri ve Özellikleri

Yığınlar, benzersiz yapıları ve sıralama ilkeleriyle, onları çeşitli hesaplama senaryolarında paha biçilmez kılan bir dizi farklı özellik ve özelliği ortaya çıkarır.

Her şeyden önce yığınlar doğası gereği verimli. Ağaç tabanlı yapıları, özellikle tam ikili ağaç formatı, öncelikli öğelerin (maksimum veya minimum) eklenmesi ve çıkarılması gibi işlemlerin genellikle logaritmik zamanda gerçekleştirilebilmesini sağlar. O (log n). Bu verimlilik, öncelikli öğelere sık erişim gerektiren algoritmalar ve uygulamalar için bir nimettir.

Yığınların bir diğer önemli özelliği de bellek verimliliği. Yığınlar, alt veya üst düğümlere yönelik açık işaretçilere gerek kalmadan diziler veya listeler kullanılarak temsil edilebildiğinden, yerden tasarruf sağlarlar. Her öğenin dizideki konumu, ağaçtaki yerleşimine karşılık gelir ve öngörülebilir ve basit geçiş ve manipülasyona olanak tanır.

Yığınların, ister maksimum yığın ister minimum yığın olsun, sıralama özelliği şunları sağlar: kök her zaman en yüksek önceliğe sahip öğeyi tutar. Bu tutarlı sıralama, tüm yapıyı aramaya gerek kalmadan en yüksek öncelikli öğeye hızlı erişime olanak tanıyan şeydir.

Ayrıca yığınlar çok yönlü. İkili yığınlar (her ebeveynin en fazla iki çocuğunun olduğu) en yaygın olanı olsa da, yığınlar ikiden fazla çocuğa sahip olacak şekilde genelleştirilebilir. günlük yığınlar. Bu esneklik, belirli kullanım durumları ve performans gereksinimlerine göre ince ayar yapılmasına olanak tanır.

Son olarak yığınlar kendini ayarlayan. Öğeler eklendiğinde veya çıkarıldığında yapı, özelliklerini koruyacak şekilde kendini yeniden düzenler. Bu dinamik dengeleme, yığının her zaman temel işlemleri için optimize edilmiş kalmasını sağlar.

Python'un uygulanmasını ve pratik uygulamalarını daha derinlemesine araştırdıkça, yığınların gerçek potansiyeli önümüzde ortaya çıkacak.

Yığın Türleri

Tüm yığınlar eşit yaratılmamıştır. Sıralamalarına ve yapısal özelliklerine bağlı olarak yığınlar, her biri kendi uygulama ve avantajlarına sahip farklı türlere ayrılabilir. İki ana kategori şunlardır: maksimum yığın ve min öbek.

Bir kişinin en ayırt edici özelliği maksimum yığın herhangi bir düğümün değerinin, çocuklarının değerlerinden büyük veya ona eşit olmasıdır. Bu, yığındaki en büyük öğenin her zaman kökte bulunmasını sağlar. Böyle bir yapı, belirli öncelik kuyruğu uygulamalarında olduğu gibi, maksimum öğeye sıklıkla erişmeye ihtiyaç duyulduğunda özellikle faydalıdır.

Maksimum yığının karşılığı olan a min öbek Herhangi bir düğümün değerinin, çocuklarının değerlerinden küçük veya onlara eşit olmasını sağlar. Bu, yığının en küçük öğesini kökte konumlandırır. Minimum yığınlar, gerçek zamanlı veri işlemeyle ilgilenen algoritmalar gibi en az öğenin birincil öneme sahip olduğu senaryolarda çok değerlidir.

Bu birincil kategorilerin ötesinde yığınlar, dallanma faktörlerine göre de ayırt edilebilir:

Her ebeveynin en fazla iki çocuğa sahip olduğu ikili yığınlar en yaygın olanı olsa da, yığın kavramı ikiden fazla çocuğu olan düğümleri de kapsayacak şekilde genişletilebilir. İçinde günlük yığın, her düğümün en fazla d çocuklar. Bu varyasyon, belirli operasyonları hızlandırmak için ağacın yüksekliğini azaltmak gibi belirli senaryolar için optimize edilebilir.

Binom Yığını yinelemeli olarak tanımlanan bir dizi binom ağacıdır. Binom yığınları öncelik sırası uygulamalarında kullanılır ve verimli birleştirme işlemleri sunar.

Adını ünlü Fibonacci dizisinden alan Fibonacci yığını ikili veya binom yığınlara kıyasla birçok işlem için daha iyi amorti edilmiş çalışma süreleri sunar. Özellikle ağ optimizasyon algoritmalarında faydalıdırlar.

Python'un Heap Uygulaması – yığınq modül

Python, yığın işlemleri için yerleşik bir modül sunar; heapq modülü. Bu modül, geliştiricilerin özel bir uygulamaya ihtiyaç duymadan listeleri yığınlara dönüştürmesine ve çeşitli yığın işlemlerini gerçekleştirmesine olanak tanıyan yığınla ilgili işlevlerden oluşan bir koleksiyon sağlar. Bu modülün nüanslarına ve size yığınların gücünü nasıl getirdiğine bakalım.

The heapq modül ayrı bir yığın veri türü sağlamaz. Bunun yerine, normal Python listeleri üzerinde çalışan, bunları dönüştüren ve ele alan işlevler sunar. ikili yığınlar.

Bu yaklaşım hem bellek açısından verimlidir hem de Python'un mevcut veri yapılarıyla sorunsuz bir şekilde bütünleşir.

Bu şu demek oluyor yığınlar listeler halinde temsil edilir in heapq. Bu temsilin güzelliği basitliğindedir; sıfır tabanlı liste indeks sistemi örtülü bir ikili ağaç görevi görür. Konumdaki herhangi bir öğe için i, onun:

• Sol Çocuk pozisyonda 2*i + 1
• Sağ Çocuk pozisyonda 2*i + 2
• Ana Düğüm konumunda (i-1)//2

Bu örtülü yapı, ayrı bir düğüm tabanlı ikili ağaç temsiline gerek kalmamasını sağlayarak işlemleri basitleştirir ve bellek kullanımını minimum düzeye indirir.

Şunu belirtmek önemlidir: heapq modül varsayılan olarak minimum yığınlar oluşturur. Bu, en küçük öğenin her zaman kökte (veya listedeki ilk konumda) olduğu anlamına gelir. Maksimum yığına ihtiyacınız varsa, öğeleri şununla çarparak sırayı tersine çevirmeniz gerekir: -1 veya özel bir karşılaştırma işlevi kullanın.

Python'un heapq Modül, geliştiricilerin listelerde çeşitli yığın işlemleri gerçekleştirmesine olanak tanıyan bir dizi işlev sağlar.

Aşağıdaki bölümlerde, bu temel işlemlerin her birini derinlemesine inceleyeceğiz, mekanizmalarını ve kullanım örneklerini inceleyeceğiz.

Bir Listeyi Yığına Dönüştürme

The heapify() işlevi yığınla ilgili birçok görevin başlangıç ​​noktasıdır. Yinelenebilir bir liste alır (tipik olarak bir liste) ve minimum yığının özelliklerini karşılamak için öğelerini yerinde yeniden düzenler:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(data)
print(data)

Bu, geçerli bir minimum yığını temsil eden yeniden sıralanmış bir listenin çıktısını verecektir:

[1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

Heap'e Eleman Nasıl Eklenir?

The heappush() işlevi, yığının özelliklerini korurken yığına yeni bir öğe eklemenizi sağlar:

import heapq heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
print(heap)

Kodu çalıştırmak size min heap özelliğini koruyan öğelerin bir listesini verecektir:

[3, 5, 7]

En Küçük Öğeyi Yığından Çıkarma ve İade Etme

The heappop() işlev, yığındaki en küçük öğeyi (min yığınındaki kök) çıkarır ve döndürür. Kaldırıldıktan sonra listenin geçerli bir yığın olarak kalmasını sağlar:

import heapq heap = [1, 3, 5, 7, 9]
print(heapq.heappop(heap))
print(heap)

Bu, en küçük elemanın ve kalan listenin çıktısını verecektir:

1
[3, 7, 5, 9]

Burada, 1 en küçük elementtir heapve geri kalan liste, biz kaldırdıktan sonra bile yığın özelliğini korudu 1.

Yeni Bir Öğe Nasıl İtilir ve En Küçük Öğe Nasıl Patlatılır

The heappushpop() işlevi, yığına yeni bir öğe iten ve ardından yığından en küçük öğeyi çıkarıp döndüren birleşik bir işlemdir:

import heapq heap = [3, 5, 7, 9]
print(heapq.heappushpop(heap, 4)) print(heap)

Bu çıktı olacak 3en küçük öğeyi seçin ve yenisini yazdırın heap şimdi içeren liste 4 yığın özelliğini korurken:

3
[4, 5, 7, 9]

En Küçük Öğe Nasıl Değiştirilir ve Yeni Bir Öğe Nasıl İtilir?

The heapreplace() işlevi tek bir verimli işlemle en küçük öğeyi açar ve yığına yeni bir öğe iter:

import heapq heap = [1, 5, 7, 9]
print(heapq.heapreplace(heap, 4))
print(heap)

Bu yazdırır 1, en küçük öğe ve liste artık 4'ü içeriyor ve heap özelliğini koruyor:

1
[4, 5, 7, 9]

Python'un Heap'inde Çoklu Uç Noktaları Bulma

nlargest(n, iterable[, key]) ve nsmallest(n, iterable[, key]) işlevler yinelenebilir bir öğeden birden çok en büyük veya en küçük öğeyi almak için tasarlanmıştır. Yalnızca birkaç uç değere ihtiyaç duyduğunuzda yinelenebilirliğin tamamını sıralamaktan daha verimli olabilirler. Örneğin, aşağıdaki listeye sahip olduğunuzu ve listede üç en küçük ve üç en büyük değeri bulmak istediğinizi varsayalım:

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

Burada, nlargest() ve nsmallest() işlevler kullanışlı olabilir:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(heapq.nlargest(3, data)) print(heapq.nsmallest(3, data)) 

Bu size iki liste verecektir; biri en büyük üç değeri, diğeri ise listedeki en küçük üç değeri içerir. data liste:

[9, 6, 5]
[1, 1, 2]

Özel Yığınınızı Nasıl Oluşturabilirsiniz?

Python'un ise heapq modül, yığınlarla çalışmak için güçlü bir araç seti sağlar; varsayılan minimum yığın davranışının yeterli olmayabileceği senaryolar vardır. İster bir maksimum yığın uygulamak istiyor olun ister özel karşılaştırma işlevlerine dayalı olarak çalışan bir yığına ihtiyaç duyuyor olun, özel bir yığın oluşturmak aradığınız yanıt olabilir. Yığınların belirli ihtiyaçlara göre nasıl uyarlanacağını keşfedelim.

Max Heap kullanarak uygulama heapq

Varsayılan olarak, heapq oluşturur minimum yığın. Ancak basit bir numarayla bunu maksimum yığın uygulamak için kullanabilirsiniz. Buradaki fikir, elemanların sırasını aşağıdakilerle çarparak tersine çevirmektir. -1 bunları yığına eklemeden önce:

import heapq class MaxHeap: def __init__(self): self.heap = [] def push(self, val): heapq.heappush(self.heap, -val) def pop(self): return -heapq.heappop(self.heap) def peek(self): return -self.heap[0]

Bu yaklaşımla, en büyük sayı (mutlak değer açısından) en küçük sayı haline gelir ve heapq Maksimum yığın yapısını korumak için çalışır.

Özel Karşılaştırma İşlevlerine Sahip Yığınlar

Bazen yalnızca öğelerin doğal sırasına göre karşılaştırılmayan bir yığına ihtiyacınız olabilir. Örneğin, karmaşık nesnelerle çalışıyorsanız veya belirli sıralama kriterleriniz varsa, özel bir karşılaştırma işlevi gerekli hale gelir.

Bunu başarmak için öğeleri, karşılaştırma işleçlerini geçersiz kılan bir yardımcı sınıfa sarabilirsiniz:

import heapq class CustomElement: def __init__(self, obj, comparator): self.obj = obj self.comparator = comparator def __lt__(self, other): return self.comparator(self.obj, other.obj) def custom_heappush(heap, obj, comparator=lambda x, y: x < y): heapq.heappush(heap, CustomElement(obj, comparator)) def custom_heappop(heap): return heapq.heappop(heap).obj

Bu kurulumla herhangi bir özel karşılaştırıcı fonksiyonunu tanımlayabilir ve bunu heap ile kullanabilirsiniz.

Sonuç

Yığınlar birçok işlem için öngörülebilir performans sunarak onları önceliğe dayalı görevler için güvenilir bir seçim haline getirir. Ancak, eldeki uygulamanın özel gerekliliklerini ve özelliklerini dikkate almak önemlidir. Bazı durumlarda yığının uygulamasında ince ayar yapmak veya hatta alternatif veri yapılarını tercih etmek daha iyi gerçek dünya performansı sağlayabilir.

Yığınlar, daha önce de incelediğimiz gibi, başka bir veri yapısından daha fazlasıdır. Verimlilik, yapı ve uyarlanabilirliğin birleşimini temsil ederler. Temel özelliklerinden Python'daki uygulamalarına kadar heapq modül, yığınlar, özellikle öncelik merkezli olanlar olmak üzere sayısız hesaplama zorluğuna güçlü bir çözüm sunar.

• SEO Destekli İçerik ve Halkla İlişkiler Dağıtımı. Bugün Gücünüzü Artırın.
• PlatoData.Network Dikey Üretken Yapay Zeka. Kendine güç ver. Buradan Erişin.
• PlatoAiStream. Web3 Zekası. Bilgi Genişletildi. Buradan Erişin.
• PlatoESG. karbon, temiz teknoloji, Enerji, Çevre, Güneş, Atık Yönetimi. Buradan Erişin.
• PlatoSağlık. Biyoteknoloji ve Klinik Araştırmalar Zekası. Buradan Erişin.
• Kaynak: https://stackabuse.com/guide-to-heaps-in-python/