Maksimum yığın ve dengeli BST kullanarak öncelik kuyruğunu uygulama

Question

Dengeli BST ve maksimum yığın, hem ekleme hem de silme işlemlerini gerçekleştirir O(logn). Bununla birlikte, maksimum yığın içinde maksimum değer bulmak, O(1)ancak bu O(logn)dengeli BST'dedir.

Bir maksimum yığın içindeki maksimum değeri kaldırırsak, O(logn)bu bir silme işlemi olduğu için alır .

Dengeli BST'de, maksimum elemanı silme = maksimum değeri bulma + silme; logn + logn'ye eşittir O(logn). Yani dengeli BST'deki maksimum değeri silmek bile O(logn).

Okudum böyle bir max heap uygulamasının bir öncelik sırası olduğunu ve birincil amacı her kuyruktan çıkarma işlemi için maksimum değeri kaldırmaktır. Maksimum öğeyi silmek O(logn)hem maksimum yığın hem de dengeli BST içinse, aşağıdaki sorularım var

• Öncelik kuyruğundaki maksimum yığının amacı, tam aranabilir dengeli BST kullanmaktan çok uygulaması kolay olduğu için nedir?

• Dengeleme faktörü hesaplaması olmadığından, maksimum yığın dengesiz ikili ağaç olarak adlandırılabilir mi?

• Her dengeli BST bir öncelik kuyruğu olarak kullanılabilir ve O(logn)maksimum yığın araması O(n)doğru olsa da hangisi aranabilir ?

En kötü durum için tüm zaman karmaşıklıkları hesaplanır. Herhangi bir yardım çok takdir edilmektedir.

Answer 1

Öncelik kuyruğundaki maksimum yığının amacı, tam aranabilir dengeli BST kullanmaktan çok uygulaması kolay olduğu için nedir?

Bir yığının bazı avantajları şunlardır:

• Sıralanmamış bir girdi dizisi verildiğinde , bir BST'nin O (nlogn) zamanına ihtiyacı varken, O (n) zamanında bir yığın oluşturulabilir .

• İlk girdi bir dizi ise, aynı dizi yığın görevi görebilir, yani onun için fazladan belleğe gerek yoktur. Dizideki verileri yerinde kullanarak bir BST oluşturmanın yolları düşünülebilirse de, bu oldukça tuhaf olacaktır (ilkel türler için) ve daha fazla işlem yükü sağlar. Bir BST genellikle sıfırdan oluşturulur ve veriler oluşturulurken düğümlere kopyalanır.

  İlginç gerçek: sıralı bir dizi aynı zamanda bir yığındır, bu nedenle girdinin sıralandığı biliniyorsa, öbek oluşturmak için hiçbir şey yapılmasına gerek yoktur.

• Bir yığın, çapraz referansları depolamaya gerek kalmadan bir dizi olarak depolanabilirken , bir BST genellikle sol ve sağ referanslara sahip düğümlerden oluşur. Bunun en az iki sonucu vardır:

  • Bir BST için kullanılan bellek, bir yığından yaklaşık 3 kat daha büyüktür.
  • Birkaç işlem hem yığın hem de BST için aynı zaman karmaşıklığına sahip olsa da, bir BST'yi uyarlamak için ek yük çok daha büyüktür, bu nedenle bu işlemler için harcanan gerçek zaman BST durumunda (sabit) bir faktördür.

Dengeleme faktörü hesaplaması olmadığından, maksimum yığın dengesiz ikili ağaç olarak adlandırılabilir mi?

Bir yığın aslında tam bir ikili ağaçtır , bu yüzden her zaman olabildiğince dengelidir: yapraklar her zaman son veya bir ama son seviyede konumlandırılacaktır. Kendi kendini dengeleyen bir BST (AVL, kırmızı-siyah, ... gibi), yaprakların genellikle üç seviyede veya daha fazlasında ortaya çıktığı yüksek seviyedeki dengelemeyi geçemez.

Her dengeli BST bir öncelik kuyruğu olarak kullanılabilir ve hangisi O (logn) içinde de aranabilir ancak maksimum yığın araması O (n) doğru mu?

Evet bu doğru. Dolayısıyla, uygulamanın arama özelliğine ihtiyacı varsa, bir BST daha üstündür.

Answer 2

Öncelik kuyruğundaki maksimum yığının amacı, tam aranabilir dengeli BST kullanmaktan çok uygulaması kolay olduğu için nedir?

Hayır! Maksimum yığın daha iyi uyuyor, çünkü bir sonraki (önceliğe göre) öğeyi ASAP, O (1) zamanında döndürmek için dikkatli bir şekilde ayarlandı. Mümkün olan en basit öncelik kuyruğundan istediğiniz şey budur.

Dengeleme faktörü hesaplaması olmadığından, maksimum yığın dengesiz ikili ağaç olarak adlandırılabilir mi?

Hayır! Bir de denge var. Uzun lafın kısası, bir yığının dengelenmesi, yukarı kaydırma veya aşağı kaydırma işlemleriyle yapılır (sıra dışı öğelerin değiştirilmesi).

Her dengeli BST bir öncelik kuyruğu olarak kullanılabilir ve hangisi O (logn) içinde de aranabilir ancak maksimum yığın araması O (n) doğru mu?

Evet! Bağlantılı listenin yanı sıra kullanılabilir veya dizi olabilir. O-notasyonu açısından daha pahalı ve pratikte çok daha yavaş olacak.