本篇介绍开源C语言库Melon的斐波那契堆的使用。关于 Melon 库,这是一个开源的 C 语言库,它具有:开箱即用、无第三方依赖、安装部署简单、中英文文档齐全等优势。
Github: github.com/Water-Melon/Melon
关于斐波那契堆,感兴趣的朋友可以参考《算法导论》或者是各类讲解博客。
本篇介绍的是斐波那契最小堆,但对于判断条件和初始化属性进行调整后,也可实现最大堆。
数据结构各类操作时间复杂度:
由此,我们可以看到斐波那契堆非常适合频繁插入和删除以及取得极值(最小值)结点操作。这样的操作第一个能想到的场景就是实现对超时定时器的管理。
我们先给出示例代码:
#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
");
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.
");
return -1;
}
fn = mln_fheap_node_new(fh, &i);
if (fn == NULL) {
mln_log(error, "fheap node init failed.
");
return -1;
}
mln_fheap_insert(fh, fn);
fn = mln_fheap_minimum(fh);
mln_log(debug, "%d
", *((int *)mln_fheap_node_key(fn)));
mln_fheap_free(fh);
return 0;
}
main函数中的流程大致如下:
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;
};
其中:
这些属性字段中,除cmp,copy,min_val和min_val_size外,其余若无需求,则可以置NULL。
内存池和分配释放函数主要是用于堆结点的分配和释放之用。之所以不直接给出一个 Melon 实现的内存池结构指针,是因为不希望斐波那契堆代码与内存池类型强关联,这样允许斐波那契堆可以接入使用者自己定义的内存管理功能。
关于斐波那契堆代码的演进,与此前红黑树文章基本类似,再次就不过多阐述了。
斐波那契堆在整个Melon框架中的使用场景基本都是在超时定时器的维护上面。
在Melon中,斐波那契堆的使用相较于红黑树而言确实少了很多,因此其演进的速度相对来说会慢一些,演化方向也会受到类似红黑树结构演进的影响。
同时,因为使用并不是很广泛,因此此前也有用户发起了issue,提出了堆结构存在实现错误,并给出了问题点。当然,问题早已被修复和验证。
在此非常感谢各位使用者的使用和反馈,你们的反馈也是Melon库前进的动力。
欢迎各位对Melon感兴趣的读者访问其Github仓库 github.com/Water-Melon/Melon。
感谢阅读!
页面更新:2024-03-06
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2008-2024 All Rights Reserved. Powered By bs178.com 闽ICP备11008920号-3
闽公网安备35020302034844号