#堆
 
 
 
what ? why ? when ? how ?
 
 
##why
 为什么要用堆？
 
##what
 什么是堆？
 
堆有什么特点？
 
##how
 
如何操作堆（建立、插入、删除、查找）？
 
##when
 
 
##什么是堆？
 
堆是特殊的“队列”，从堆中取出元素是按照元素优先级大小，而不是元素进入队列的先后顺序。
 
堆是一颗完全二叉树，其结点的值大于或小于其子结点的值（大于是最大堆 小于是最小堆）。
 
最大堆：
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1T8Qs0o2-1603163463755)(https://i.imgur.com/iNt7VPc.png)]
 
最小堆：
 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-e3hC0mKJ-1603163463757)(https://i.imgur.com/WZtNa6D.png)]
 
##为什么要用堆？
 堆也被称为“优先队列”。 比如做事情：事情 A 明天需要完成，事情 B 这周需要完成，事情 C 这个月需要完成。 事情 A 、 B 、 C 出现的顺序是 C 早于 B 早于 C ，正常情况下都将 A 置为优先级最高，B 其次，C 最低。虽然事情 C 最先知道要做但是由于优先级（时间紧迫）需要先把事件 A 先完成。
 
##堆有什么特点？
 
堆的两个特性：
 
结构性：用数组表示的完全二叉树；
 
有序性：任一结点的关键字是其子树所有结点的最大值(或最小值)。
 
##如何操作堆（建立、插入、删除、判空、判满）？
 
最大堆的操作
 
class Heap {
int[] data; //存储元素
int size;   //堆中当前元素的个数
int capacity;   //堆的最大容量
}
 
###建立
 
/**
 * 创建堆
 *
 * @param capacity
 * @return
 */
public static Heap createHeap(int capacity) {
    if (capacity <= 0) {
        System.out.println("创建失败：capacity 值为0或负数");
        return null;
    }
    Heap heap = new Heap();
    heap.data = new int[capacity + 1];
    heap.size = 0;
    heap.capacity = capacity;
    return heap;
}
 
###判空
 
    /**
 * 堆是否为空
 *
 * @param heap
 * @return
 */
public boolean isEmpty(Heap heap) {
    if (heap == null) {
        System.out.println("Heap is null.");
        return false;
    }
    return heap.size == 0;
}
 
###判满
 
    /**
 * 堆中元素是否满了
 *
 * @param heap
 * @return
 */
public boolean isFull(Heap heap) {
    if (heap == null) {
        System.out.println("Heap is null.");
        return false;
    }
    return heap.size == heap.capacity;
}
 
###插入
 
思路：
 
插入最后面比较该节点值和其父亲结点值大小，如果比其父亲结点值大换 一直判断到根。
 
/**
 * 往堆中插入元素
 *
 * @param heap
 * @param element
 * @return
 */
public boolean insert(Heap heap, int element) {
    if (heap == null) {
        System.out.println("Heap is null. 插入失败");
        return false;
    } else if (isFull(heap)) {
        System.out.println("堆满了,插入失败");
        return false;
    }
    int i = 0;
    i = ++heap.size;
    for (; element > heap.data[i / 2] && i > 1; i = i / 2) {
        heap.data[i] = heap.data[i / 2];
    }
    //插入元素
    heap.data[i] = element;
    return true;
}
 
###删除堆中的最大值
 
思路：
 将最后一个节点的值替换根结点值然后判断其子节点的值是否比其大，如果比它大换 一直往下判断到其子节点比其小或到最后。
 
/**
 * 删除堆中的最大值
 *
 * @param heap
 * @return
 */
public int deleteMax(Heap heap) {
    if (heap.isEmpty(heap)) {
        System.out.println("堆为空");
        return -1;
    }
    //读取堆中的最大元素
    int maxElement = heap.data[1];
    //获取堆中最后一个元素并将当前个数减少1
    int lastElement = heap.data[heap.size--];
    int parent=1,child;
    for (; parent * 2 <= heap.size; parent = child) {
        child = parent * 2;
        if (child != heap.size && heap.data[child] < heap.data[child + 1]) {
            child++;//指向左右孩子结点较大者
        }
        if (lastElement >= heap.data[child] ){
            //找到合适的位置
            break;
        }else{
            //在往下找调整
            heap.data[parent] = heap.data[child];
        }
    }
    heap.data[parent]=lastElement;
    return maxElement;
}
 
###按层遍历
 
/**
 * 按层遍历堆
 * @param heap
 */
public void layerTraversal(Heap heap){
    if(heap==null){
        System.out.println("Heap is null");
        return;
    }
    int layer=1,num=1;
    while(num<=heap.size){
        //每层的数量
        int layerNum=(int)(Math.pow(2,layer-1));
        for(int i=0;i<layerNum && num<=heap.size;i++){
            System.out.print("--------"+heap.data[num++]);
        }
        System.out.println();
        layer++;
    }
}
 
##结果
 
	Heap heap=Heap.createHeap(100);
    int [] data={100,34,67,78,98,55,44};
    for (int i = 0; i < data.length; i++) {
        if(heap.insert(heap,data[i])){
        }else{
            System.out.println("插入失败");
            break;
        }
    }
    heap.layerTraversal(heap);
    System.out.println("MaxElement: "+heap.deleteMax(heap));
    heap.layerTraversal(heap);
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-shjrq8Ja-1603163463759)(https://i.imgur.com/f38xvan.png)]
 
##最大堆的建立
 
记得阿里面试的时候问到过自己没有回答好… 现在想起来应该这样回答
 
方法1：通过插入操作，将N个元素一个个相继插入到一个初始为空的堆中去，其时间代价最大为 O(NlogN).
 
方法2：在线性时间复杂度下建立最大堆。
 
将N个元素按输入顺序存入，先满足完全二叉树的结构特性
调整各结点位置，以满足最大堆的有序特性。
 
方法2
 
public void buildMaxHeap(Heap heap, int[] data) {
    if (heap == null) {
        System.out.println("Heap is null");
        return;
    }
    if ((heap.capacity - heap.size) < data.length) {
        System.out.println("堆容量不足");
        return;
    }
    for (int i = 0; i < data.length; i++) {
        heap.data[++size] = data[i];
    }

    for (int i = heap.size / 2; i > 0; i--) {
        percDown(heap, i);
    }
}

//调整
public void percDown(Heap heap, int p) {
    int parent, child;
    int temp = heap.data[p];
    for (parent = p; parent * 2 <= heap.size; parent = child) {
        child = parent * 2;
        if (child != heap.size && heap.data[child+1] > heap.data[child]) {
            //指向左右结点较大者
            child++;
        }
        if (temp > heap.data[child]) {
            break;
        } else {
            heap.data[parent] = heap.data[child];
        }
    }
    heap.data[parent] = temp;
}
 
###证明方法 2 建造最大堆时间复杂度为 O(N)
 
若二叉树高为 h ，是一棵满二叉树 (堆是一棵完全二叉树结点数一定小于满二叉树)，那么结点的个数是 n=2^h -1
 
最后一层节点数 2^(h-1) 个， 最后第二层 2^(h-2) 个 … 第一层 2^(h-h) 个
 
2^(h-2) 个结点向下访问一次，2^(h-3) 个结点向下访问两次… 1 个结点向下访问 h-1 次。
 
公式推导：
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-escvy9tr-1603163463760)(https://i.imgur.com/uWb6Ft6.jpg)]
 
源代码：https://github.com/rookieLJ/Tree.git
 
TestHeap.java
 #总结
 
 
 
参考
 数据结构 陈越 何钦铭
 https://blog.csdn.net/anonymalias/article/details/8807895
 
 
堆是一个“优先队列”。
 
堆的特点：完全二叉树、每个结点大于或小于其子结点的值。从根结点到任意结点路径上结点序列的有序性。
 
最大堆的建立（第二种方法），时间复杂度 O(N)。
 
 
 
有什么问题欢迎指出，感谢！
 

 
文章目录
 
简单概述
堆叠线
两台交换机一根堆叠线如何做堆叠？
基本配置
简单测试
    
三台交换机三根堆叠线呢？
拓扑
基本配置
   
  
 

 
简单概述
 
堆叠的核心思想是将多台设备连接在一起，进行必要的配置后，虚拟化成一台设备。堆叠成功之后，主交换机、备份交换机、从交换机都是可以正常转发数据的，因为做了堆叠的交换机逻辑成为一台交换机了。要是只有主交换机在转发数据的话，那做堆叠是没有成功的，需要重新做。你可以假设一下，要是只有主交换机转发数据，备份交换机却不能转发数据，那做堆叠就没有意义了！所以主交换机、备份交换机、从交换机都是可以正常转发数据的。
 
以交换机H3C S5130型号为例
 
堆叠线
 
用一根堆叠线在两台交换机的52端口相连（做堆叠有什么线才能成功的做堆叠么？可以用网线，下图就是用网线做的堆叠；可用光纤跳线做堆叠；还有就是堆叠线）
 
光纤跳线：
 
 
堆叠线：
 
 
下面实操的堆叠线用的是网线：
 
物理图
 
 
两台交换机一根堆叠线如何做堆叠？
 
两台交换机一根堆叠线如何做堆叠？真机来一波实操。
 
拓扑图
 
 
基本配置
 
S2
 
[H3C]irf member 1 renumber 2 //配置设备的成员编号为2
 
 
<H3C>reboot   //重启
 
 
[H3C]irf member 2 priority  20  //IRF中成员编号为2的设备的优先级为20
[H3C]interface ten-gigabitethernet 2/0/52
[H3C-Ten-GigabitEthernet2/0/52]shutdown   //端口关闭
[H3C-Ten-GigabitEthernet2/0/52]quit
[H3C]irf-port 2/2   //进入IRF端口2/2
[H3C-irf-port2/2]port group interface ten-gigabitethernet 2/0/52  
[H3C-irf-port2/2]quit
[H3C]interface  ten-gigabitethernet 2/0/52
[H3C-Ten-GigabitEthernet2/0/52]undo shutdown  //开启端口
[H3C-Ten-GigabitEthernet2/0/52]quit
[H3C]irf-port-configuration active    //激活IRF端口的配置
[H3C]save force
 
S1
 
[H3C]irf member 1 priority  30
[H3C]interface ten-gigabitethernet 1/0/52
[H3C-Ten-GigabitEthernet1/0/51]shutdown
[H3C-Ten-GigabitEthernet1/0/51]quit
[H3C]irf-port 1/1
[H3C-irf-port1/1]port group interface ten-gigabitethernet 1/0/52
[H3C-irf-port1/1]quit
[H3C]interface ten-gigabitethernet 1/0/52
[H3C-Ten-GigabitEthernet1/0/51]undo shutdown
[H3C-Ten-GigabitEthernet1/0/51]quit
[H3C]save f
[H3C]irf-port-configuration active
 
 
dis irf //查看IRF的主备信息
 
 display irf link //查看IRF链路信息
 
 
display irf configuration //查看IRF中所有成员设备的IRF配置信息
 
 堆叠已经做好了
 
测试一下主交换机，备交换机是否能正常转发数据？
 
首先划分VLAN，这里直接使用默认的VLAN 1
 
给VLAN 1 配置网关IP地址为：192.168.2.1/24
 
[H3C]interface Vlan-interface 1
[H3C-Vlan-interface1]ip address  192.168.2.1 24
[H3C-Vlan-interface1]quit
[H3C]int g1/0/1
[H3C-GigabitEthernet1/0/1]port link-type access 
[H3C-GigabitEthernet1/0/1]port access vlan 1
[H3C-GigabitEthernet1/0/1]quit
[H3C]
[H3C]interface GigabitEthernet 2/0/1
[H3C-GigabitEthernet2/0/1]port link-type access 
[H3C-GigabitEthernet2/0/1]port access vlan 1
[H3C-GigabitEthernet2/0/1]quit
[H3C]
 
给本地电脑配置IP地址为192.168.2.100/24
 
 
简单测试
 
进行PING测试（主交换机）
 

 ping 192.168.2.1
 
 由以上输出结果可知，已通。
 
进行PING测试（备交换机）
 

 ping 192.168.2.1
 
 
由以上输出结果可知，已通。
 
三台交换机三根堆叠线呢？
 
交换机为H3C，型号为S5130
 
真机
 
 
 
拓扑
 
 
基本配置
 
配置的步骤其实和上面的例子基本是一样
 
 
<H3C>system-view
[H3C]irf member 1 priority  30
[H3C]interface range ten-gigabitethernet 1/0/51 to ten-gigabitethernet 1/0/52
[H3C-if-range]shutdown
[H3C-if-range]quit
[H3C]irf-port 1/1
[H3C-irf-port1/1]port group interface ten-gigabitethernet 1/0/51
[H3C-irf-port1/1]quit
[H3C]irf-port 1/2
[H3C-irf-port1/2]port group interface ten-gigabitethernet 1/0/52
[H3C-irf-port1/2]quit
[H3C]interface range ten-gigabitethernet 1/0/51 to ten-gigabitethernet 1/0/52
[H3C-if-range]undo shutdown
[H3C-if-range]return
<H3C>save f
<H3C>sys
[H3C]irf-port-configuration active
 
[H3C]irf member 1 renumber 2
 
reboot
 
 
 
<H3C>system-view
[H3C]irf member 2 priority  20
[H3C]interface range ten-gigabitethernet 2/0/51 to ten-gigabitethernet 2/0/52
[H3C-if-range]shutdown
[H3C-if-range]quit
[H3C]irf-port 2/1
[H3C-irf-port2/1]port group interface ten-gigabitethernet 2/0/51
[H3C-irf-port2/1]quit
[H3C]irf-port 2/2
[H3C-irf-port2/2]port group interface ten-gigabitethernet 2/0/52
[H3C-irf-port2/2]quit
[H3C]interface range ten-gigabitethernet 2/0/51 to ten-gigabitethernet 2/0/52
[H3C-if-range]undo shutdown
[H3C]return
<H3C>save f
<H3C>sys
[H3C]irf-port-configuration active
 
[H3C]irf member 1 renumber  3
[H3C]quit
<H3C>reboot
 

 
 
<H3C>sys
[H3C]irf member 3 priority  10
[H3C]interface range ten-gigabitethernet 3/0/51 to ten-gigabitethernet 3/0/52
[H3C-if-range]shutdown
[H3C-if-range]quit
[H3C]irf-port 3/1
[H3C-irf-port3/1]port group interface ten-gigabitethernet 3/0/51
[H3C-irf-port3/1]quit
[H3C]irf-port 3/2
[H3C-irf-port3/2]port group interface ten-gigabitethernet 3/0/52
[H3C-irf-port3/2]quit
[H3C]interface range ten-gigabitethernet 3/0/51 to ten-gigabitethernet 3/0/52
[H3C-if-range]undo shutdown
[H3C-if-range]return
<H3C>save f
<H3C>sys
[H3C]irf-port-configuration active
 

 
 
 
OK
 
 

这次要做的是用Verilog代码写一个寄存器堆，此寄存器堆共有32个寄存器，每个寄存器可存储32个二进制位。要求有一个写端口，两个读端口，本次实验设计为异步读同步写的寄存器堆，即读寄存器不需要时钟控制，但写寄存器需时钟控制。
 先上寄存器堆模块的代码
 
`timescale 1ns / 1ps
//*************************************************************************
//   > 文件名: regfile.v
//   > 描述  ：寄存器堆模块，同步写，异步读
//   > 作者  : LOONGSON
//   > 日期  : 2016-04-14
//*************************************************************************
module regfile(
    input             clk,      //时钟控制信号
    input             wen,      //写使能信号，1有效
    input      [4 :0] raddr1,   //第一个读端口的地址
    input      [4 :0] raddr2,   //第二个读端口的地址
    input      [4 :0] waddr,    //一个写端口
    input      [31:0] wdata,    //需要写入的数据
    output  [31:0] rdata1,   //读出的数据1
    output  [31:0] rdata2,   //读出的数据2
    input      [4 :0] test_addr,    //输入的调试地址
    output  [31:0] test_data     //输出调试数据
    );
    //总共32个寄存器
integer i = 0;
reg [31:0] REG_Files[31:0];
	initial//初始化32个寄存器，全为0
        for(i = 0;i < 32;i = i + 1) 
        REG_Files[i]<=0;
	always @ (posedge clk)
	begin
	   if(wen)
	   REG_Files[waddr] <= wdata;
	end
	assign rdata1 = REG_Files[raddr1] ;
	assign rdata2 = REG_Files[raddr2];
	assign test_data  = REG_Files[test_addr];
endmodule

 
其实整个代码的逻辑还是比较简单的。定义一个reg型数组REG_Files来充当寄存器堆，此数组共有32个元素，每一个元素的大小为32个二进制位。在initial块中，用for循环对寄存器堆的内容初始化为0。当时钟信号clk上跳沿时触发always语句的执行，如果写使能信号wen为1，则把数据写入寄存器堆中。因为是异步读，所以只要是输入寄存器的地址，应能够立刻得到寄存器的内容。用assign语句对读数据的输出端口rdata1和rdata2进行赋值，其中，数组的下标相当于寄存器的地址，因此可以写成REG_Files[raddr1] 这种形式。最后一个assign语句是上板验证时用到的，用test_data来向显示屏传送数据。如果仅仅是为了得到仿真图形，可以不用管这行代码，但如果想上板验证，可以查看我的另一篇博客中关于test_data的介绍。点击此处进行跳转
 
仿真图形
 写寄存器阶段
 
 读寄存器阶段
 上板验证图
 
 
regfile模块结构框图
  寄存器堆设计实验的顶层模块大致框图
 
 
最后附上本实验用到的所有文件：
 
可以使用百度云进行免费下载
 链接：https://pan.baidu.com/s/17x4MJ9VBMOF8MhVe9dWKOA
 提取码：itbo
 
如果本博客对你有所帮助，欢迎使用CSDN下载来支持我
 链接：https://download.csdn.net/download/weixin_43074474/13728756

 
二叉堆
 
二叉树
 
二叉树：是树的一种，主要的特点是二叉树的所有节点最多只有两个叶节点。除此之外没有别的要求
完全二叉树：就是在二叉树当中，除了最后一层之外，所有层的节点都有满的，且最后一层的节点也是从左到右的。优先填满左边的节点。
满二叉树：又是一种特殊的完全二叉树，满二叉树的最后一层也是满的。也就是说，除了最后一层的节点外所有的节点都有两个子节点，满二叉树的第i层节点数量为2^(i-1)。
 
二叉查找树(Binary Search Tree)，又称为有序二叉树，排序二叉树，满足以下性质：
 
1）没有键值相等的节点。
 
2）若左子树不为空，左子树上节点值均小于根节点的值。
 
3）若右子树不为空，右子树上节点值均大于根节点的值。
 二叉查找树中对于目标节点的查找过程类似与有序数组的二分查找，并且查找次数不会超过树的深度。设节点数目为n，树的深度为h，假设树的每层都被塞满(第L层有2^L个节点，层数从1开始)，则根据等比数列公式可得h=log（n+1）。即最好的情况下，二叉查找树的查找效率为O(log n)。当二叉查找树退化为单链表时，比如，只有右子树的情况,如下图所示，此时查找效率为O(n)，如下图所示：
 
 
 
 
二叉堆
 
二叉堆是完全二元树或者是近似完全二元树，按照数据的排列方式可以分为两种：最大堆和最小堆。
 
下面是数组实现的最大堆和最小堆的示意图：
 
 
添加
 
假设在最大堆[90,80,70,60,40,30,20,10,50]种添加85，需要执行的步骤如下：
 
 
 
 
删除
 
假设从最大堆[90,85,70,60,80,30,20,10,50,40]中删除90，需要执行的步骤如下：
 
 
注意：从最大堆[90,85,70,60,80,30,20,10,50,40]中删除60，执行的步骤不能单纯的用它的字节点来替换；而必须考虑到"替换后的树仍然要是最大堆"！
 
 
源码实例（最大堆）
 
 
 
 
/**
 * 二叉堆(最大堆)
 *
 */
import java.util.ArrayList;
import java.util.List;
public class MaxHeap<T extends Comparable<T>> {
    private List<T> mHeap;    // 队列(实际上是动态数组ArrayList的实例)
    public MaxHeap() {
        this.mHeap = new ArrayList<T>();
    }
    /* 
     * 最大堆的向下调整算法
     *
     * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
     *
     * 参数说明：
     *     start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
     *     end   -- 截至范围(一般为数组中最后一个元素的索引)
     */
    protected void filterdown(int start, int end) {
        int c = start;          // 当前(current)节点的位置
        int l = 2*c + 1;     // 左(left)孩子的位置
        T tmp = mHeap.get(c);    // 当前(current)节点的大小
        while(l <= end) {
            int cmp = mHeap.get(l).compareTo(mHeap.get(l+1));
            // "l"是左孩子，"l+1"是右孩子
            if(l < end && cmp<0)
                l++;        // 左右两孩子中选择较大者，即mHeap[l+1]
            cmp = tmp.compareTo(mHeap.get(l));
            if(cmp >= 0)
                break;        //调整结束
            else {
                mHeap.set(c, mHeap.get(l));
                c = l;
                l = 2*l + 1;   
            }       
        }   
        mHeap.set(c, tmp);
    }
    /*
     * 删除最大堆中的data
     *
     * 返回值：
     *      0，成功
     *     -1，失败
     */
    public int remove(T data) {
        // 如果"堆"已空，则返回-1
        if(mHeap.isEmpty() == true)
            return -1;
        // 获取data在数组中的索引
        int index = mHeap.indexOf(data);
        if (index==-1)
            return -1;
        int size = mHeap.size();
        mHeap.set(index, mHeap.get(size-1));// 用最后元素填补
        mHeap.remove(size - 1);                // 删除最后的元素
        if (mHeap.size() > 1)
            filterdown(index, mHeap.size()-1);    // 从index号位置开始自上向下调整为最小堆
        return 0;
    }
    /*
     * 最大堆的向上调整算法(从start开始向上直到0，调整堆)
     *
     * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
     *
     * 参数说明：
     *     start -- 被上调节点的起始位置(一般为数组中最后一个元素的索引)
     */
    protected void filterup(int start) {
        int c = start;            // 当前节点(current)的位置
        int p = (c-1)/2;        // 父(parent)结点的位置 
        T tmp = mHeap.get(c);        // 当前节点(current)的大小
        while(c > 0) {
            int cmp = mHeap.get(p).compareTo(tmp);
            if(cmp >= 0)
                break;
            else {
                mHeap.set(c, mHeap.get(p));
                c = p;
                p = (p-1)/2;   
            }       
        }
        mHeap.set(c, tmp);
    }
      
    /* 
     * 将data插入到二叉堆中
     */
    public void insert(T data) {
        int size = mHeap.size();
        mHeap.add(data);    // 将"数组"插在表尾
        filterup(size);        // 向上调整堆
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<mHeap.size(); i++)
            sb.append(mHeap.get(i) +" ");
        return sb.toString();
    }
 
    public static void main(String[] args) {
        int i;
        int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80};
        MaxHeap<Integer> tree=new MaxHeap<Integer>();
        System.out.printf("== 依次添加: ");
        for(i=0; i<a.length; i++) {
            System.out.printf("%d ", a[i]);
            tree.insert(a[i]);
        }
        System.out.printf("\n== 最 大 堆: %s", tree);
        i=85;
        tree.insert(i);
        System.out.printf("\n== 添加元素: %d", i);
        System.out.printf("\n== 最 大 堆: %s", tree);
        i=90;
        tree.remove(i);
        System.out.printf("\n== 删除元素: %d", i);
        System.out.printf("\n== 最 大 堆: %s", tree);
        System.out.printf("\n");
    }
} 
 
 
 
二项堆
 
二项堆是二项树的集合。在了解二项堆之前，先对二项树进行介绍。
 
二项树
 
二项树的定义
 
二项树是一种递归定义的有序树。它的递归定义如下：
 (01) 二项树B0只有一个结点；
 (02) 二项树Bk由两棵二项树B(k-1)组成的，其中一棵树是另一棵树根的最左孩子。
 
 
上图的B0、B1、B2、B3、B4都是二项树。对比前面提到的二项树的定义：B0只有一个节点，B1由两个B0所组成，B2由两个B1所组成，B3由两个B2所组成，B4由两个B3所组成；而且，当两颗相同的二项树组成另一棵树时，其中一棵树是另一棵树的最左孩子。
 
 
 
二项树的性质
 
二项树有以下性质：
 [性质一] Bk共有2k个节点。
                如上图所示，B0有20=1节点，B1有21=2个节点，B2有22=4个节点，...
 [性质二] Bk的高度为k。
                如上图所示，B0的高度为0，B1的高度为1，B2的高度为2，...
 [性质三] Bk在深度i处恰好有C(k,i)个节点，其中i=0,1,2,...,k。
               C(k,i)是高中数学中阶乘元素，例如，C(10,3)=(10*9*8) / (3*2*1)=240
               B4中深度为0的节点C(4,0)=1
               B4中深度为1的节点C(4,1)= 4 / 1 = 4
               B4中深度为2的节点C(4,2)= (4*3) / (2*1) = 6
               B4中深度为3的节点C(4,3)= (4*3*2) / (3*2*1) = 4
               B4中深度为4的节点C(4,4)= (4*3*2*1) / (4*3*2*1) = 1
              合计得到B4的节点分布是(1,4,6,4,1)。
 [性质四] 根的度数为k，它大于任何其它节点的度数。
               节点的度数是该结点拥有的子树的数目。
 
 
 
二项堆
 
二项堆是指满足以下性质的二项树的集合：
 (01) 每棵二项树都满足最小堆性质。即，父节点的关键字 <= 它的孩子的关键字。
 (02) 不能有两棵或以上的二项树具有相同的度数(包括度数为0)。换句话说，具有度数k的二项树有0个或1个。
 
 
 
 
上图就是一棵二项堆，它由二项树B0、B2和B3组成。对比二项堆的定义：(01)二项树B0、B2、B3都是最小堆；(02)二项堆不包含相同度数的二项树。
 
 
 
         二项堆的第(01)个性质保证了二项堆的最小节点就是某个二项树的根节点，第(02)个性质则说明结点数为n的二项堆最多只有log{n} + 1棵二项树。实际上，将包含n个节点的二项堆，表示成若干个2的指数和(或者转换成二进制)，则每一个2个指数都对应一棵二项树。例如，13(二进制是1101)的2个指数和为13=23 + 22+ 20, 因此具有13个节点的二项堆由度数为3, 2, 0的三棵二项树组成。
 
 
 
基本定义
 
BinomialNode是二项堆的节点。它包括了关键字(key)，用于比较节点大小；度数(degree)，用来表示当前节点的度数；左孩子(child)、父节点(parent)以及兄弟节点(next)。
 BinomialHeap是二项堆对应的类，它包括了二项堆的根节点mRoot以及二项堆的基本操作的定义。
 
 
 
 
public class BinomialHeap<T extends Comparable<T>> {
    private BinomialNode<T> mRoot;    // 根结点
    private class BinomialNode<T extends Comparable<T>> {
        T key;                // 关键字(键值)
        int degree;            // 度数
        BinomialNode<T> child;    // 左孩子
        BinomialNode<T> parent;    // 父节点
        BinomialNode<T> next;    // 兄弟节点
        public BinomialNode(T key) {
            this.key = key;
            this.degree = 0;
            this.child = null;
            this.parent = null;
            this.next = null;
        }
        public String toString() {
            return "key:"+key;
        }
    }
        
    ...
}
 
内存图如下图所示：
 
 
合并操作
 
合并操作是二项堆的重点，它的添加操作也是基于合并操作来实现的。合并两个二项堆，需要的步骤概括起来如下：
 (01) 将两个二项堆的根链表合并成一个链表。合并后的新链表按照"节点的度数"单调递增排列。
 (02) 将新链表中"根节点度数相同的二项树"连接起来，直到所有根节点度数都不相同。
 
举例如下图所示：
 
第1步：将两个二项堆的根链表合并成一个链表
           执行完第1步之后，得到的新链表中有许多度数相同的二项树。实际上，此时得到的是对应"Case 4"的情况，"树41"(根节点为41的二项树)和"树13"的度数相同，且"树41"的键值 > "树13"的键值。此时，将"树41"作为"树13"的左孩子。
第2步：合并"树41"和"树13"
          执行完第2步之后，得到的是对应"Case 3"的情况，"树13"和"树28"的度数相同，且"树13"的键值 < "树28"的键值。此时，将"树28"作为"树13"的左孩子。
第3步：合并"树13"和"树28"
          执行完第3步之后，得到的是对应"Case 2"的情况，"树13"、"树28"和"树7"这3棵树的度数都相同。此时，将x设为下一个节点。
第4步：将x和next_x往后移
          执行完第4步之后，得到的是对应"Case 3"的情况，"树7"和"树11"的度数相同，且"树7"的键值 < "树11"的键值。此时，将"树11"作为"树7"的左孩子。
第5步：合并"树7"和"树11"
          执行完第5步之后，得到的是对应"Case 4"的情况，"树7"和"树6"的度数相同，且"树7"的键值 > "树6"的键值。此时，将"树7"作为"树6"的左孩子。
第6步：合并"树7"和"树6"
          此时，合并操作完成！
 
 
 
 
插入操作
 
插入操作可以看作是将"要插入的节点"和当前已有的堆进行合并。
 
删除操作
 
删除二项堆中的某个节点，需要的步骤概括起来如下：
 (01) 将"该节点"交换到"它所在二项树"的根节点位置。方法是，从"该节点"不断向上(即向树根方向)"遍历，不断交换父节点和子节点的数据，直到被删除的键值到达树根位置。
 (02) 将"该节点所在的二项树"从二项堆中移除；将该二项堆记为heap。
 (03) 将"该节点所在的二项树"进行反转。反转的意思，就是将根的所有孩子独立出来，并将这些孩子整合成二项堆，将该二项堆记为child。
 (04) 将child和heap进行合并操作。
 
举例如下图所示：
 
 
 
 
更新操作
 
 
 
更新二项堆中的某个节点，就是修改节点的值。
 
 
斐波那契堆
 
斐波那契堆(Fibonacci heap)是一种可合并堆，可用于实现合并优先队列。它比二项堆具有更好的平摊分析性能，它的合并操作的时间复杂度是O(1)。
 与二项堆一样，它也是由一组堆最小有序树组成，并且是一种可合并堆。
 与二项堆不同的是，斐波那契堆中的树不一定是二项树；而且二项堆中的树是有序排列的，但是斐波那契堆中的树都是有根而无序的。
 
 
 
 
基本定义
 
FibNode是斐波那契堆的节点类，它包含的信息较多。key是用于比较节点大小的，degree是记录节点的度，left和right分别是指向节点的左右兄弟，child是节点的第一个孩子，parent是节点的父节点，marked是记录该节点是否被删除第1个孩子(marked在删除节点时有用)。
FibHeap是斐波那契堆对应的类。min是保存当前堆的最小节点，keyNum用于记录堆中节点的总数，maxDegree用于记录堆中最大度，而cons在删除节点时来暂时保存堆数据的临时空间。
 
 
 
 
public class BinomialHeap<T extends Comparable<T>> {
    private BinomialNode<T> mRoot;    // 根结点
    private class BinomialNode<T extends Comparable<T>> {
        T key;                // 关键字(键值)
        int degree;            // 度数
        BinomialNode<T> child;    // 左孩子
        BinomialNode<T> parent;    // 父节点
        BinomialNode<T> next;    // 兄弟节点
        public BinomialNode(T key) {
            this.key = key;
            this.degree = 0;
            this.child = null;
            this.parent = null;
            this.next = null;
        }
        public String toString() {
            return "key:"+key;
        }
    }
        
    ...
}
 
斐波那契堆是由一组最小堆组成，这些最小堆的根节点组成了双向链表(又叫"根链表")；斐波那契堆中的最小节点就是"根链表中的最小节点"！其内存图如下图所示：
 
 
插入操作
 
插入操作非常简单：插入一个节点到堆中，直接将该节点插入到"根链表的min节点"之前即可；若被插入节点比"min节点"小，则更新"min节点"为被插入节点。
 
 
斐波那契堆的根链表是"双向链表"，这里将min节点看作双向联表的表头。在插入节点时，每次都是"将节点插入到min节点之前(即插入到双链表末尾)"。此外，对于根链表中最小堆都只有一个节点的情况，插入操作就很演化成双向链表的插入操作。
 
 
 
合并操作
 
合并操作和插入操作的原理非常类似：将一个堆的根链表插入到另一个堆的根链表上即可。简单来说，就是将两个双链表拼接成一个双向链表。
 
 
 
 
获取最值操作
 
获取最小结点的操作是斐波那契堆中较复杂的操作。
 (1）将要抽取最小结点的子树都直接串联在根表中；
 (2）合并所有degree相等的树，直到没有相等的degree的树。
 
 
 
 
修改节点值操作
 
修改节点值包括减小节点值和增大节点值操作，以减小节点为例，减少斐波那契堆中的节点的键值，这个操作的难点是：如果减少节点后破坏了"最小堆"性质，如何去维护呢？下面对一般性情况进行分析。
 
(1) 首先，将"被减小节点"从"它所在的最小堆"剥离出来；然后将"该节点"关联到"根链表"中。 倘若被减小的节点不是单独一个节点，而是包含子树的树根。则是将以"被减小节点"为根的子树从"最小堆"中剥离出来，然后将该树关联到根链表中。
 (2) 接着，对"被减少节点"的原父节点进行"级联剪切"。所谓"级联剪切"，就是在被减小节点破坏了最小堆性质，并被切下来之后；再从"它的父节点"进行递归级联剪切操作。
       而级联操作的具体动作则是：若父节点(被减小节点的父节点)的marked标记为false，则将其设为true，然后退出。
       否则，将父节点从最小堆中切下来(方式和"切被减小节点的方式"一样)；然后递归对祖父节点进行"级联剪切"。
       marked标记的作用就是用来标记"该节点的子节点是否有被删除过"，它的作用是来实现级联剪切。而级联剪切的真正目的是为了防止"最小堆"由二叉树演化成链表。
 (3) 最后，别忘了对根链表的最小节点进行更新。
 
 
 
 
删除节点值操作
 
删除节点操作是："取出最小节点"和"减小节点值"的组合。
 
(1) 先将被删除节点的键值减少。减少后的值要比"原最小节点的值"即可。
 (2) 接着，取出最小节点即可。