Yumuşak yığın - Soft heap

Gelen bilgisayar bilimleri , bir yumuşak yığın basit bir varyant olan yığın veri yapısı sabit sahiptir itfa edilmiş operasyonların 5 türleri için zaman karmaşıklığı. Bu, yığın içindeki en fazla sabit sayıda değerin anahtarlarını dikkatlice "bozarak" (artırarak) elde edilir. Sabit zamanlı işlemler şunlardır:

• oluştur ( S ): Yeni bir yumuşak yığın oluştur
• ekle ( S , x ): Yumuşak bir yığına bir öğe ekleyin
• meld ( S , S ' ): İki yumuşak yığının içeriğini tek bir yerde birleştirin,
• delete ( S , x ): Yumuşak bir öbekten bir öğeyi siler
• findmin ( S ): Yumuşak yığındaki minimum anahtarla elemanı alın

Fibonacci yığınları gibi diğer yığınlar , bu sınırların çoğuna herhangi bir bozulma olmadan ulaşır, ancak kritik silme işleminde sabit zaman sınırı sağlayamaz . Bozulma miktarı, bir ε parametresinin seçilmesiyle kontrol edilebilir, ancak bu ne kadar düşük ayarlanırsa, ins hata oranı için daha fazla zaman eklemesi ( O (log 1 / ε)) gerektirir.

Daha kesin olarak, yumuşak yığının sunduğu garanti şudur: 0 ile 1/2 arasında sabit bir değer için ε , herhangi bir noktada öbekte en fazla ε * n bozuk anahtar olacaktır, burada n sayıdır şimdiye kadar eklenen öğe sayısı. Bunun, şu anda yığında bulunan anahtarların yalnızca sabit bir yüzdesinin bozuk olduğunu garanti etmediğini unutmayın : şanssız bir ekleme ve silme dizisinde, öbekteki tüm öğelerde bozuk anahtarlar olabilir. Benzer şekilde, findmin ve delete ile öbekten çıkarılan bir dizi öğede , anahtarların yalnızca sabit bir yüzdesinde bozuk olacağına dair hiçbir garantimiz yok : şanssız bir senaryoda, öbekten yalnızca bozuk öğeler çıkarılır.

Yumuşak yığın, 2000 yılında Bernard Chazelle tarafından tasarlandı . Yapıdaki "bozulma" terimi, Chazelle'in yumuşak bir yığın içinde "araba paylaşımı" dediği şeyin sonucudur. Yazılım yığınındaki her düğüm, bağlantılı bir anahtar listesi ve bir ortak anahtar içerir. Ortak anahtar, bağlantılı listedeki anahtarların değerlerinin üst sınırıdır. Bağlantılı listeye bir anahtar eklendikten sonra bozuk olarak kabul edilir çünkü değeri yazılım öbek işlemlerinin hiçbirinde bir daha asla alakalı değildir: yalnızca ortak anahtarlar karşılaştırılır. Yumuşak yığınları "yumuşak" yapan şey budur; içine koyduğunuz belirli bir değerin bozulup bozulmayacağından emin olamazsınız. Bu bozulmaların amacı , verilerin bilgi entropisini etkili bir şekilde düşürmek , veri yapısının yığınlarla ilgili bilgi-teorik engelleri aşmasını sağlamaktır.

Başvurular

Sınırlamaları ve öngörülemeyen doğalarına rağmen, yumuşak yığınlar deterministik algoritmaların tasarımında kullanışlıdır. Minimum yayılan ağaç bulmak için bugüne kadarki en iyi karmaşıklığı elde etmek için kullanıldılar . Ayrıca, yerleştirme sıralamanın hızlı olduğu bir durumda, her öğeyi nihai konumuna yakın yerleştiren algoritmalar olan yakın sıralama algoritmalarının yanı sıra optimum bir seçim algoritmasını kolayca oluşturmak için de kullanılabilirler .

En basit örneklerden biri seçim algoritmasıdır. Bulmak istiyoruz Say k bir grup büyük inci n numaralar. Önce 1/3 hata oranı seçiyoruz; yani, yerleştirdiğimiz anahtarların en fazla% 33'ü bozulacaktır. Şimdi, tüm n öğeyi öbeğe yerleştiriyoruz - orijinal değerlere "doğru" anahtarlar ve yığın içinde depolanan değerlere "depolanan" anahtarlar diyoruz. Bu noktada, en fazla n / 3 anahtar bozuktur, yani en fazla n / 3 anahtar "doğru" anahtardan daha büyük olan "depolanmış" anahtardır, diğer tüm anahtarlar için saklanan anahtar doğru anahtara eşittir.

Daha sonra, minimum elemanı öbekten n / 3 kez siliyoruz (bu, "depolanmış" anahtara göre yapılır). Şimdiye kadar yaptığımız toplam ekleme sayısı hala n olduğundan , yığın içinde hala en çok n / 3 bozuk anahtar var. Buna göre yığın içinde kalan anahtarların en az 2 n / 3 - n / 3 = n / 3'ü bozuk değildir.

Kaldırdığımız öğeler arasında en büyük doğru anahtara sahip öğe L olsun . L' nin depolanan anahtarı muhtemelen doğru anahtardan daha büyüktür (eğer L bozuksa) ve bu daha büyük değer bile yığındaki kalan öğelerin tüm depolanan anahtarlarından daha küçüktür (minimumları kaldırırken). Bu nedenle, L' nin doğru anahtarı , yumuşak yığınta kalan n / 3 bozulmamış öğelerden daha küçüktür . Böylece L , elementleri% 33 /% 66 ile% 66 /% 33 arasında bir yere böler. Bu daha sonra yaklaşık dizi bölme L kullanılarak bölüm algoritmayı hızlı sıralama ve daha az sayı grubu ya da yine aynı algoritma uygulamak L ya da daha fazla sayıda grubu L 2 aşabilir, ikisi de n / 3 elemanları. Her ekleme ve silme, O (1) amortisman süresi gerektirdiğinden, toplam deterministik süre T ( n ) = T (2 n / 3) + O ( n ) 'dir. Kullanma durum 3 arasında bölmek-böl nüks için ana teoremi (ε = 1 ve c = 2/3), bildiğimiz T ( n ) = Θ ( n ).

Son algoritma şuna benzer:

function softHeapSelect(a[1..n], k)
    if k = 1 then return minimum(a[1..n])
    create(S)
    for i from 1 to n
        insert(S, a[i])
    for i from 1 to n/3
        x := findmin(S)
        delete(S, x)
    xIndex := partition(a, x)  // Returns new index of pivot x
    if k < xIndex
        softHeapSelect(a[1..xIndex-1], k)
    else
        softHeapSelect(a[xIndex..n], k-xIndex+1)

Referanslar

• Chazelle, Bernard (Kasım 2000). "Yumuşak yığın: optimum hata oranına sahip yaklaşık bir öncelik sırası" (PDF) . J. ACM . 47 (6): 1012–1027. CiteSeerX  10.1.1.5.9705 . doi : 10.1145 / 355541.355554 .
• Kaplan, Haim; Zwick, Uri (2009). "Chazelle'in yumuşak yığınlarının daha basit bir uygulaması ve analizi" . Ayrık Algoritmalar Üzerine Ondokuzuncu Yıllık ACM-SIAM Sempozyumu Bildirileri . Endüstriyel ve Uygulamalı Matematik Derneği. sayfa 477–485. CiteSeerX  10.1.1.215.6250 . doi : 10.1137 / 1.9781611973068.53 . ISBN 978-0-89871-680-1.