Fibonacci Heap

Fibonachchi to'pi (Fibonacci Heap) — minimal to'p (min-heap) yoki maksimal to'p (max-heap) xossasiga bo'ysunuvchi daraxtlar to'plamidan iborat ma'lumotlar tuzilmasidir. Biz avvalgi To'p ma'lumotlar tuzilmasi darsida min-heap va max-heap xossalarini o'rgangan edik. Ushbu ikki xossa Fibonachchi to'pidagi daraxtlarning asosiy xarakteristikalari hisoblanadi.

Fibonachchi to'pida tugun ikkitadan ko'p bolaga ega bo'lishi yoki umuman bolaga ega bo'lmasligi mumkin. Shuningdek, u binomial (binomial) va ikkilik (binary) to'plarga qaraganda ancha samarali to'p amallarini ta'minlaydi.

Fibonachchi to'pi nima uchun bunday nomlangan? Chunki undagi daraxtlar shunday tarzda quriladiki, n-tartibli daraxt kamida F(n+2) ta tugundan iborat bo'ladi, bu yerda F(n+2) — (n + 2)-Fibonachchi sonidir.

Fibonachchi to'pi (Fibonacci Heap)

Fibonachchi to'pining xossalari

Fibonachchi to'pining muhim xossalari:

• Bu min-heap tartibidagi daraxtlar to'plamidir (ya'ni, ota tugun doimo o'zining bola tugunlaridan kichik bo'ladi).
• Minimal element joylashgan tugunga doimiy ko'rsatkich (pointer) saqlanadi (min pointer).
• U belgilangan (marked) tugunlar to'plamidan iborat bo'ladi (bu xususiyat kalitni kamaytirish amali uchun kerak).
• Fibonachchi to'pi ichidagi daraxtlar tartiblanmagan (unordered), biroq har biri o'z ildiziga ega (rooted).

Fibonachchi to'pi tugunlarining xotirada ifodalanishi

Barcha daraxtlarning ildizlari tezkor murojaat qilish maqsadida bir-biriga bog'lanadi. Ota tugunning bola tugunlari esa quyidagi rasmda ko'rsatilganidek aylanma ikki tomonlama bog'langan ro'yxat (circular doubly linked list) orqali o'zaro bog'lanadi.

Aylanma ikki tomonlama bog'langan ro'yxatdan foydalanishning ikkita asosiy ustunligi mavjud:

1. Daraxtdan ixtiyoriy tugunni o'chirish O(1) vaqt oladi.
2. Ikkita shunday ro'yxatni birlashtirish (ulash) O(1) vaqt oladi.

Fibonachchi to'pining xotiradagi tuzilishi

Fibonachchi to'pi ustida amallar

1. Element qo'shish

Algoritm

insert(H, x)
    degree[x] = 0
    p[x] = NIL
    child[x] = NIL
    left[x] = x
    right[x] = x
    mark[x] = FALSE
    x ni o'z ichiga olgan ildiz ro'yxatini H ning ildiz ro'yxatiga birlashtiring
    if min[H] == NIL yoki key[x] < key[min[H]]
        then min[H] = x
    n[H] = n[H] + 1

Mavjud to'pga yangi tugun qo'shish quyidagi bosqichlarda amalga oshiriladi:

1. Element uchun yangi tugun yarating.
2. To'p bo'sh yoki yo'qligini tekshiring.
3. Agar to'p bo'sh bo'lsa, yangi tugunni ildiz tugun deb belgilang va unga min ko'rsatkichini yo'naltiring.
4. Aks holda, tugunni ildizlar ro'yxatiga qo'shing va agar zarur bo'lsa, min ko'rsatkichini yangilang.

Fibonachchi to'piga element qo'shish namunasi

2. Minimal elementni topish

Minimal element har doim to'g'ridan-to'g'ri min ko'rsatkichi orqali olinadi. Shu sababli bu amal O(1) vaqt talab etadi.

3. Birlashtirish

Ikkita Fibonachchi to'pini birlashtirish quyidagi bosqichlardan iborat:

