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

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

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

2025-12-07

浏览次数：次

返回列表

斐波那契堆由最小堆性质的树构成，通过循环双向链表连接根节点，支持O(1)摊还时间的插入与合并操作，提取最小值为O(log n)，适用于频繁合并场景。

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

斐波那契堆是一种高级优先队列结构，支持插入、查找最小值、合并、提取最小值和减小键值等操作，其中合并和插入的摊还时间复杂度为 O(1)，提取最小值为 O(log n)。相比二叉堆，它在需要频繁合并堆的场景中更高效。

基本原理与结构设计

斐波那契堆由一组满足最小堆性质的树组成，这些树以循环双向链表连接。每个节点包含以下信息：

key：存储的数据值
degree：子节点数量
marked：标记节点是否丢失过一个子节点
parent, child, left, right：用于构建树和根链表的指针

堆整体维护一个指向最小节点的指针，并通过级联剪枝和度数压缩优化性能。

C++ 实现关键部分

以下是简化但核心功能完整的实现框架：

// 节点定义 struct FibNode { int key; int degree; bool marked; FibNode* parent; FibNode* child; FibNode* left; FibNode* right;

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

};

简小派

简小派是一款AI原生求职工具，通过简历优化、岗位匹配、项目生成、模拟面试与智能投递，全链路提升求职成功率，帮助普通人更快拿到更好的 offer。

123 查看详情简小派

// 斐波那契堆类（简化版） class FibonacciHeap { private: FibNode* min_node; int size;

// 将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;
}

public: FibonacciHeap() : min_node(nullptr), size(0) {}

~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;
}

};

使用示例与注意事项

下面是一个简单的测试用法：

int main() { FibonacciHeap heap1, heap2;

heap1.push(5);
heap1.push(2);
heap1.push(8);

heap2.push(3);
heap2.push(7);

heap1.merge(heap2);  // O(1)

while (!heap1.empty()) {
    std::cout << heap1.extract_min() << " ";
}
// 输出: 2 3 5 7 8

}

注意：上述实现省略了 decrease_key 和 delete 操作，它们依赖于标记机制和级联剪枝，在图算法如 Dijkstra 中非常关键。生产环境需增加内存管理、异常安全和模板泛型支持。

基本上就这些，理解其摊还分析和树合并策略是掌握的关键。

以上就是C++怎么实现一个斐波那契堆_C++具有高效合并操作的优先队列数据结构的详细内容，更多请关注其它相关文章！

# 是一个 # seo2 是非极性分子 # 淮南网站建设工作方案 # 闸北网站建设设计 # 济南关键词排名seo # 普洱seo关键词排名优化如何避坑 # 网站建站建设网站 # 萝岗网站优化推广方案 # 佛山企业网站建设流程 # seo课程资源 # 山西京东网站建设选择 # 级联 # node # 移除 # 值为 # 如何使用 # 递归 # 摊还 # 最小值 # 数据结构 # 链表 # c++ # ai

相关栏目：【科技资讯46185 】【网络学院92790 】

上一篇：苹果16 Pro为何出现屏幕偏色_苹果16 Pro偏色问题分析

下一篇：《云集》查看累计收益方法

首页

关于我们

产品展示

咨询研究

新闻中心

留言板

联系我们

新闻中心 NEWS CENTER

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

基本原理与结构设计

C++ 实现关键部分

使用示例与注意事项