欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

优先队列之二项队列(JAVA实现)

程序员文章站 2022-03-12 23:31:34
...

一、定义

1.二项树

  • 堆性:每个结点都比它的左右子树中结点要小(小顶堆)
  • 高度为 k 的二项树B(k)通过将一棵二项树B(k-1)附到另一棵二项树B(k-1)的根上构成。而B(k-1)又可以由B(k-2)附到另一棵B(k-2)的二项树上,故:B(k)是由一个根节点和B(0)、B(1)、B(2)….B(k-1)组成的。

如下是二项树B(0),B(1),B(2),B(3),B(4).
优先队列之二项队列(JAVA实现)

图1-1

2.二项队列

  • 二项队列不是一棵树,它是一个森林,一个由一组二项树组成的深林。
  • 二项队列中的树高度不同,一个高度至多存在一棵二项树。将高度为0的二项树记为 B(0),高度为 k 的二项树记为 B(k)。即:也就是说,对于k>=0,二项队列中至多存在一棵 B(k)的二项树。
  • 具有N个结点的二项队列最多有 logN 棵二项树。
每棵二项树B(k)中含有2^k个结点。故:
2^0 + 2^1 + 2^2 + .... + 2^k = N,得到 k=logN(k为树的棵数)。注意到上面提到的是“**最多**” 有logN 棵二项树,这说明一个二项队列可以缺少某棵 B(i) , 0<=i<=k
  • 由于二项树中结点个数的性质(B(k)有2^k个结点),而二项队列又是若干二项树的集合,故二项队列可以采用二进制数来标记:
如,大小为13(共有13个结点)的二项队列可以用森林 B(3)B(2)B(0)表示,并可以把这种表示写成 1101,1101以二进制形式表示13,而且还表示了该二项队列中,不存在B(1)这样的树。

二、二项队列的存储结构

二项队列是存储于一个一维数组中,该数组中的每个元素存储一棵二项树的根结点指针。具体存储方式如下图(源于网上)
优先队列之二项队列(JAVA实现)

图2-1

该存储方式的特点:

  1. 最右边的那个数组元素存储了一颗高度为0的二项树B(0)。B(0)只有一个结点,该结点的权值为13。如果数组的长度表示二进制的位数,那么这个二项队列表示为 00001101。这说明该二项队列不存在高度为7、6、5、4、1 这样的二项树:B(7)、B(6)、B(5)、B(4)、B(1)。
  2. 二项树在数组中存储是按高度排序的。
  3. 数组第 i 号索引处,存储的是高度为 i 的二项树。如,第0号索引,存储高度为0的二项树,该二项树只有一个结点,结点权值为13
  4. 二项树的采用的是链表表示,这里采用的是“左孩子右兄弟”表示法。(具体表示如下图描述的是B(4)采用左孩子右兄弟表示法)
    优先队列之二项队列(JAVA实现)
    图2-2

三、实现思路

1.合并(merge)
假设需要合并二项队列H1和H2,合并后的结果为H3。合并两个二项队列的过程如下:

  • a.寻找H1和H2中高度相同的二项树,合并这两颗二项树
  • b.重复 a) 直至树中不再有高度相同的二项树为止。
  • c.形成了新的二项队列H3

下图(图片源自网上)直观描述了H1和H2合并成H3’的过程。
优先队列之二项队列(JAVA实现)

图3-1

下图(图片源自网上)展示将两个相同高度的二项树合并的过程。
优先队列之二项队列(JAVA实现)
图3-2

具体分析:
在merge的过程中,可细分为8种情况(入下表3-3)
下图中,carry表示上一步合并二项树过程上,生成的一棵新二项树。rhs代表需要合并的二项数,this代表被合并的二项树。三者任意存在,故有八种情况。为简化代码,将八种情况使用二进制如下表示(其中0代表不存在,1代表存在)。sum表示二进制代表的数字,用于区分不同情况。

case carry rhs this sum describe
1 0 0 0 0 都不存在
2 0 0 1 1 只有this存在
3 0 1 0 2 只有rhs存在
4 0 1 1 3 rhs和this存在
5 1 0 0 4 只有carry存在
6 1 0 1 5 只有carry和this存在
7 1 1 0 6 只有carry和rhs存在
8 1 1 1 7 都存在

表3-3

