Yığın (veri yapısı) - Heap (data structure)

Düğüm anahtarlarının 1 ile 100 arasında tam sayılar olduğu ikili maksimum yığın örneği

Olarak bilgisayar biliminin , bir yığın bir uzmanlaşmış ağaç tabanlı veri yapısı hemen hemen tamamen ağaç esas olduğu tatmin yığın özelliği : a maksimum yığın , herhangi bir için düğüm C, P C'lik bir üst düğümü ise, o zaman anahtar ( değeri ) C'nin anahtarından büyük veya ona eşittir. Bir min yığınında , P'nin anahtarı C'nin anahtarından küçük veya ona eşittir. Yığının "en üstündeki" düğüm ebeveynler) kök düğüm olarak adlandırılır .

Yığın, öncelik sırası adı verilen soyut bir veri türünün maksimum düzeyde verimli bir uygulamasıdır ve aslında, nasıl uygulanabileceklerinden bağımsız olarak, öncelik sıralarına genellikle "yığınlar" denir. Bir yığında, en yüksek (veya en düşük) öncelikli öğe her zaman kökte depolanır. Ancak, bir yığın sıralanmış bir yapı değildir; kısmen sipariş edilmiş olarak kabul edilebilir. Bir yığın, en yüksek (veya en düşük) önceliğe sahip nesneyi tekrar tekrar kaldırmak gerektiğinde yararlı bir veri yapısıdır.

Bir yığının yaygın bir uygulaması , ağacın bir ikili ağaç olduğu ikili yığındır (şekle bakın). Yığın veri yapısı, özellikle ikili yığın, 1964 yılında JWJ Williams tarafından yığın sıralama algoritması için bir veri yapısı olarak tanıtıldı . Yığınlar, Dijkstra'nın algoritması gibi birkaç verimli grafik algoritmasında da çok önemlidir . Bir yığın tam bir ikili ağaç olduğunda, mümkün olan en küçük yüksekliğe sahiptir - N düğümlü bir yığın ve her düğüm için bir dal her zaman bir N yüksekliğe sahiptir.

Grafikte gösterildiği gibi, kardeşler veya kuzenler arasında ima edilen bir sıralama ve sıralı bir geçiş için ima edilen bir sıra olmadığına dikkat edin (örneğin, bir ikili arama ağacında olacağı gibi ). Yukarıda bahsedilen yığın ilişkisi yalnızca düğümler ile onların ebeveynleri, büyükanne ve büyükbabaları vb. arasında geçerlidir. Her düğümün sahip olabileceği maksimum çocuk sayısı, yığın türüne bağlıdır.

Operasyonlar

Yığınları içeren yaygın işlemler şunlardır:

Temel
  • find-max (veya find-min ): sırasıyla bir maksimum yığının maksimum öğesini veya bir minimum yığının minimum öğesini bulun (aka peek )
  • insert : yığına yeni bir anahtar ekleme (aka, push )
  • özüt-maks (veya özüt-min ): yığından çıkarıldıktan sonra bir maksimum yığından [veya bir minimum yığından minimum değer] maksimum değerin düğümünü döndürür (aka, pop )
  • delete-max (veya delete-min ): sırasıyla bir maksimum yığının (veya minimum yığının) kök düğümünü kaldırma
  • replace : pop root ve yeni bir tuşa basın. Pop ve ardından Push'tan daha verimli, çünkü iki kez değil, yalnızca bir kez dengeleme gerekir ve sabit boyutlu yığınlar için uygundur.
oluşturma
  • create-heap : boş bir yığın oluştur
  • heapify : verilen eleman dizisinden bir yığın oluşturun
  • birleştirme ( birleşim ): orijinal yığınları koruyarak her ikisinin tüm öğelerini içeren geçerli bir yeni yığın oluşturmak için iki yığını birleştirmek.
  • meld : orijinal yığınları yok ederek, her ikisinin de tüm öğelerini içeren geçerli bir yeni yığın oluşturmak için iki yığını birleştirmek.
İnceleme
  • size : yığındaki öğelerin sayısını döndürür.
  • is-empty : yığın boşsa true, aksi takdirde false döndürür.
Dahili
  • artırma anahtarı veya azaltma anahtarı : sırasıyla bir maksimum veya minimum yığın içindeki bir anahtarı güncelleme
  • sil : rastgele bir düğümü siler (ardından son düğümü hareket ettirir ve yığını korumak için eleme yapar)
  • eleme : ağaçtaki bir düğümü gerektiği kadar yukarı hareket ettirin; eklemeden sonra yığın durumunu geri yüklemek için kullanılır. Düğüm, bir elekte olduğu gibi doğru seviyeye ulaşana kadar ağaçta yukarı doğru hareket ettiği için "eleme" olarak adlandırılır .
  • eleme : eleme işlemine benzer şekilde ağaçta bir düğümü aşağı hareket ettirin; silme veya değiştirme işleminden sonra yığın durumunu geri yüklemek için kullanılır.

uygulama

