Documentation

Like sparse set https://research.swtch.com/sparse, but also a max heap https://en.wikipedia.org/wiki/Heap_(data_structure)

i.e. pop returns minimum element.

Size of sparse heap.

>>> runST $ do { set <- newSparseHeap 100; mapM_ (insertSparseHeap set) [3,5,7,11,13,11]; sizeofSparseHeap set }
5

Create new sparse heap.

>>> runST $ newSparseHeap 100 >>= elemsSparseHeap
[]

Test for membership.

>>> runST $ do { set <- newSparseHeap 100; mapM_ (insertSparseHeap set) [3,5,7,11,13,11]; memberSparseHeap set 10 }
False

>>> runST $ do { set <- newSparseHeap 100; mapM_ (insertSparseHeap set) [3,5,7,11,13,11]; memberSparseHeap set 13 }
True

Insert into the heap.

>>> runST $ do { set <- newSparseHeap 100; mapM_ (insertSparseHeap set) [3,5,7,11,13,11]; elemsSparseHeap set }
[3,5,7,11,13]

Delete element from the heap.

>>> runST $ do { set <- newSparseHeap 100; deleteSparseHeap set 10; elemsSparseHeap set }
[]

>>> let insert heap x = modifyWeightSparseHeap heap x (\_ -> fromIntegral $ 100 - x) >> insertSparseHeap heap x;

>>> runST $ do { set <- newSparseHeap 100; mapM_ (insert set) [3,5,7,11,13,11]; deleteSparseHeap set 10; elemsSparseHeap set }
[3,5,7,11,13]

>>> runST $ do { set <- newSparseHeap 100; mapM_ (insert set) [3,5,7,11,13,11]; deleteSparseHeap set 13; elemsSparseHeap set }
[3,5,7,11]

>>> runST $ do { set <- newSparseHeap 100; mapM_ (insert set) [3,5,7,11,13,11]; deleteSparseHeap set 11; elemsSparseHeap set }
[3,5,7,13]

>>> runST $ do { set <- newSparseHeap 100; mapM_ (insert set) [3,5,7,11,13,11]; deleteSparseHeap set 3; elemsSparseHeap set }
[5,11,7,13]

>>> runST $ do { set <- newSparseHeap 100; mapM_ (insert set) $ [0,2..20] ++ [19,17..3]; deleteSparseHeap set 10; elemsSparseHeap set }
[0,2,4,5,3,17,12,9,6,8,20,19,18,15,13,14,11,16,7]

Pop element from the heap.

>>> let insert heap x = modifyWeightSparseHeap heap x (\_ -> - fromIntegral x) >> insertSparseHeap heap x;

>>> runST $ do { heap <- newSparseHeap 100; mapM_ (insert heap) [5,3,7,11,13,11]; popSparseHeap heap }
Just 3

>>> runST $ do { heap <- newSparseHeap 500; mapM_ (insert heap) [1..400]; drainSparseHeap heap }
[1,2...,400]

Elements of the heap.

Returns elements as they are internally stored.

Clear sparse heap.

>>> runST $ do { set <- newSparseHeap 100; mapM_ (insertSparseHeap set) [3,5,7,11,13,11]; clearSparseHeap set; elemsSparseHeap set }
[]

Extend sparse heap to fit new capacity.

Drain element from the heap.

>>> let insert heap x = modifyWeightSparseHeap heap x (\_ -> - fromIntegral x) >> insertSparseHeap heap x;

>>> runST $ do { set <- newSparseHeap 100; mapM_ (insert set) [3,5,7,11,13,11]; drainSparseHeap set }
[3,5,7,11,13]

Modify weight of the element.

>>> let insert heap x = modifyWeightSparseHeap heap x (\_ -> fromIntegral $ 100 - x) >> insertSparseHeap heap x;
>>> let populate heap = mapM_ (insert heap) [5,3,7,11,13,11]
>>> let populate' heap = mapM_ (insertSparseHeap heap) [5,3,7,11,13,11]

>>> runST $ do { heap <- newSparseHeap 100; populate heap; popSparseHeap heap }
Just 3

>>> runST $ do { heap <- newSparseHeap 100; populate heap; modifyWeightSparseHeap heap 3 (\_ -> 0); popSparseHeap heap }
Just 5

Weight are preserved even if element is not in the heap at the moment

>>> runST $ do { heap <- newSparseHeap 100; modifyWeightSparseHeap heap 7 (\_ -> 100); populate' heap; popSparseHeap heap }
Just 7