Java Implementation
import java.util.*;
public class PatienceSort
{ public static
> void sort (E n) { List> piles = new ArrayList>; // sort into piles for (E x : n) { Pile newPile = new Pile; newPile.push(x); int i = Collections.binarySearch(piles, newPile); if (i < 0) i = ~i; if (i != piles.size) piles.get(i).push(x); else piles.add(newPile); } System.out.println("longest increasing subsequence has length = " + piles.size); // priority queue allows us to retrieve least pile efficiently PriorityQueue> heap = new PriorityQueue>(piles); for (int c = 0; c < n.length; c++) { Pile smallPile = heap.poll; n = smallPile.pop; if (!smallPile.isEmpty) heap.offer(smallPile); } assert(heap.isEmpty); } private static class Pile> extends Stack implements Comparable> { public int compareTo(Pile y) { return peek.compareTo(y.peek); } }
}