[Haskell-cafe] k-minima in Haskell

Yitzchak Gale gale at sefer.org
Thu Apr 12 14:23:23 EDT 2007


kmin :: Ord a => Int -> [a] -> [Int]
kmin k x = map snd $ Set.toList $ foldl' insertIfSmall (Set.fromList h) t
    (h, t) = splitAt k $ zip x [0..]

insertIfSmall :: Ord a => Set.Set a -> a -> Set.Set a
insertIfSmall s e
 | e < mx    = Set.insert e s'
 | otherwise = s
   (mx, s') = Set.deleteFindMax s


This gives O(log k * (n + k)) execution in constant memory.
If you need the result indices to be in order, you can put in
a sort at the end without changing the complexity.

This could be improved by a significant constant factor
by using a priority queue instead of Set. Any Edison people
out there?


More information about the Haskell-Cafe mailing list