Algorithms which operate on heaps.
More...
Detailed Description
Algorithms which operate on heaps.
A heap is a way of organizing a sequential range as a tree. The first element in the range is always the element that least satisfies the predicate used to sort the heap. That is, if the heap is created using OLLess as the predicate, then the first element will be the largest. This makes heaps very useful for containers like priority queues, as there is no need to sort through the collection to find the element with the highest priority. Additionally, elements can be added and removed from a heap in logarithmic time.
- See also:
- OLAlgorithm
Function Documentation
Test whether a range is a heap.
This message simply sends the message isHeapFrom:to:predicate: using OLLess as the predicate.
- See also:
- + sortHeapFrom:to:
- Parameters:
-
first | the first in the range of elements to test |
last | one position beyond the last in the range of elements to test |
- Returns:
- YES if the range is a heap, NO otherwise
Test whether a range is a heap.
If the range [first, last)
is a heap that was created with the predicate pred, then this message returns YES.
- See also:
- + sortHeapFrom:to:predicate:
- Parameters:
-
first | the first in the range of elements to test |
last | one position beyond the last in the range of elements to test |
pred | the function object used to determine the order of the heap |
- Returns:
- YES if the range is a heap, NO otherwise
Convert the given range into a heap.
This message simply sends the message makeHeapFrom:to:predicate: using OLLess as the predicate.
- See also:
- + sortHeapFrom:to:
- Parameters:
-
first | the first in the range of elements to make a heap |
last | one position beyond the last in the range of elements to make a heap |
Convert the given range into a heap.
The range [first, last)
is turned into a heap using pred as the definition of the sorting order for the heap.
- See also:
- + sortHeapFrom:to:
- Parameters:
-
first | the first in the range of elements to make a heap |
last | one position beyond the last in the range of elements to make a heap |
pred | the function object used to determine the order of the heap |
Remove the top element of the heap.
This message simply sends the message popHeapFrom:to:predicate: using OLLess as the predicate.
- Precondition:
- The range
[first, last)
must qualify as a heap using the message isHeapFrom:to:predicate: with OLLess as the predicate.
- See also:
- + sortHeapFrom:to:
- Parameters:
-
first | the first in the range that is a heap |
last | one position beyond the last in the range that is a heap |
Remove the top element of the heap.
The element at the position referred to by the iterator first is removed. Of course, generic algorithms cannot actually remove anything from a collection as they only operate on iterators. Therefore, the element at the position pointed to by first is moved to the end of the range. This means that subsequently the iterator one position before last will refer to the element that was 'removed', and the remainder of the range will still qualify as a heap using the message isHeapFrom:to:predicate:.
- Precondition:
- The range
[first, last)
must qualify as a heap using the message isHeapFrom:to:predicate: with pred as the predicate.
- See also:
- + sortHeapFrom:to:
- Parameters:
-
first | the first in the range that is a heap |
last | one position beyond the last in the range that is a heap |
pred | the function object used to determine the order of the heap |
Add an element to a heap.
This message simply sends the message pushHeapFrom:to:predicate: using OLLess as the predicate.
- Precondition:
- The range
[first, (last - 1))
must be a heap as verified by the message isHeapFrom:to:predicate:.
- See also:
- + sortHeapFrom:to:
- Parameters:
-
first | the first in the range to which to add a heap element |
last | one position beyond the last in the range to which to add a heap element |
Add an element to a heap.
The element at one position before last is added to the heap. Subsequently the entire range from [first, last)
will be a valid heap.
- Precondition:
- The range
[first, (last - 1))
must be a heap as verified by the message isHeapFrom:to:predicate:.
- See also:
- + sortHeapFrom:to:
- Parameters:
-
first | the first in the range to which to add a heap element |
last | one position beyond the last in the range to which to add a heap element |
pred | the function object used to determine the order of the heap |