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}