Fibonacci Heap

                                                               Fibonacci Heap

             

          Standart binary heap bir çok işlem için worst case de en kötü o(lgn) bazılarında o(1) de çalışır ancak böyle iki heap'ı birleştirmeye(union) çalıştığımızda o(n) de çalışır.Tanımını ve özelliklerini anlatacağım fibonacci heap union işlemini amortized(ortalama) zaman da o(1) de ,decrase key'i normal binary heap o(lgn) de yaparken fibonacci heap o(1) de , yine binary heap insert işlemini o(lgn) yaparken fibonacci heap o(1) de yapar.

              Peki bu fibonacci heap neye benzer.Hem heap gibi hemde ağaçlı yapıya sahiptir bu tanım binary heapa benzese de fibonacci heap'ı binary heapdan ayıran double linked list yani karşılıklı göstergeler kullanan bir yapıda olmasıdır.Bu bağlantılı liste özelliği sayesinde yukarıda bahsettiğimiz gibi union,insert gibi işlemler o(1) de çalışmakdadır.

             Fibonacci heap'ın bazı özelliklerinden bahsedecek olursak; root olan en üstteki node'lar bir biriyle çember şeklinde bağlantılı şekildedir.

1 – Her seviye bir alt seviyedeki elemanlardan herhangi bir çoçuğu pointerle gösterir.

2-Bu çocuk ve diğer 1.basamakdaki çocuklar root'u gösteren göstergelere sahiptir.

3-Her elaman üstteki node'dan daha büyüktür.

4-Her seviyede aynen rootların olduğu seviyedeki gibi bir çember bağlılık söz konusudur.

5.Her eleman bir üst seviyeyi gösteren bir bağlantıya sahiptir.

Not : Çizgiler pointerları simgelemektedir.

Aşşağıdaki resimde 1 kırmızı 2 yeşil 5 mavi 4 turuncu ile açıklanmıştır.