Yığınlar genellikle bir dizi ile şu şekilde uygulanır:

  • Dizideki her öğe, yığının bir düğümünü temsil eder ve
  • Ebeveyn / çocuk ilişkisi, dizideki öğelerin dizinleri tarafından örtük olarak tanımlanır .
Düğüm anahtarlarının 1'den 100'e kadar tamsayılar olduğu ve bir dizide nasıl saklanacağı ile tam bir ikili maksimum yığın örneği.

Bir İçin ikili yığın , dizideki ilk endeks kök öğesi içeriyor. Dizinin sonraki iki dizini, kökün alt öğelerini içerir. Sonraki dört dizin, kökün iki alt düğümünün dört çocuğunu içerir, vb. Bu nedenle, i dizininde bir düğüm verildiğinde , onun çocukları 2i + 1 ve 2i + 2 dizinlerindedir ve ebeveyni ⌊(i−1)/2⌋ dizinindedir . Bu basit indeksleme şeması, ağacı "yukarı" veya "aşağı" hareket ettirmeyi verimli hale getirir.

Bir yığının dengelenmesi, eleme veya eleme işlemleri (düzensiz olan elemanların değiştirilmesi) ile yapılır. Fazladan bellek gerektirmeden (örneğin düğümler için) bir diziden bir yığın oluşturabileceğimiz için, bir diziyi yerinde sıralamak için yığın sıralama kullanılabilir.

Bir öbek içine bir öğe eklendikten veya öbekten silindikten sonra öbek özelliği ihlal edilebilir ve öbek, dizi içindeki ögeleri değiştirerek yeniden dengelenmelidir.

Farklı türdeki yığınlar işlemleri farklı şekilde
uygulasalar da , en yaygın yol aşağıdaki gibidir: Ekleme: Yeni öğeyi yığının sonuna, kullanılabilir ilk boş alana ekleyin. Bu, öbek özelliğini ihlal edecektir, bu nedenle ögeler , öbek özelliği yeniden kurulana kadar yukarı kaydırılır (veya yüzer işlem).
Çıkarma: Kökü kaldırın ve yığının son öğesini köke ekleyin; bu, yığın özelliğini ihlal edecektir, bu nedenle, yığın özelliğini (veya havuz işlemini) yeniden oluşturmak için aşağı eleyin . Böylece değiştirme, kökü silerek ve yeni öğeyi köke koyarak ve aşağı eleyerek yapılır, pop (son öğenin aşağı doğru elemesi) ve ardından itme (yeni öğenin yukarı kaldırılması) ile karşılaştırıldığında bir eleme adımından kaçınılır.

Belirli bir öğe dizisinden ikili (veya d -ary) bir yığının oluşturulması, klasik Floyd algoritması kullanılarak doğrusal zamanda gerçekleştirilebilir ve en kötü durum karşılaştırma sayısı 2 N − 2 s 2 ( N ) − e 2 ( N (ikili bir yığın için)), s 2 ( K ) 'in ikili gösterimi her basamak toplamıdır N ve e 2 ( N ) ait ana çarpanlara içinde 2 üssüdür N . Bu, log-doğrusal olan orijinal olarak boş bir yığına ardışık eklemeler dizisinden daha hızlıdır.

Varyantlar

Varyantlar için teorik sınırların karşılaştırılması

İşte çeşitli yığın veri yapılarının zaman karmaşıklıkları . İşlev adları bir maksimum yığın olduğunu varsayar. " O ( f )" ve " Θ ( f )" nin anlamı için Büyük O notasyonuna bakınız .

Operasyon maksimum bul maksimum silme sokmak artış anahtarı birleştirmek
İkili Θ (1) Θ (log  n ) O (günlük  n ) O (günlük  n ) Θ ( n )
Solcu Θ (1) Θ (günlük n ) Θ (günlük n ) O (günlük n ) Θ (günlük n )
binom Θ (1) Θ (günlük n ) Θ (1) Θ (günlük n ) O (günlük  n )
Fibonacci Θ (1) O (günlük  n ) Θ (1) Θ (1) Θ (1)
Eşleştirme Θ (1) O (günlük n ) Θ (1) o (log  n ) Θ (1)
brodal Θ (1) O (günlük  n ) Θ (1) Θ (1) Θ (1)
Sıra eşleştirme Θ (1) O (günlük n ) Θ (1) Θ (1) Θ (1)
katı Fibonacci Θ (1) O (günlük n ) Θ (1) Θ (1) Θ (1)
2-3 yığın O (günlük n ) O (günlük n ) O (günlük n ) Θ (1) ?

Uygulamalar

