二项队列学习笔记

心已赠人 2022-05-25 03:50 96阅读 0赞

public class BinomialQueue<E extends Comparable<? super E>> {
    
        private static final int DEFAULT_TREE = 1;
        private int currentSize;
        private Node<E>[] theTree;
    
        // 扩展树
        private void expandTheTree(int newNumTrees) {
    
        }
    
        // 联合
        private Node<E> combineTrees(Node<E> t1, Node<E> t2) {
            if (t1.element.compareTo(t2.element) > 0)
                return combineTrees(t2, t1);
    
            t2.nextSibling = t1.leftChild;// 将t1的左儿子赋值给t2的右儿子
            t1.leftChild = t2;// 将t2赋值给t1的左儿子
    
            return t1;
        }
    
        private int capacity() {
            return 1 << theTree.length - 1;
        }
    
        private int findMinIndex() {
            return 0;
        }
    
        public BinomialQueue() {
    
        }
    
        public BinomialQueue(E item) {
    
        }
    
        // 合并
        public void merge() {
    
        }
    
        // h1(this)和h2(rhs)合并,合并后的值放入h1中,清空h2
        public void merge(BinomialQueue<E> rhs) {
            if (rhs == this)
                return;
    
            currentSize += rhs.currentSize;
            if (currentSize > capacity()) {
                int maxLength = Math.max(theTree.length, rhs.theTree.length);
                expandTheTree(maxLength + 1);
            }
    
            Node<E> carry = null;// 上一步得到的树,相当于执行后的h1/h2
            for (int i = 0, j = 1; j <= currentSize; i++, j *= 2) {
                Node<E> t1 = theTree[i];
                Node<E> t2 = i < rhs.theTree.length ? rhs.theTree[i] : null;
                int whichCase = t1 == null ? 0 : 1;
                whichCase += t2 == null ? 0 : 2;
                whichCase += carry == null ? 0 : 4;
                switch (whichCase) {
                case 0: // no tree
                case 1: // only this
                    break;
                case 2:// only rhs
                    theTree[i] = t2; // 将rhs中的值放入this中
                    rhs.theTree[i] = null;// 清空rhs
                    break;
                case 3:// this和rhs
                    carry = combineTrees(t1, t2);// 这里的carry相当于h1,
                    theTree[i] = rhs.theTree[i] = null;
                    break;
                case 4:// only carry
                    theTree[i] = carry;
                    carry = null;
                    break;
                case 5:// this和carry
                    carry = combineTrees(t1, carry);// 旧carry相当于h2,新carry相当于h1
                    theTree[i] = null;
                    break;
                case 6:// rhs 和carry
                    carry = combineTrees(t2, carry);// 旧carry相当于h2,新carry相当于h1
                    rhs.theTree[i] = null;
                    break;
                case 7:// 全都有
                    theTree[i] = carry;
                    carry = combineTrees(t1, t2);
                    rhs.theTree[i] = null;
                    break;
                }
            }
            // 清空rhs
            for (int k = 0; k < rhs.theTree.length; k++) {
                rhs.theTree[k] = null;
    
                rhs.currentSize = 0;
            }
        }
    
        // 插入
        public void insert() {
    
        }
    
        // 查找最小项
        public E findMin() {
            return null;
        }
    
        // 删除最小项
        public E deleteMin() throws UnderflowException {
            if (isEmpty()) {
                throw new UnderflowException();
            }
            int minIndex = findMinIndex();
            E minItem = theTree[minIndex].element;
            Node<E> deleteTree = theTree[minIndex].leftChild;
            BinomialQueue<E> deleteQueue = new BinomialQueue<>();
            deleteQueue.expandTheTree(minIndex + 1);
    
            deleteQueue.currentSize = (1 << minIndex) - 1;
            for (int j = minIndex - 1; j >= 0; j--) {
                deleteQueue.theTree[j] = deleteTree;
                deleteTree = deleteTree.nextSibling;
                deleteQueue.theTree[j].nextSibling = null;
    
            }
            theTree[minIndex] = null;
            currentSize -= deleteQueue.currentSize + 1;
            merge(deleteQueue);
            return minItem;
        }
    
        // 判断非空
        public boolean isEmpty() {
            return theTree==null;
        }
    
        // 清空
        public void makeEmpty() {
    
        }
    
        private static class Node<E> {
            private E element;
            private Node<E> leftChild;// 左儿子
            private Node<E> nextSibling;// 右儿子
    
            Node(E theElement) {
                this(theElement, null, null);
            }
    
            public Node(E theElement, Node<E> lt, Node<E> nt) {
                element = theElement;
                leftChild = lt;
                nextSibling = nt;
            }
    
        }
    }