"Kees Bleijenberg"
My program uses a very long list of (index,count) items. Index and count are Int's. The program updates the count values a lot. Therefor it uses the index as a key to update the belonging count value. After updating, the program needs the (index,count) pair with the least count value in the list. What is an approriate (fast) datastructure? My first idea was to use a heap. Problem with the heap is that I can't update the count value by its index fast. Any ideas?
Try Data.IntMap and Data.Map. I think they have different asymptotics, but they both do exactly what you want, so try both. Because of the purity I would estimate the total query time to O(log n) and the total update time to O((log n)^2). Greets, Ertugrul -- nightmare = unsafePerformIO (getWrongWife >>= sex) http://ertes.de/