Yığın veri yapısının birçok uygulaması vardır.

  • Heapsort : Yerinde olmak ve ikinci dereceden en kötü durum senaryoları olmadan en iyi sıralama yöntemlerinden biri.
  • Seçim algoritmaları : Bir yığın, sabit zamanda minimum veya maksimum öğeye erişim sağlar ve diğer seçimler (medyan veya kth-element gibi) bir yığındaki veriler üzerinde lineer zamanda yapılabilir.
  • Grafik algoritmaları : Yığınları dahili çapraz veri yapıları olarak kullanarak, çalışma süresi polinom sırasına göre azaltılacaktır. Bu tür problemlere örnek olarak Prim'in minimal yayılan ağaç algoritması ve Dijkstra'nın en kısa yol algoritması verilebilir .
  • Öncelik Sırası : Öncelik sırası, "liste" veya "harita" gibi soyut bir kavramdır; Bir listenin bağlantılı bir liste veya dizi ile uygulanabilmesi gibi, bir öncelik sırası da bir yığın veya çeşitli başka yöntemlerle uygulanabilir.
  • K-way birleştirme : Bir yığın veri yapısı, önceden sıralanmış birçok girdi akışını tek bir sıralanmış çıktı akışında birleştirmek için kullanışlıdır. Birleştirme ihtiyacına örnekler, günlük yapılandırılmış birleştirme ağacı gibi dağıtılmış verilerden harici sıralama ve akış sonuçlarını içerir. İç döngü min elemanını alıyor, karşılık gelen girdi akışı için bir sonraki elemanla değiştiriyor ve ardından bir eleme yığını işlemi yapıyor. (Alternatif olarak değiştirme işlevi.) (Öncelik kuyruğunun çıkarma-max ve ekleme işlevlerini kullanmak çok daha az verimlidir.)
  • Sıra istatistikleri : Yığın veri yapısı, bir dizideki en küçük (veya en büyük) öğeyi verimli bir şekilde bulmak için kullanılabilir.

Programlama dili uygulamaları

  • C ++ Standart kütüphane sağlar make_heap , push_heap ve pop_heap rastgele erişimli ameliyat (genellikle ikili yığınları olarak uygulanır) kümeler için algoritmaları, yineleyicileri . Yineleyicileri bir diziye referans olarak ele alır ve diziden yığına dönüştürmeyi kullanır. Ayrıca , bu tesisleri kapsayıcı benzeri bir sınıfa saran kapsayıcı bağdaştırıcısı Priority_queue sağlar . Ancak, değiştirme, eleme/yukarı eleme veya azaltma/artırma tuşları işlemleri için standart bir destek yoktur.
  • Boost C ++ kütüphaneleri bir yığınları kütüphane yer almaktadır. STL'den farklı olarak, azaltma ve artırma işlemlerini destekler ve ek yığın türlerini destekler: özellikle d -ary, binom, Fibonacci, eşleştirme ve eğri yığınlarını destekler.
  • Bir yoktur jenerik yığın uygulama için C ve C ++ ile D-li yığın ve B-yığın desteği. STL benzeri bir API sağlar.
  • D programlama dilinin standart kitaplığı , D'nin aralıkları cinsinden uygulanan std.container.BinaryHeap öğesini içerir . Örnekler, herhangi bir rastgele erişim aralığından oluşturulabilir . BinaryHeap , D'nin yerleşik foreach ifadeleriyle yinelemeye ve std.algorithm paketinin aralık tabanlı API'siyle entegrasyona izin veren bir giriş aralığı arabirimi sunar .
  • Java (sürüm 1.5 beri) platformu sınıfıyla bir ikili yığın uygulamasını sağlar java.util.PriorityQueueyılında Java Koleksiyonları Framework . Bu sınıf, varsayılan olarak bir min-yığın uygular; bir maksimum yığın uygulamak için programcı özel bir karşılaştırıcı yazmalıdır. Değiştirme, eleme/yukarı eleme veya azaltma/artırma tuşu işlemleri için destek yoktur.
  • Python , ikili bir yığın kullanarak bir öncelik sırası uygulayan bir heapq modülüne sahiptir. Kitaplık, k-yollu birleştirmeyi desteklemek için bir yığın yeri işlevi sunar.
  • PHP , Standart PHP Kitaplığında sürüm 5.3'ten itibaren hem maksimum yığına ( SplMaxHeap ) hem de minimum yığına ( SplMinHeap ) sahiptir.
  • Perl içinde, ikili binom ve Fibonacci yığınları desteği olup Öbek dağılımına uygun CPAN .
  • Git dili içeren yığın keyfi bir tip tatmin, belirli bir arayüz üzerinde işlem yığın algoritmalarla paketi. Bu paket değiştirme, eleme/yukarı eleme veya azaltma/artırma tuşları işlemlerini desteklemez.
  • Apple'ın Core Foundation kitaplığı bir CFBinaryHeap yapısı içerir .
  • Pharo , Collections-Sequenceable paketinde bir dizi test senaryosu ile birlikte bir yığın uygulamasına sahiptir. Zamanlayıcı olay döngüsünün uygulanmasında bir yığın kullanılır.
  • Pas programlama dili bir ikili max-yığın uygulanmasını sahiptir BinaryHeap içinde, koleksiyonları standart kütüphanenin modülü.

Ayrıca bakınız

Referanslar

Dış bağlantılar

  • Wolfram MathWorld'de Yığın
  • Temel yığın algoritmalarının nasıl çalıştığının açıklaması
  • Bentley, Jon Louis (2000). Programlama İncileri (2. baskı). Addison Wesley. s. 147-162. ISBN'si 0201657880.