共计 2563 个字符,预计需要花费 7 分钟才能阅读完成。
本篇介绍开源 C 语言库 Melon 的斐波那契堆的应用。对于 Melon 库,这是一个开源的 C 语言库,它具备:开箱即用、无第三方依赖、装置部署简略、中英文文档齐全等劣势。
Github repo
简介
对于斐波那契堆,感兴趣的敌人能够参考《算法导论》或者是各类解说博客。
本篇介绍的是斐波那契最小堆,但对于判断条件和初始化属性进行调整后,也可实现最大堆。
数据结构各类操作工夫复杂度:
- 创立堆:O(1)
- 插入:O(1)
- 取最小值:O(1)
- 将最小值从堆中移除:O(logN)
- 合并堆:O(1)
- 将堆结点 key 值减小:O(1)
- 移除某个堆结点:O(logN)
由此,咱们能够看到斐波那契堆非常适合频繁插入和删除以及获得极值(最小值)结点操作。这样的操作第一个能想到的场景就是实现对超时定时器的治理。
应用
咱们先给出示例代码:
#include <stdio.h>
#include <stdlib.h>
#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 仓库。
感激浏览!