Decrease Key and Delete Node on Fibonacci Heap

// Go tilida Fibonachchi to'pida Decrease Key va Delete amallari
package main

import (
	"fmt"
	"math"
)

// Fibonachchi daraxti tuguni
type FibonacciTree struct {
	key      int
	children []*FibonacciTree
	parent   *FibonacciTree
	marked   bool
	order    int
}

func newFibonacciTree(key int) *FibonacciTree {
	return &FibonacciTree{
		key:      key,
		children: make([]*FibonacciTree, 0),
		parent:   nil,
		marked:   false,
		order:    0,
	}
}

func (t *FibonacciTree) addAtEnd(other *FibonacciTree) {
	t.children = append(t.children, other)
	other.parent = t
	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,
	}
}

// Tugun qo'shish
func (h *FibonacciHeap) insert(key int) *FibonacciTree {
	newTree := newFibonacciTree(key)
	h.trees = append(h.trees, newTree)
	if h.least == nil || key < h.least.key {
		h.least = newTree
	}
	h.count++
	return newTree
}

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

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

// Minimal elementni ajratib olish
func (h *FibonacciHeap) extractMin() (int, bool) {
	smallest := h.least
	if smallest == nil {
		return 0, false
	}

	for _, child := range smallest.children {
		child.parent = nil
		h.trees = append(h.trees, child)
	}

	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.key, true
}

// Daraxtlarni konsolidatsiya qilish
func (h *FibonacciHeap) consolidate() {
	auxSize := floorLog2(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.key > y.key {
				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.key < h.least.key {
				h.least = k
			}
		}
	}
}

// Kalit qiymatini kamaytirish (Decrease Key)
func (h *FibonacciHeap) decreaseKey(x *FibonacciTree, newKey int) error {
	if newKey > x.key {
		return fmt.Errorf("yangi kalit mavjud kalitdan katta")
	}
	x.key = newKey
	y := x.parent
	if y != nil && x.key < y.key {
		h.cut(x, y)
		h.cascadingCut(y)
	}
	if x.key < h.least.key {
		h.least = x
	}
	return nil
}

// Tugunni ota tugundan uzib ildizlar ro'yxatiga qo'shish (Cut)
func (h *FibonacciHeap) cut(x *FibonacciTree, y *FibonacciTree) {
	newChildren := make([]*FibonacciTree, 0, len(y.children))
	for _, c := range y.children {
		if c != x {
			newChildren = append(newChildren, c)
		}
	}
	y.children = newChildren
	y.order--
	x.parent = nil
	x.marked = false
	h.trees = append(h.trees, x)
}

// Kaskadli kesish (Cascading Cut)
func (h *FibonacciHeap) cascadingCut(y *FibonacciTree) {
	z := y.parent
	if z != nil {
		if !y.marked {
			y.marked = true
		} else {
			h.cut(y, z)
			h.cascadingCut(z)
		}
	}
}

// Tugunni o'chirish (Delete)
func (h *FibonacciHeap) delete(x *FibonacciTree) {
	h.decreaseKey(x, math.MinInt)
	h.extractMin()
}

func main() {
	fheap := newFibonacciHeap()

	fheap.insert(11)
	fheap.insert(10)
	fheap.insert(39)
	fheap.insert(26)
	fheap.insert(24)

	if minVal, ok := fheap.getMin(); ok {
		fmt.Println("Minimum value:", minVal)
	}

	if removedVal, ok := fheap.extractMin(); ok {
		fmt.Println("Minimum value removed:", removedVal)
	}
}