Fibonacci yığınlarının neden basamaklı kesmelere ihtiyacı var?

Question

'Algoritma girişten' f-öbek öğreniyorum ve 'azaltma tuşu' işlemi beni gerçekten şaşırtıyor - bu neden bir 'basamaklı kesim' gerektiriyor?

Bu işlem kaldırılırsa:

bütünleme yığın()() eklemek, en az() ve birlik() maliyeti açık değişmez

özü-min()

hala O (D (n)), çünkü O (n (H)) 'konsolidasyon' işleminde, en köklü ağaçların maliyeti, kök listesine eklendiğinde ve kalan maliyetler O (D (n))
1. azalan anahtar(): belli ki O (1)

D (n) 'ye gelince, tam olarak açıklayamasam da, sanırım hala o (lgn), cak' kesişme-kesim 'olmadan, bir düğüm sadece biraz sonra root listesine taşınmış olabilir ve numaralı herhangi bir düğüm, numaralı babanın altındaki gizler verimliliği etkilemez. En azından bu durum durumu daha da kötüleştirmeyecek. Benim kötü İngilizce :(

kimse yardımcı olabilir? sayesinde

Answer 1

basamaklı kesim nedeni D (n) düşük tutmaktır için

özür dileriz. Bu çıkıyor o size herhangi bir sayıda izin verirse bir ağaçtan kesilecek düğümler, daha sonra D (n) lineer olmak için büyüyebilir, bu da silme ve silme-min'in lineer zaman almasını sağlar.

Sezgisel olarak, k siparişindeki bir ağaçtaki düğüm sayısını istersiniz. Bu şekilde, konsolide bir yığın içinde sadece logaritma açısından çok fazla ağaç olabilirsiniz.Normal sayıdaki düğümleri kesebilirsiniz. Bir ağaçtan, bu garantiyi kaybedersiniz. Özellikle, k siparişine sahip bir ağaç alabilirsin, sonra bütün torunlarını kesebilirsin. Bu, her biri yapraklar olan k çocuklu bir ağaç bırakır. Sonuç olarak, yalnızca k + 1 toplam düğümleri ile k siparişinde ağaçlar oluşturabilirsiniz. Bu, en kötü durumda, tüm düğümleri tutmak için n - 1 nolu bir ağaca ihtiyacınız olacaktır, bu nedenle D (n), O (log n) yerine n - 1 olur.

Bu yardımcı olur umarız!