what is the most appropriate data structure supporting binary search to solve LIS?

Question

I would like to solve the Longest increasing subsequence problem in Haskell, with the patience sorting algorithm.

I first did it with lists, and it worked in O(n^2) time.

Now I would like to do create an algorithm that solve it in O(n log n) time. To do it I need to get the "first fit" when I insert each value v, in other words finding the first pile whose last element is bigger than v in n log n time.

data OrderedStruct = undefined -- ???

-- I need a method to remove elements in   (n log n)  time
popFirstBigger :: Ord a -> a -> OrderedStruct a -> (Maybe a, OrderedStruct a)
popFirstBigger a t = undefined

-- and one to insert them in  (n log n) or faster
insert :: Ord a -> a -> OrderedStruct a -> OrderedStruct a
insert a t = undefined

I could do it with a balanced binary search tree, but I would like to know if it exists a shortest way. For example, any structure that I could use in a dichotomic search would be sufficient.

Does such a data structure exists in standard Haskell (Seq for example?)

Otherwise which data structure could I use?

Answer 1

Data.Set offers insert, delete, and lookupGT, all in O(log n) time.