Fibonacci heap

To implement the required operations (make_heap, insert, find_min, delete_min, and decrease_key) in a Fibonacci Heap in C++, I will guide you through each function step by step.

Node Structure First, we need a Node structure to represent each element in the Fibonacci Heap:

struct Node {
    int key;
    int degree;
    bool marked;
    Node *parent;
    Node *child;
    Node *left;
    Node *right;

    Node(int k) : key(k), degree(0), marked(false), parent(nullptr), child(nullptr) {
        left = right = this;
    }
};

FibonacciHeap Class Next, we'll define the FibonacciHeap class with the required operations:

class FibonacciHeap {
private:
    Node* min;
    int n;

    void link(Node* y, Node* x);
    void consolidate();
    void cut(Node* x, Node* y);
    void cascadingCut(Node* y);

public:
    FibonacciHeap() : min(nullptr), n(0) {}

    // Operations
    void makeHeap();
    void insert(int key);
    Node* findMin();
    int deleteMin();
    void decreaseKey(Node* x, int k);

    bool isEmpty() const {
        return min == nullptr;
    }
};

Operation Implementations a. makeHeap Creates a new empty Fibonacci Heap.

void FibonacciHeap::makeHeap() {
    min = nullptr;
    n = 0;
}

b. insert Inserts a new key into the heap.

void FibonacciHeap::insert(int key) {
    Node* x = new Node(key);
    if (min == nullptr) {
        min = x;
    } else {
        x->left = min;
        x->right = min->right;
        min->right->left = x;
        min->right = x;
        if (key < min->key) {
            min = x;
        }
    }
    n++;
}

c. findMin Finds the minimum key in the heap.

Node* FibonacciHeap::findMin() {
    return min;
}

d. deleteMin Deletes the minimum key from the heap and returns its value.

int FibonacciHeap::deleteMin() {
    Node* z = min;
    if (z != nullptr) {
        if (z->child != nullptr) {
            Node* x = z->child;
            do {
                Node* next = x->right;
                x->left = min;
                x->right = min->right;
                min->right->left = x;
                min->right = x;
                x->parent = nullptr;
                x = next;
            } while (x != z->child);
        }

        z->left->right = z->right;
        z->right->left = z->left;

        if (z == z->right) {
            min = nullptr;
        } else {
            min = z->right;
            consolidate();
        }
        n--;
    }
    int minKey = z->key;
    delete z;
    return minKey;
}

e. decreaseKey Decreases the key of a node and restructures the heap if necessary.

void FibonacciHeap::decreaseKey(Node* x, int k) {
    if (k > x->key) {
        throw invalid_argument("New key is greater than current key.");
    }
    x->key = k;
    Node* y = x->parent;
    if (y != nullptr && x->key < y->key) {
        cut(x, y);
        cascadingCut(y);
    }
    if (x->key < min->key) {
        min = x;
    }
}

Helper Functions These helper functions are used internally by the main operations:

a. link Links two trees of the same degree.

void FibonacciHeap::link(Node* y, Node* x) {
    y->left->right = y->right;
    y->right->left = y->left;

    y->parent = x;
    if (x->child == nullptr) {
        x->child = y;
        y->right = y;
        y->left = y;
    } else {
        y->left = x->child;
        y->right = x->child->right;
        x->child->right->left = y;
        x->child->right = y;
    }

    x->degree++;
    y->marked = false;
}

b. consolidate Consolidates the trees in the heap to maintain the Fibonacci Heap properties.

void FibonacciHeap::consolidate() {
    int D = floor(log2(n)) + 1;
    vector<Node*> A(D, nullptr);

    vector<Node*> rootList;
    Node* x = min;
    if (x != nullptr) {
        do {
            rootList.push_back(x);
            x = x->right;
        } while (x != min);
    }

    for (Node* w : rootList) {
        x = w;
        int d = x->degree;
        while (A[d] != nullptr) {
            Node* y = A[d];
            if (x->key > y->key) {
                swap(x, y);
            }
            link(y, x);
            A[d] = nullptr;
            d++;
        }
        A[d] = x;
    }

    min = nullptr;
    for (Node* y : A) {
        if (y != nullptr) {
            if (min == nullptr) {
                min = y;
                min->left = min;
                min->right = min;
            } else {
                y->left = min;
                y->right = min->right;
                min->right->left = y;
                min->right = y;
                if (y->key < min->key) {
                    min = y;
                }
            }
        }
    }
}

c. cut Cuts a node from its parent and adds it to the root list.

void FibonacciHeap::cut(Node* x, Node* y) {
    if (x->right == x) {
        y->child = nullptr;
    } else {
        x->right->left = x->left;
        x->left->right = x->right;
        if (y->child == x) {
            y->child = x->right;
        }
    }
    y->degree--;

    x->left = min;
    x->right = min->right;
    min->right->left = x;
    min->right = x;
    x->parent = nullptr;
    x->marked = false;
}

d. cascadingCut Performs a cascading cut to maintain the heap's structure.

void FibonacciHeap::cascadingCut(Node* y) {
    Node* z = y->parent;
    if (z != nullptr) {
        if (!y->marked) {
            y->marked = true;
        } else {
            cut(y, z);
            cascadingCut(z);
        }
    }
}

Main Function Example Here's a simple main function to test the Fibonacci Heap:

int main() {
    FibonacciHeap heap;

    heap.makeHeap();
    heap.insert(10);
    heap.insert(3);
    heap.insert(15);
    heap.insert(6);

    cout << "Minimum: " << heap.findMin()->key << endl; // Should print 3

    cout << "Deleted Min: " << heap.deleteMin() << endl; // Should delete and print 3

    cout << "Minimum after deletion: " << heap.findMin()->key << endl; // Should print 6

    return 0;
}

This setup covers all operations.

akshay-nm/gist.md