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

\begin{code}

kmin :: Ord a => Int -> [a] -> [Int]
kmin k x = map snd $Set.toList$ foldl' insertIfSmall (Set.fromList h) t
where
(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
where
(mx, s') = Set.deleteFindMax s

\end{code}

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?

Regards,
Yitz