package algs24;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class XPairingPQ implements PQ {
	static class Node {
		Node (double x, LinkedList<Node> sh) { item = x; subheaps = sh; }
		double item;
		LinkedList<Node> subheaps;
		public String toString () {
			StringBuilder sb = new StringBuilder ();
			sb.append(item);
			sb.append(" [ ");
			for (Node x : subheaps) {
				sb.append(x.toString());
				sb.append(' ');
			}
			sb.append(']');
			return sb.toString();		
		}
	};
	XPairingPQ (int N) {}
	
	Node head = null;
	int _size = 0;
	
	public String toString () {
		if (head == null)
			return "";
		return head.toString();
	}
	public int size() {
		return _size;
	}
	public boolean isEmpty() {
		return _size == 0;
	}
	
	static private Node meld (Node h1, Node h2) {
		if (h1 == null) return h2;
		if (h2 == null) return h1;
		if (h1.item < h2.item) {
			h1.subheaps.add(h2);
			return h1;
		}
		h2.subheaps.add(h1);
		return h2;
	}
	public void insert(double x) {
		head = meld (head, new Node (x, new LinkedList <> ()));
	}
	public double min() { return head.item; }
	static private Node merge_pairs (List<Node> heaps) {
		if (heaps.isEmpty())
			return null;
		Node cur = null;
		Iterator<Node> it = heaps.iterator ();
		if (heaps.size() % 2 == 1)
			cur = it.next();
		while (it.hasNext())
			cur = meld (cur, meld (it.next(), it.next()));
		return cur;
	}
	public double delMin() { 
		double ret = head.item;
		head = merge_pairs (head.subheaps); 
		return ret; 
	}
	public void toGraphviz() {}
}