Heap -package:heap
Pairing heap implementation of dictionary
This module implements operations for working with a quaternary heap
stored in an unboxed array. Most heapsorts are defined in terms of a
binary heap, in which each internal node has at most two children. By
contrast, a quaternary heap has internal nodes with up to four
children. This reduces the number of comparisons in a heapsort
slightly, and improves locality (again, slightly) by flattening out
the heap.
An efficient, asymptotically optimal, implementation of a priority
queues extended with support for efficient size, and
Foldable
Note: Since many function names (but not the type name) clash
with
Prelude names, this module is usually imported
qualified, e.g.
import Data.Heap (Heap)
import qualified Data.Heap as Heap
The implementation of
Heap is based on
bootstrapped skew
binomial heaps as described by:
All time bounds are worst-case.
A min-heap of values of type a.
With this module, you can investigate the heap representation of
Haskell values, i.e. to investigate sharing and lazy evaluation.
Implementation of pairing heaps stored off-heap
The program's heap is reaching its limit, and the program should take
action to reduce the amount of live data it has. Notes:
- It is undefined which thread receives this exception. GHC
currently throws this to the same thread that receives
UserInterrupt, but this may change in the future.
- The GHC RTS currently can only recover from heap overflow if it
detects that an explicit memory limit (set via RTS flags). has been
exceeded. Currently, failure to allocate memory from the operating
system results in immediate termination of the program.