优先队列之左式堆学习笔记

谁践踏了优雅 2022-05-25 01:26 162阅读 0赞

public class LeftisHeap<E extends Comparable<T>, T> {
    
        private Node<E> root;
    
        // 合并左式堆的驱动例程
        private Node<E> merge(Node<E> n1, Node<E> n2) {
            if(n1==null)
                return n2;
            if(n2==null)
                return n1;
            if(n1.element.compareTo((T) n2.element)<0)
                return merge1(n1,n2);
            else 
                return merge1(n2,n1);
    
        }
        // 合并左式堆的实际例程
        private Node<E> merge1(Node<E> n1, Node<E> n2) {
            if(n1.left==null)//单节点
                n1.left=n2;
            else{
                n1.right=merge(n1.right,n2);
                if(n1.left.npl<n1.right.npl)//左儿子零路径比右儿子的短
                    swapChildren(n1); //交换(旋转)
                n1.npl=n1.right.npl+1;
            }
    
            return n1;
    
        }
    
        // 儿子交换
        private void swapChildren(Node<E> t) {
    
        }
    
        public LeftisHeap() {
            root = null;
        }
    
        public void merge(LeftisHeap<E, T> rhs) {
            if(this==rhs)
                return;
    
            root=merge(root,rhs.root);
            rhs.root=null;
        }
    
        // 插入
        public void insert(T x) {
            root=merge(new Node<E>((E) x),root);
        }
    
        // 查找最小
        public T findMin() {
            return null;
        }
    
        // 删除最小
        public E deleteMin() throws UnderflowException {
            if (isEmpty())
                throw new UnderflowException();// 如果为空,报错
            E minItem=root.element;
            root=merge(root.left,root.right);
            return minItem;
        }
    
        // 非空判断
        public boolean isEmpty() {
            return root == null;
        }
    
        public void makeEmpty() {
            root = null;
        }
    
        private static class Node<E> {
            E element;
            Node<E> left;  //左节点
            Node<E> right; //右节点
            int npl; //null path length 零路径长 :从某点x到一个不具有两儿子的节点的最短路径的长 对于任一节点,左儿子的零路径长至少等于右儿子的零路径长(left.npl>=right.npl)
    
            Node(E theElement) {
                this(theElement, null, null);
            }
    
            Node(E theElement, Node<E> lt, Node<E> rt) {
                element = theElement;
                left = lt;
                right = rt;
            }
    
        }
    }