概要
前面分别通过C和C++实现了斐波那契堆，本章给出斐波那契堆的Java版本。还是那句老话，三种实现的原理一样，择其一了解即可。
目录
1. 斐波那契堆的介绍
2. 斐波那契堆的基本操作
3. 斐波那契堆的Java实现(完整源码)
4. 斐波那契堆的Java测试程序
转载请注明出处：
更多内容：数据结构与算法系列 目录
(01) 斐波那契堆(一)之 图文解析 和 C语言的实现
(02) 斐波那契堆(二)之 C++的实现
(03) 斐波那契堆(三)之 Java的实现
斐波那契堆(Fibonacci heap)是一种可合并堆，可用于实现合并优先队列。它比二项堆具有更好的平摊分析性能，它的合并操作的时间复杂度是O(1)。
与二项堆一样，它也是由一组堆最小有序树组成，并且是一种可合并堆。
与二项堆不同的是，斐波那契堆中的树不一定是二项树；而且二项堆中的树是有序排列的，但是斐波那契堆中的树都是有根而无序的。
1. 基本定义
private int keyNum; // 堆中节点的总数
private FibNode min; // 最小节点(某个最小堆的根节点)
private class FibNode {
int key; // 关键字(键值)
int degree; // 度数
FibNode left; // 左兄弟
FibNode right; // 右兄弟
FibNode child; // 第一个孩子节点
FibNode parent; // 父节点
boolean marked; // 是否被删除第一个孩子
public FibNode(int key) {
this.key = key;
this.degree = 0;
this.marked = false;
this.left = this;
this.right = this;
this.parent = null;
this.child = null;
}
}
...
}
FibNode是斐波那契堆的节点类，它包含的信息较多。key是用于比较节点大小的，degree是记录节点的度，left和right分别是指向节点的左右兄弟，child是节点的第一个孩子，parent是节点的父节点，marked是记录该节点是否被删除第1个孩子(marked在删除节点时有用)。
FibHeap是斐波那契堆对应的类。min是保存当前堆的最小节点，keyNum用于记录堆中节点的总数，maxDegree用于记录堆中最大度，而cons在删除节点时来暂时保存堆数据的临时空间。
上面是斐波那契堆的两种不同结构图的对比。从中可以看出，斐波那契堆是由一组最小堆组成，这些最小堆的根节点组成了双向链表(后文称为"根链表")；斐波那契堆中的最小节点就是"根链表中的最小节点"！
PS. 上面这幅图的结构和测试代码中的"基本信息"测试函数的结果是一致的；你可以通过测试程序来亲自验证！
2. 插入操作
插入操作非常简单：插入一个节点到堆中，直接将该节点插入到"根链表的min节点"之前即可；若被插入节点比"min节点"小，则更新"min节点"为被插入节点。
上面是插入操作的示意图。
斐波那契堆的根链表是"双向链表"，这里将min节点看作双向联表的表头(后文也是如此)。在插入节点时，每次都是"将节点插入到min节点之前(即插入到双链表末尾)"。此外，对于根链表中最小堆都只有一个节点的情况，插入操作就很演化成双向链表的插入操作。
此外，插入操作示意图与测试程序中的"插入操作"相对应，感兴趣的可以亲自验证。
插入操作代码
* 将node堆结点加入root结点之前(循环链表中)
* a …… root
* a …… node …… root
*/
private void addNode(FibNode node, FibNode root) {
node.left = root.left;
root.left.right = node;
node.right = root;
root.left = node;
}
/*
* 将节点node插入到斐波那契堆中
*/
private void insert(FibNode node) {
if (keyNum == 0)
min = node;
else {
addNode(node, min);
Linux 常用命令随笔（一） - 516Forever713 阅读原文»
Linux 常用命令随笔（一）
1、检查linux服务器的文件系统的磁盘空间
df -h
说明：
-h更具目前磁盘空间和使用情况 以更易读的方式显示
-H根上面的-h参数相同,不过在根式化的时候,采用1000而不是1024进行容量转换
-k以单位显示磁盘的使用情况
2、查看Linux使用内存使用情况
cat /proc/meminfo
3、Linux开放端口
1）、修改 /etc/sysconfig/iptables 文件
2）、重启 iptables
service iptables restart
4、Linux查看网络信息
netstat用于显示与IP、TCP、UDP和ICMP协议相关的统计数据，一般用于检验本机各端口的网络连接情况。
常见参数：
-a (all)显示所有选项，默认不显示LISTEN相关
-t (tcp)仅显示tcp相关选项
-u (udp)仅显示udp相关选项
-n 拒绝显示别名，能显示数字的全部转化成数字。
-l 仅列出有在 Listen (监听) 的服�状态
-p 显示建立相关链接的程序名
-r 显示路由信息，路由表
-e 显示扩展信息，例如uid等
-s 按各个协议进行统计
-c 每隔一个固定时间，执行该netstat命令。
提示：LISTEN和LISTENING的状态只有用-a或者-l才能看到
netstat -an | grep 4899
Proto Local Address Foreign Address State
TCP Eagle:2929 219.137.227.10:4899 ESTABLISHED
协议（Proto）：TCP，指是传输层通讯协议
本地机器名（Local Address）：Eagle，俗称计算机名，本地打开并用于连接的端口：2929
远程机器名（Foreign Address）：219.137.227.10
远程端口：4899
状态：ESTABLISHED
状态列表
LISTEN ：在监听状态中。
ESTABLISHED：已建立联机的联机情况。
TIME_WAIT：该联机在目前已经是等待的状态。
列出所有 tcp 端口
netstat -at
列出所有 udp 端口
netstat -au
列出所有处于监听状态的 Sockets
只显示监听端口
netstat -l
只列出所有监听 tcp 端口
netstat -lt
只列出所有监听 udp 端口
netstat -lu
在 netstat 输出中显示 PID 和进程名称
netstat -p
netstat -p 可以与其它开关一起使用，就可以添加 “PID/进程名称” 到 netstat 输出中，这样 debugging 的时候可以很方便的发现特定端口运行的程序。
Active Internet connections (w/o servers)
Proto Recv-Q Send-Q Local Address Foreign Address State PID/Program name
tcp 1 0 ramesh-laptop.loc:47212 192.168.185.75:www CLOSE_WAIT 2109/firefox
tcp 0 0 ramesh-laptop.loc:52750 lax:www ESTABLISHED 2109/firefox
5、Linux建立软连接
ln是linux中一个非常重要命令。它的功能是为某一个文件在另外一个位置建立一个同步的链接，这个命令最常用的参数是-s,具体用法是：
ln -s 源文件 目标文件 -s 是 symbolic的意思。
例：ln -s /lib/lsb /usr/lj
即：在usr目录下建立指向/lib/lsb目录的lj文件。
本文链接：Linux 常用命令随笔（一），转载请注明。
没有评论:
发表评论