Returns a tuple where the first element is a heap consisting of the longest prefix of least elements in this heap that do not satisfy the given predicate, and the second element is the remainder of the elements.
Returns a tuple where the first element is a heap consisting of the longest prefix of least elements in this heap that do not satisfy the given predicate, and the second element is the remainder of the elements. O(n log n)
Delete the minimum key from the heap and return the resulting heap.
Delete the minimum key from the heap and return the resulting heap. O(log n)
Return a heap consisting of all the members of this heap except for the least n.
Return a heap consisting of all the members of this heap except for the least n. O(n log n)
Returns a heap consisting of the longest prefix of least elements of this heap that do not satisfy the predicate.
Returns a heap consisting of the longest prefix of least elements of this heap that do not satisfy the predicate. O(n log n)
Filter the heap, retaining only values that satisfy the predicate.
Filter the heap, retaining only values that satisfy the predicate. O(n)
Construct heaps from each element in this heap and union them together into a new heap.
Construct heaps from each element in this heap and union them together into a new heap. O(n)
Insert a new value into the heap.
Insert a new value into the heap. O(1)
Is the heap empty? O(1)
Map a function over the heap, returning a new heap ordered appropriately.
Map a function over the heap, returning a new heap ordered appropriately. O(n)
Get the minimum key on the (nonempty) heap.
Get the minimum key on the (nonempty) heap. O(1)
Remove duplicate entries from the heap.
Remove duplicate entries from the heap. O(n log n)
Partition the heap according to a predicate.
Partition the heap according to a predicate. The first heap contains all elements that satisfy the predicate. The second contains all elements that fail the predicate. O(n)
The number of elements in the heap.
The number of elements in the heap. O(1)
Returns a tuple where the first element is a heap consisting of the longest prefix of least elements in this heap that satisfy the given predicate and the second element is the remainder of the elements.
Returns a tuple where the first element is a heap consisting of the longest prefix of least elements in this heap that satisfy the given predicate and the second element is the remainder of the elements. O(n log n)
Partition the heap of the elements that are less than, equal to, and greater than a given value.
Partition the heap of the elements that are less than, equal to, and greater than a given value. O(n)
Split into two heaps, the first containing the n least elements, the second containing the n greatest elements.
Split into two heaps, the first containing the n least elements, the second containing the n greatest elements. O(n log n)
Return a heap consisting of the least n elements of this heap.
Return a heap consisting of the least n elements of this heap. O(n log n)
Returns a heap consisting of the longest prefix of least elements of this heap that satisfy the predicate.
Returns a heap consisting of the longest prefix of least elements of this heap that satisfy the predicate. O(n log n)
Traverse the elements of the heap in sorted order and produce a new heap with applicative effects.
Traverse the elements of the heap in sorted order and produce a new heap with applicative effects. O(n log n)
Split the heap into the minimum element and the remainder.
Split the heap into the minimum element and the remainder. O(log n)
Meld the values from two heaps into one heap.
Meld the values from two heaps into one heap. O(1)
An efficient, asymptotically optimal, implementation of priority queues extended with support for efficient size.
The implementation of 'Heap' is based on bootstrapped skew binomial heaps as described by: G. Brodal and C. Okasaki , "Optimal Purely Functional Priority Queues", Journal of Functional Programming 6:839-857 (1996),
Based on the heaps Haskell library by Edward Kmett