本篇介绍开源C语言库Melon的斐波那契堆的使用。关于 Melon 库，这是一个开源的 C 语言库，它具有：开箱即用、无第三方依赖、安装部署简单、中英文文档齐全等优势。 Github: github.com/Water-Melon/Melon 简介关于斐波那契堆，感兴趣的朋友可以参考《算法导论》或者是各类讲解博客。 本篇介绍的是斐波那契最小堆，但对于判断条件和初始化属性进行调整后，也可实现最大堆。 数据结构各类操作时间复杂度： 创建堆：O(1)插入：O(1)取最小值：O(1)将最小值从堆中移除：O(logN)合并堆：O(1)将堆结点key值减小：O(1)移除某个堆结点：O(logN)由此，我们可以看到斐波那契堆非常适合频繁插入和删除以及取得极值（最小值）结点操作。这样的操作第一个能想到的场景就是实现对超时定时器的管理。 使用我们先给出示例代码： #include #include #include "mln_core.h" #include "mln_log.h"#include "mln_fheap.h" static int cmp_handler(const void *key1, const void *key2) { return *(int *)key1 < *(int *)key2? 0: 1; } static void copy_handler(void *old_key, void *new_key) { *(int *)old_key = *(int *)new_key; } int main(int argc, char *argv[]) { int i = 10, min = 0; mln_fheap_t *fh; mln_fheap_node_t *fn; struct mln_fheap_attr fattr; struct mln_core_attr cattr; cattr.argc = argc; cattr.argv = argv; cattr.global_init = NULL; cattr.master_process = NULL; cattr.worker_process = NULL; if (mln_core_init(&cattr) < 0) { fprintf(stderr, "init failed\n"); return -1; } fattr.pool = NULL; fattr.pool_alloc = NULL; fattr.pool_free = NULL; fattr.cmp = cmp_handler; fattr.copy = copy_handler; fattr.key_free = NULL; fattr.min_val = &min; fattr.min_val_size = sizeof(min); fh = mln_fheap_new(&fattr); if (fh == NULL) { mln_log(error, "fheap init failed.\n"); return -1; } fn = mln_fheap_node_new(fh, &i); if (fn == NULL) { mln_log(error, "fheap node init failed.\n"); return -1; } mln_fheap_insert(fh, fn); fn = mln_fheap_minimum(fh); mln_log(debug, "%d\n", *((int *)mln_fheap_node_key(fn))); mln_fheap_free(fh); return 0;}main函数中的流程大致如下： 对Melon库进行初始化设置斐波那契堆初始化属性对斐波那契堆进行初始化创建斐波那契堆结点将新建的斐波那契堆结点插入堆中取斐波那契堆中最小key值的堆结点销毁斐波那契堆结构Melon中，使用斐波那契堆需要引入mln_fheap.h头文件。 这里要对堆初始化属性进行一番说明： struct mln_fheap_attr { void *pool; fheap_pool_alloc_handler pool_alloc; fheap_pool_free_handler pool_free; fheap_cmp cmp; fheap_copy copy; fheap_key_free key_free; void *min_val; mln_size_t min_val_size;};其中： pool是用于支持用户自定义内存池之用的，该指针将于pool_alloc和pool_free配合使用。pool_alloc是用于支持用户自定义分配内存之用，该函数指针第一个参数为pool，第二个参数是要分配的内存大小。pool_free是用于支持用户自定义释放内存之用，该函数指针第一个参数为要释放的内存起始地址。cmp是用于对两个堆结点所关联的用户自定义数据进行比较大小之用的。copy是用于将堆结点key值减小(decrease_key)时，将新key值（即用户自定义结构）拷贝到老key值中。key_free是用于对堆结点所关联的用户自定义数据进行释放之用的。min_val用户自定义结构的最小值，因为这里实现的是最小堆，因此需要给出一个相对所有插入本堆的结点而言都小的最小值范例。min_val_size用户自定义最小值结构所占字节数，即min_val指向的结构的字节大小。这些属性字段中，除cmp，copy，min_val和min_val_size外，其余若无需求，则可以置NULL。 内存池和分配释放函数主要是用于堆结点的分配和释放之用。之所以不直接给出一个 Melon 实现的内存池结构指针，是因为不希望斐波那契堆代码与内存池类型强关联，这样允许斐波那契堆可以接入使用者自己定义的内存管理功能。 关于斐波那契堆代码的演进，与此前红黑树文章基本类似，再次就不过多阐述了。 斐波那契堆在整个Melon框架中的使用场景基本都是在超时定时器的维护上面。 结语在Melon中，斐波那契堆的使用相较于红黑树而言确实少了很多，因此其演进的速度相对来说会慢一些，演化方向也会受到类似红黑树结构演进的影响。 同时，因为使用并不是很广泛，因此此前也有用户发起了issue，提出了堆结构存在实现错误，并给出了问题点。当然，问题早已被修复和验证。 在此非常感谢各位使用者的使用和反馈，你们的反馈也是Melon库前进的动力。 欢迎各位对Melon感兴趣的读者访问其Github仓库 github.com/Water-Melon/Melon。 感谢阅读！