1. Har ikkala to'pning ildizlar ro'yxatini bir-biriga ulang (concatenate).
2. Yangi hosil bo'lgan umumiy ildizlar ro'yxatidan eng kichik kalitni tanlab, min ko'rsatkichini yangilang.

Ikkita to'pni birlashtirish (Union)

4. Minimal elementni ajratib olish

Bu Fibonachchi to'pidagi eng muhim amal hisoblanadi. Ushbu amalda to'pdan eng kichik qiymatga ega bo'lgan tugun o'chiriladi va to'p qayta konsolidatsiya qilinadi (tartibga solinadi).

Quyidagi bosqichlar ketma-ket bajariladi:

1. min tugunni o'chiring.
2. min ko'rsatkichini ildizlar ro'yxatidagi keyingi ildizga o'tkazing.
3. O'chirishdan oldin to'pdagi daraxtlarning maksimal darajasiga teng o'lchamli yordamchi massiv yarating.
4. Bir xil darajaga ega bo'lgan bir nechta ildizlar qolmaguncha quyidagi (5–7) bosqichlarni bajaring:
5. Joriy ildizning (min ko'rsatkichi) darajasini massivdagi mos indeksga joylashtiring.
6. Keyingi ildizning darajasini massivdagi indeksga moslang.
7. Agar bir xil daraja uchun ikkitadan ko'p moslik paydo bo'lsa, ushbu ildizlarga birlashtirish (union) amalini qo'llang.

Yuqoridagi bosqichlarni amaliy misolda ko'rib chiqamiz:

• Quyidagi to'p ustida extract-min amalini bajaramiz:

Boshlang'ich Fibonachchi to'pi

• min tugunni o'chiramiz, uning barcha bola tugunlarini ildizlar ro'yxatiga chiqaramiz va min ko'rsatkichini keyingi ildizga yo'naltiramiz:

Minimal tugunni o'chirish

• Daraxtdagi maksimal daraja 3 ga teng. 4 o'lchamli massiv yaratib, ildizlar darajasini moslashtiramiz:

Massiv yaratish va moslashtirish

• Bu yerda 23 va 7 bir xil darajaga ega, shuning uchun ularni birlashtiramiz:

Bir xil darajadagi daraxtlarni birlashtirish

• Yana 7 va 17 bir xil darajaga ega bo'ldi, ularni ham birlashtiramiz:

Bir xil darajalilarni birlashtirish

• Yana 7 va 24 bir xil darajaga ega bo'ldi, ularni ham birlashtiramiz:

Bir xil darajalilarni birlashtirish

• Keyingi tugunlarni moslashtiramiz:

Qolgan tugunlarni massivga moslashtirish

• 52 va 21 bir xil darajaga ega bo'ldi, ularni birlashtiramiz:

Bir xil darajalilarni birlashtirish

• Shuningdek, 21 va 18 ni birlashtiramiz:

Bir xil darajalilarni birlashtirish

• Qolgan ildizni moslashtiramiz:

Qolgan ildizni moslashtirish

• Yakuniy to'p holati hosil bo'ladi:

Yakuniy Fibonachchi to'pi

5. Kalitni kamaytirish va tugunni o'chirish

Ushbu amallar to'pning eng nozik va muhim amallari bo'lib, ular haqida alohida Fibonachchi to'pida kalitni kamaytirish va tugunni o'chirish amallari mavzusida batafsil to'xtalamiz.

Dasturiy namunalar: Go, Python, Java, C va C++

// Go tilida Fibonachchi to'pi (Fibonacci Heap)
package main

import (
	"fmt"
	"math"
)

// Fibonachchi daraxti tuguni
type FibonacciTree struct {
	value int
	child []*FibonacciTree
	order int
}

func newFibonacciTree(value int) *FibonacciTree {
	return &FibonacciTree{
		value: value,
		child: make([]*FibonacciTree, 0),
		order: 0,
	}
}

// Daraxtni bolalar ro'yxatining oxiriga qo'shish
func (t *FibonacciTree) addAtEnd(other *FibonacciTree) {
	t.child = append(t.child, other)
	t.order++
}

// Fibonachchi to'pi
type FibonacciHeap struct {
	trees []*FibonacciTree
	least *FibonacciTree
	count int
}

func newFibonacciHeap() *FibonacciHeap {
	return &FibonacciHeap{
		trees: make([]*FibonacciTree, 0),
		least: nil,
		count: 0,
	}
}

// Yangi tugun qo'shish (Insert)
func (h *FibonacciHeap) insertNode(value int) {
	newTree := newFibonacciTree(value)
	h.trees = append(h.trees, newTree)
	if h.least == nil || value < h.least.value {
		h.least = newTree
	}
	h.count++
}

// Minimal qiymatni olish (Find Min)
func (h *FibonacciHeap) getMin() (int, bool) {
	if h.least == nil {
		return 0, false
	}
	return h.least.value, true
}

func floorLog(x int) int {
	if x <= 0 {
		return 0
	}
	return int(math.Log2(float64(x)))
}

// Daraxtlarni birlashtirish (Consolidate)
func (h *FibonacciHeap) consolidate() {
	auxSize := floorLog(h.count) + 2
	aux := make([]*FibonacciTree, auxSize)

	for len(h.trees) > 0 {
		x := h.trees[0]
		h.trees = h.trees[1:]
		order := x.order

		for order < len(aux) && aux[order] != nil {
			y := aux[order]
			if x.value > y.value {
				x, y = y, x
			}
			x.addAtEnd(y)
			aux[order] = nil
			order++
			if order >= len(aux) {
				aux = append(aux, nil)
			}
		}
		if order >= len(aux) {
			for len(aux) <= order {
				aux = append(aux, nil)
			}
		}
		aux[order] = x
	}

	h.least = nil
	for _, k := range aux {
		if k != nil {
			h.trees = append(h.trees, k)
			if h.least == nil || k.value < h.least.value {
				h.least = k
			}
		}
	}
}

// Minimal elementni o'chirish va qaytarish (Extract Min)
func (h *FibonacciHeap) extractMin() (int, bool) {
	smallest := h.least
	if smallest == nil {
		return 0, false
	}

	// Bolalarini ildiz ro'yxatiga qo'shish
	for _, child := range smallest.child {
		h.trees = append(h.trees, child)
	}

	// smallest tugunini to'pdan olib tashlash
	newTrees := make([]*FibonacciTree, 0, len(h.trees))
	for _, t := range h.trees {
		if t != smallest {
			newTrees = append(newTrees, t)
		}
	}
	h.trees = newTrees

	if len(h.trees) == 0 {
		h.least = nil
	} else {
		h.least = h.trees[0]
		h.consolidate()
	}

	h.count--
	return smallest.value, true
}

func main() {
	fibonacciHeap := newFibonacciHeap()

	fibonacciHeap.insertNode(7)
	fibonacciHeap.insertNode(3)
	fibonacciHeap.insertNode(17)
	fibonacciHeap.insertNode(24)

	if minVal, ok := fibonacciHeap.getMin(); ok {
		fmt.Println("the minimum value of the fibonacci heap:", minVal)
	}

	if removedVal, ok := fibonacciHeap.extractMin(); ok {
		fmt.Println("the minimum value removed:", removedVal)
	}
}

Vaqt murakkabligi

Fibonachchi to'pining asosiy amallari uchun asimptotik vaqt murakkabliklari quyidagi jadvalda keltirilgan:

Fibonachchi to'pining qo'llanilishi

• Dijkstra algoritmi — graflarda manbadan eng qisqa yo'llarni qidirishda prioritetli navbat sifatida Fibonachchi to'pidan foydalanilganda umumiy vaqt murakkabligi O(E + V log V) ga qisqaradi (ikkilik to'pda bu O((E + V) log V) bo'ladi).
• Prim algoritmi — minimal qamrovchi daraxtni (Minimum Spanning Tree - MST) qurish jarayonida kalitlarni tezkor yangilash (O(1)) imkoniyatini beradi.