| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Data.PriorityMap.Heap
Description
A (dynamically-sized) heap in the ST monad that allows for callbacks when objects change position within the heap. These callbacks are necessary for external data structures to keep track of the heap's state, which allows us to create the priority map data structure.
Lowest scores get placed at the top of the heap.
- data Heap s k v = Heap {}
- type OnUpdate s kv = Int -> kv -> ST s ()
- nullCallback :: OnUpdate s a
- empty :: ST s (Heap s k v)
- insertWith :: Ord k => Heap s k v -> OnUpdate s (k, v) -> (k, v) -> ST s ()
- insert :: Ord k => Heap s k v -> (k, v) -> ST s ()
- popWith :: Ord k => Heap s k v -> OnUpdate s (k, v) -> ST s (Maybe (k, v))
- pop :: Ord k => Heap s k v -> ST s (Maybe (k, v))
- bubbleUp :: Ord k => Heap s k v -> OnUpdate s (k, v) -> Int -> (k, v) -> ST s Int
- bubbleDown :: Ord k => Heap s k v -> OnUpdate s (k, v) -> Int -> (k, v) -> Int -> ST s Int
- bubbleUpDown :: Ord k => Heap s k v -> OnUpdate s (k, v) -> Int -> (k, v) -> ST s Int
- lookup :: Heap s k v -> Int -> ST s (k, v)
- modifyWith :: Ord k => Heap s k v -> OnUpdate s (k, v) -> Int -> ((k, v) -> (k, v)) -> ST s ()
- deleteWith :: Ord k => Heap s k v -> OnUpdate s (k, v) -> Int -> ST s ()
- data Tree a
- inspect :: Heap s k v -> ST s (Tree (k, v))
The heap type
Callbacks
type OnUpdate s kv = Int -> kv -> ST s ()
When this update is called, it means that heap data kv (a score/value
pair) has been moved to a new position (indicated by the Int).
nullCallback :: OnUpdate s a
This callback does nothing.
Construction
Modification
The functions which end in "With" allow you to supply an arbitrary
callback. The functions which do not use nullCallback.
insertWith :: Ord k => Heap s k v -> OnUpdate s (k, v) -> (k, v) -> ST s ()
O(log n). Insert a new score/value pair into the heap.
insert :: Ord k => Heap s k v -> (k, v) -> ST s ()
O(log n). Insert a new score/value pair into the heap (using
nullCallback).
popWith :: Ord k => Heap s k v -> OnUpdate s (k, v) -> ST s (Maybe (k, v))
O(log n). Remove the element with the lowest score from the heap. If
the heap is empty, return Nothing and make no modifications.
pop :: Ord k => Heap s k v -> ST s (Maybe (k, v))
O(log n). Remove the element with the lowest score from the heap (using
nullCallback).
Internal functions
You probably shouldn't call these functions.
bubbleUp :: Ord k => Heap s k v -> OnUpdate s (k, v) -> Int -> (k, v) -> ST s Int
Returns the final location of the thing that is bubbled up.
bubbleDown :: Ord k => Heap s k v -> OnUpdate s (k, v) -> Int -> (k, v) -> Int -> ST s Int
Returns the final location of the thing that is bubbled down.
bubbleUpDown :: Ord k => Heap s k v -> OnUpdate s (k, v) -> Int -> (k, v) -> ST s Int
Bubble up or down, depending on what is appropriate.
lookup :: Heap s k v -> Int -> ST s (k, v)
O(1). Lookup the score/value pair at a particular index in the heap.
modifyWith :: Ord k => Heap s k v -> OnUpdate s (k, v) -> Int -> ((k, v) -> (k, v)) -> ST s ()
O(log n). Make a modification to an element located at a particular index in the heap, and adjust the heap accordingly.
deleteWith :: Ord k => Heap s k v -> OnUpdate s (k, v) -> Int -> ST s ()
O(log n). Delete an element from a particular index in the heap, and adjust the heap accordingly.