用上表详细解释图3-1的例子(H1合并到H2上):

  • a.高度为0 H1的B(0)为null,H2的B(0)不为null,即rhs为null,this不为null,对应情形2(sum为1),合并之后为B(0)
  • b.高度为1 H1和H2的B(1)都不为null,即rhs和this都不为null,对应情形4(sum为3),合并为一颗新的B(2)
  • c.高度为2 H1的B(2)为null,H2的B(2)不为null,carry不为null(上一步合成的B(2));即rhs为null,this和carry不为null,对应情形6(sum为5),合并为一颗新的B(3)

2.插入
插入就是将插入的节点当作B(0)的一种合并。虽然感觉插入的时间复杂度是O(logN),但是实际是O(1),因为有一定的概率是被插入的二项队列没有B0

3.删除最小值

  • 每一个二项树的最小值为根节点,故先在根节点处找到最小值,设为B(k)。
  • 删除B(i)的根,得到若干棵二项树:B(0)、B(1)…B(k-1)。这些二项树组成一个新的二项队列 H”
  • 原来的二项队列,删除B(i)这棵根的权值最小的二项树后,得到的新的二项队列 H’
  • 合并 H” 和 H’ 即可

    每一个过程的时间复杂度为O(logN)。故加起来的时间复杂度仍为O(logN)。

四、代码实现

/**
 * Created by pengqiao on 2017/6/20.
 */
public class BinomialQueue<T extends Comparable> {
    /**
     * 二项树 采取左儿子右兄弟的记录方式
     */
    static class BinNode<T> {
        private T element;//元素
        private BinNode<T> leftChild;//左二子
        private BinNode<T> nextSibling;//兄弟

        public BinNode(T element) {
            this(element, null, null);
        }

        public BinNode(T element, BinNode<T> lt, BinNode<T> ns) {
            this.element = element;
            this.leftChild = lt;
            this.nextSibling = ns;
        }
    }

    private static final int DEAFULT_TREES = 1;//默认二项树的个数
    private int currentSize;//数组内的元素
    private BinNode<T>[] arrayTrees;//存放二项树的数组

    /**
     * 构造器
     */
    public BinomialQueue() {
        arrayTrees = new BinNode[DEAFULT_TREES];
    }

    public BinomialQueue(T x) {
        currentSize = 1;
        arrayTrees = new BinNode[1];
        arrayTrees[0] = new BinNode<>(x);
    }

    /**
     * 二项队列是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return currentSize == 0;
    }

    /**
     * 二项队列置空
     */
    public void makeEmpty() {
        this.currentSize = 0;
        for (BinNode bn : arrayTrees) {
            bn = null;
        }
    }

    /**
     * 二项队列的合并
     *
     * @param rhs(需要合并的二项队列)
     */
    public void merge(BinomialQueue rhs) {
        if (rhs == this) {//避免传入失误,合并自己
            return;
        }
        currentSize += rhs.currentSize;
        if (currentSize > capacity()) {//当前容量大于最大容量,扩容(数组长度+1)
            int newNumTrees = Math.max(this.arrayTrees.length, rhs.arrayTrees.length) + 1;
            expandTheTrees(newNumTrees);
        }
        BinNode<T> carry = null;
        for (int i = 0, j = 1; j <= currentSize; i++, j *= 2) {//使用j来控制是否结束
            BinNode<T> t1 = arrayTrees[i];//this二项树
            BinNode<T> t2 = i < rhs.arrayTrees.length ? rhs.arrayTrees[i] : null;//rhs二项树

            int whichCase = (t1 == null ? 0 : 1);
            whichCase += (t2 == null ? 0 : 2);
            whichCase += (carry == null ? 0 : 4);
            switch (whichCase) {
                case 0://this,rhs,carry都为空
                    break;
                case 1://只有this二项树
                    break;
                case 2://只有rhs二项树
                    arrayTrees[i] = t2;
                    rhs.arrayTrees[i] = null;
                    break;
                case 3://只有rhs和this二项树
                    carry = combinTrees(t1, t2);//二项树升级,不放在本节点,放在carry等待处理下个节点时处理
                    this.arrayTrees[i] = rhs.arrayTrees[i] = null;
                    break;
                case 4://只有carry二项树
                    this.arrayTrees[i] = carry;
                    carry = null;
                    break;
                case 5://只有carry和this二项树
                    carry = combinTrees(t1, carry);
                    this.arrayTrees[i] = null;
                    break;
                case 6://只有carry和rhs二项树
                    carry = combinTrees(t2, carry);
                    rhs.arrayTrees[i] = null;
                    break;
                case 7://有this,rhs和carry二项树
                    this.arrayTrees[i] = carry;
                    carry = combinTrees(t1, t2);
                    rhs.arrayTrees[i] = null;
                    break;
            }
        }
        //将rhs置空
        rhs.makeEmpty();
    }

