import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.stream.Collectors;
import org.apache.commons.collections4.iterators.PeekingIterator;

class MegaIterator<T extends Comparable<T>> implements Iterator<T> {
    private PriorityQueue<PeekIter> queue = new PriorityQueue<>();
    
    public static void main (String[] args) throws java.lang.Exception {
    	// Test
    	Iterator<Integer> iter1 = Arrays.asList(1, 5).iterator();
        Iterator<Integer> iter2 = Arrays.asList(2, 4).iterator();
        Iterator<Integer> iter3 = Arrays.asList(1, 2, 4, 5).iterator();
        MegaIterator<Integer> megaIter = new MegaIterator<>(iter1, iter2, iter3);
        while (megaIter.hasNext()) {
            System.out.println(megaIter.next());
        }
    }
 
    public MegaIterator(Collection<Iterator<T>> iters) {
        List<PeekIter> itersList = iters.stream()
                .map(i -> new PeekIter(i))
                .collect(Collectors.toList());
        queue.addAll(itersList);
    }
    
    public MegaIterator(Iterator<T>... iters) {
        List<PeekIter> itersList = Arrays.asList(iters).stream()
                .map(i -> new PeekIter(i))
                .collect(Collectors.toList());
        queue.addAll(itersList);
    }

    @Override
    public boolean hasNext() {
        return queue.isEmpty() ? false : queue.peek().hasNext();
    }

    @Override
    public T next() {
        if (queue.isEmpty() || !queue.peek().hasNext()) {
            throw new NoSuchElementException();
        }
        PeekIter nextIter = queue.poll();
        T nextVal = nextIter.next();
        if (nextIter.hasNext()) {
            queue.add(nextIter);
        }
        return nextVal;
    }
    
    private class PeekIter extends PeekingIterator<T> implements Comparable<PeekIter> {

        public PeekIter(Iterator<? extends T> iterator) {
            super(iterator);
        }     

        @Override
        public int compareTo(PeekIter o) {
            return this.peek().compareTo(o.peek());
        }
    }
}