`collections.heapqueue` does mostly what you want. You would have to remove
duplicates yourself, like below, but probably with an iterator called something
like `unique`.
import collections.heapqueue
var heap = newHeapQueue[int]()
let data = [1, 3, 5, 1, 7, 9, 2, 4, 6, 6, 8, 0]
for item in data:
push(heap, item)
var last = heap.pop() #NOTE: assumes heap.len >= 1
echo last
while heap.len > 0:
let next = heap.pop()
if next != last:
echo next
last = next
Note that this does actually store duplicates until the final iteration because
heaps do not possess a fast { i.e. O(log-set-size) } test for membership. So,
if you had a great many copies and/or memory constraints that could be an
issue. You didn't mention how high the duplication rate would be, but I bet
something like the above is fast enough.
A more memory optimal structure for this is probably a simple B-Tree or some
kind of balanced binary tree (less cache friendly than a B-Tree, but typically
more available/implemented more often) or possibly an adaptation of
`collections.critbits` or some other digital search tree. I think there is a
red-black tree in Nim floating around.
