C++怎么实现一个斐波那契堆_C++具有高效合并操作的优先队列数据结构

// 将y链接为x的子节点
void link(FibNode* y, FibNode* x) {
    // 从根链表移除y
    remove_from_list(y);
    y->parent = x;
    if (!x->child) {
        x->child = y;
        y->left = y->right = y;
    } else {
        add_to_list(y, x->child);
    }
    x->degree++;
    y->marked = false;
}

// 合并根链表到数组，进行合并操作
void consolidate() {
    if (!min_node) return;
    int max_degree = 0;
    int sz = size + 1;
    while ((1 << max_degree) <= sz) max_degree++;
    std::vector<FibNode*> A(max_degree, nullptr);

    auto roots = get_root_list();
    for (FibNode* w : roots) {
        int d = w->degree;
        while (A[d]) {
            FibNode* u = A[d];
            if (w->key > u->key) std::swap(w, u);
            link(u, w);
            A[d] = nullptr;
            d++;
        }
        A[d] = w;
    }

    // 重建根链表并找新的最小值
    min_node = nullptr;
    for (FibNode* node : A) {
        if (!node) continue;
        if (!min_node) {
            min_node = node;
            min_node->left = min_node->right = node;
        } else {
            add_to_list(node, min_node);
            if (node->key < min_node->key) {
                min_node = node;
            }
        }
    }
}

// 从双链表中移除节点
void remove_from_list(FibNode* node) {
    node->left->right = node->right;
    node->right->left = node->left;
}

// 将节点加入某链表（以anchor为头）
void add_to_list(FibNode* node, FibNode* anchor) {
    node->left = anchor;
    node->right = anchor->right;
    anchor->right->left = node;
    anchor->right = node;
}

// 获取当前所有根节点
std::vector<FibNode*> get_root_list() {
    std::vector<FibNode*> roots;
    if (!min_node) return roots;

    FibNode* curr = min_node;
    do {
        roots.push_back(curr);
        curr = curr->right;
    } while (curr != min_node);
    return roots;
}

~FibonacciHeap() {
    // 简化：实际应递归释放所有节点
    while (min_node) extract_min();
}

bool empty() const { return min_node == nullptr; }

int top() const {
    if (!min_node) throw std::runtime_error("Heap is empty");
    return min_node->key;
}

void push(int key) {
    FibNode* node = new FibNode(key);
    if (!min_node) {
        min_node = node;
    } else {
        add_to_list(node, min_node);
        if (node->key < min_node->key) {
            min_node = node;
        }
    }
    size++;
}

int extract_min() {
    if (!min_node) throw std::runtime_error("Heap is empty");

    FibNode* z = min_node;
    // 将z的所有子节点提升为根
    if (z->child) {
        auto children = get_children(z);
        for (FibNode* child : children) {
            add_to_list(child, min_node);
            child->parent = nullptr;
        }
    }
    remove_from_list(z);
    int res = z->key;

    if (z == z->right) {
        min_node = nullptr;
    } else {
        min_node = z->right;
        consolidate();
    }
    delete z;
    size--;
    return res;
}

// 获取某个节点的所有子节点
std::vector<FibNode*> get_children(FibNode* node) {
    std::vector<FibNode*> result;
    if (!node->child) return result;
    FibNode* curr = node->child;
    do {
        result.push_back(curr);
        curr = curr->right;
    } while (curr != node->child);
    return result;
}

// 合并另一个堆（O(1) 摊还时间）
void merge(FibonacciHeap& other) {
    if (other.min_node == nullptr) return;
    if (min_node == nullptr) {
        *this = std::move(other);
        return;
    }

    // 拼接两个根链表
    FibNode* this_left = min_node->left;
    FibNode* other_right = other.min_node->right;

    min_node->left->right = other.min_node;
    other.min_node->left->right = min_node;
    FibNode* tmp = min_node->left;
    min_node->left = other.min_node->left;
    other.min_node->left = tmp;

    if (other.min_node->key < min_node->key) {
        min_node = other.min_node;
    }
    size += other.size;
    other.min_node = nullptr;
    other.size = 0;
}