#FibonacciHeap

#🚀 Key Features

#📥 Installation

moon add SupremeHuaji/FibonacciHeap

#🚀 Usage Guide

#🔨 Create Heap

let heap = new(int_compare)

#➕ Insert Elements

let heap = new(int_compare)
ignore(heap.insert("apple", 5))
ignore(heap.insert("banana", 2))

#📉 Peek/Extract Minimum

let heap = new(int_compare)
ignore(heap.insert("apple", 5))
ignore(heap.insert("banana", 2))
let min = heap.peek_min()         // Some(("banana", 2))
let min_pair = heap.extract_min() // Some(("banana", 2))

#🗑️ Delete Arbitrary Node

let heap = new(int_compare)
let node = heap.insert("orange", 7)
let result = heap.delete(node) // true

#🔗 Merge Heaps

let heap1 = new(int_compare)
let heap2 = new(int_compare)
ignore(heap1.insert("apple", 5))
ignore(heap2.insert("pear", 1))
heap1.merge(heap2)

#🛠️ Batch Insert

let heap = new(int_compare)
let values = ["a", "b", "c"]
let keys = [3, 1, 2]
heap.insert_many(values, keys)

#🔍 Find Node

let heap = new(int_compare)
ignore(heap.insert("a", 1))
let node = heap.find_by_value("a")
let node2 = heap.find_by_key(1)

#🎯 Traverse All Elements (Unordered/Sorted)

let heap = new(int_compare)
ignore(heap.insert("a", 3))
ignore(heap.insert("b", 1))
ignore(heap.insert("c", 2))
let arr = heap.to_array()
let sorted_arr = heap.to_sorted_array()

#🧹 Clear Heap

let heap = new(int_compare)
ignore(heap.insert("a", 1))
heap.clear()

#🏗️ Deep Clone Heap

let heap = new(int_compare)
ignore(heap.insert("a", 1))
ignore(heap.insert("b", 2))

let heap2 = heap.clone()
// heap2 is a complete copy of heap

ignore(heap.insert("c", 3)) // Modify original heap
ignore(heap2.insert("d", 4)) // Modify clone

// The two heaps are independent
let arr1 = heap.to_sorted_array()      // Contains a, b, c
let arr2 = heap2.to_sorted_array()     // Contains a, b, d

#📊 Performance Characteristics

• n = number of elements in the heap
• m = number of elements inserted in batch

#🏗️ Implementation Details

#📦 Core Data Structures

1. Node Structure (Node)
   • Content: Stores actual value and key
   • Degree: Number of child nodes
   • Mark: For cascading cuts
   • Parent/Child/Left/Right Pointers: Support heap and circular list structure

2. Heap Structure (FibHeap)
   • Root List: Circular doubly-linked list
   • Min Pointer: Fast access to minimum element
   • Element Count: Current number of elements
   • Compare Function: Custom key comparison logic

#🔄 Fibonacci Heap Working Principle

// Insert/Merge: Directly add node to root list
// Delete-Min: Promote all children of min node to root, consolidate trees of same degree
// Decrease-Key: If heap order violated, cut node and cascade cut parent

#🆚 FibonacciHeap vs Traditional Binary Heap

#🤝 Contributing

1. Fork this repository
2. Create a feature branch (git checkout -b feature/AmazingFeature)
3. Commit your changes (git commit -m 'Add some AmazingFeature')
4. Push to the branch (git push origin feature/AmazingFeature)
5. Open a Pull Request

#📜 License

#🔗 Related Resources

• Fibonacci Heap Algorithm
• MoonBit Language Documentation