    /**
     * 插入元素
     *
     * @param x
     */
    public void insert(T x) {
        merge(new BinomialQueue(x));
    }

    /**
     * 查找最小元素
     *
     * @return 最小元素
     */
    public T findMin() {
        return arrayTrees[findMinIndex()].element;
    }

    /**
     * 删除最小元素
     *
     * @return 最小元素
     */
    public T deleteMin() {
        if (isEmpty()) {
            System.out.println("BinomialQueue is empty");
        }
        int minIndex = findMinIndex();
        T minElement = arrayTrees[minIndex].element;//最小元素

        //将最小元素所在的二项树删除根节点,形成新的二项队列
        BinNode<T> delete = arrayTrees[minIndex].leftChild;//最小元素所在的二项树删除根节点之后的树
        BinomialQueue newBinomialQueue = new BinomialQueue();//新的二项队列
        newBinomialQueue.expandTheTrees(minIndex + 1);//新的二项队列的数组大小(B(k)分解为b(0),B(1),……B(k-1))
        newBinomialQueue.currentSize = (1 << minIndex) - 1;
        //下述循环内由于未使用中间变量,是指针指向,不可调换顺序
        for (int i = minIndex - 1; i >= 0; i--) {
            newBinomialQueue.arrayTrees[i] = delete;
            delete = delete.nextSibling;
            newBinomialQueue.arrayTrees[i].nextSibling = null;
        }
        //原有的二项队列删除最小元素所在的二项树
        arrayTrees[minIndex] = null;
        currentSize = currentSize - newBinomialQueue.currentSize;
        //进行合并
        merge(newBinomialQueue);
        return minElement;
    }

    /**
     * 更新数组长度
     *
     * @param newNumTrees 新数组的长度
     */
    private void expandTheTrees(int newNumTrees) {
        BinNode<T>[] newTrees = new BinNode[newNumTrees];
        for (int i = 0; i < Math.min(arrayTrees.length, newNumTrees); i++) {
            newTrees[i] = arrayTrees[i];
        }
        arrayTrees = newTrees;
    }

    /**
     * 合并两颗相同高度的二项树(t1的根<=t2的根)
     *
     * @param t1
     * @param t2
     * @return
     */
    private BinNode<T> combinTrees(BinNode<T> t1, BinNode<T> t2) {
        if (t1.element.compareTo(t2.element) > 0)
            return combinTrees(t2, t1);
        t2.nextSibling = t1.leftChild;
        t1.leftChild = t2;
        return t1;
    }

    /**
     * 容量(该二项队列最大容量 2^k-1 k为数组长度)
     *
     * @return
     */
    private int capacity() {
        return (1 << arrayTrees.length) - 1;
    }

    /**
     * 查找最小元素所在数组的下标
     *
     * @return
     */
    private int findMinIndex() {
        int min = 0;
        for (; arrayTrees[min] == null; min++) {//找出数组中第一个不为null的下标
            ;
        }
        for (int i = min; i < arrayTrees.length; i++) {//找出最小值
            if (arrayTrees[i] != null && arrayTrees[min].element.compareTo(arrayTrees[i].element) > 0) {
                min = i;
            }
        }
        return min;
    }

    public static void main(String[] args) {
        int numItems = 10000;
        BinomialQueue<Integer> h = new BinomialQueue<>();
        BinomialQueue<Integer> h1 = new BinomialQueue<>();
        int i = 37;
        System.out.println("Starting check.");
        for (i = 37; i != 0; i = (i + 37) % numItems)
            if (i % 2 == 0)
                h1.insert(i);
            else
                h.insert(i);

        h.merge(h1);
        for (i = 1; i < numItems; i++)
            if (h.deleteMin() != i)
                System.out.println("Oops! " + i);
        System.out.println("Check done.");
    }
}