关于c:开源C语言库Melon斐波那契堆

本篇介绍开源 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 仓库。

感激浏览！

关于c:开源C语言库Melon斐波那契堆

简介

应用

结语