001package algs24;
002
003import java.util.Iterator;
004import java.util.LinkedList;
005import java.util.List;
006
007public class XPairingPQ implements PQ {
008        static class Node {
009                Node (double x, LinkedList<Node> sh) { item = x; subheaps = sh; }
010                double item;
011                LinkedList<Node> subheaps;
012                public String toString () {
013                        StringBuilder sb = new StringBuilder ();
014                        sb.append(item);
015                        sb.append(" [ ");
016                        for (Node x : subheaps) {
017                                sb.append(x.toString());
018                                sb.append(' ');
019                        }
020                        sb.append(']');
021                        return sb.toString();           
022                }
023        };
024        XPairingPQ (int N) {}
025        
026        Node head = null;
027        int _size = 0;
028        
029        public String toString () {
030                if (head == null)
031                        return "";
032                return head.toString();
033        }
034        public int size() {
035                return _size;
036        }
037        public boolean isEmpty() {
038                return _size == 0;
039        }
040        
041        static private Node meld (Node h1, Node h2) {
042                if (h1 == null) return h2;
043                if (h2 == null) return h1;
044                if (h1.item < h2.item) {
045                        h1.subheaps.add(h2);
046                        return h1;
047                }
048                h2.subheaps.add(h1);
049                return h2;
050        }
051        public void insert(double x) {
052                head = meld (head, new Node (x, new LinkedList <> ()));
053        }
054        public double min() { return head.item; }
055        static private Node merge_pairs (List<Node> heaps) {
056                if (heaps.isEmpty())
057                        return null;
058                Node cur = null;
059                Iterator<Node> it = heaps.iterator ();
060                if (heaps.size() % 2 == 1)
061                        cur = it.next();
062                while (it.hasNext())
063                        cur = meld (cur, meld (it.next(), it.next()));
064                return cur;
065        }
066        public double delMin() { 
067                double ret = head.item;
068                head = merge_pairs (head.subheaps); 
069                return ret; 
070        }
071        public void toGraphviz() {}
072}