|
Collaboration diagram for Heaps:
|
|
Heaps | |
| (BOOL) | + isHeapFrom:to: |
| Test whether a range is a heap. | |
| (BOOL) | + isHeapFrom:to:predicate: |
| Test whether a range is a heap. | |
| (void) | + makeHeapFrom:to: |
| Convert the given range into a heap. | |
| (void) | + makeHeapFrom:to:predicate: |
| Convert the given range into a heap. | |
| (void) | + popHeapFrom:to: |
| Remove the top element of the heap. | |
| (void) | + popHeapFrom:to:predicate: |
| Remove the top element of the heap. | |
| (void) | + pushHeapFrom:to: |
| Add an element to a heap. | |
| (void) | + pushHeapFrom:to:predicate: |
| Add an element to a heap. | |
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.
| + (BOOL) isHeapFrom: | (OLForwardIterator *) | first | ||
| to: | (OLForwardIterator *) | last | ||
Test whether a range is a heap.
This message simply sends the message isHeapFrom:to:predicate: using OLLess as the predicate.
| first | the first in the range of elements to test | |
| last | one position beyond the last in the range of elements to test |
| + (BOOL) isHeapFrom: | (OLForwardIterator *) | first | ||
| to: | (OLForwardIterator *) | last | ||
| predicate: | (id< OLBoolBinaryFunction >) | pred | ||
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.
| 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 |
| + (void) makeHeapFrom: | (OLRandomAccessIterator *) | first | ||
| to: | (OLRandomAccessIterator *) | last | ||
Convert the given range into a heap.
This message simply sends the message makeHeapFrom:to:predicate: using OLLess as the predicate.
| 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 |
| + (void) makeHeapFrom: | (OLRandomAccessIterator *) | first | ||
| to: | (OLRandomAccessIterator *) | last | ||
| predicate: | (id< OLBoolBinaryFunction >) | pred | ||
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.
| 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 |
| + (void) popHeapFrom: | (OLRandomAccessIterator *) | first | ||
| to: | (OLRandomAccessIterator *) | last | ||
Remove the top element of the heap.
This message simply sends the message popHeapFrom:to:predicate: using OLLess as the predicate.
[first, last) must qualify as a heap using the message isHeapFrom:to:predicate: with OLLess as the predicate.| first | the first in the range that is a heap | |
| last | one position beyond the last in the range that is a heap |
| + (void) popHeapFrom: | (OLRandomAccessIterator *) | first | ||
| to: | (OLRandomAccessIterator *) | last | ||
| predicate: | (id< OLBoolBinaryFunction >) | pred | ||
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:.
[first, last) must qualify as a heap using the message isHeapFrom:to:predicate: with pred as the predicate.| 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 |
| + (void) pushHeapFrom: | (OLRandomAccessIterator *) | first | ||
| to: | (OLRandomAccessIterator *) | last | ||
Add an element to a heap.
This message simply sends the message pushHeapFrom:to:predicate: using OLLess as the predicate.
[first, (last - 1)) must be a heap as verified by the message isHeapFrom:to:predicate:.| 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 |
| + (void) pushHeapFrom: | (OLRandomAccessIterator *) | first | ||
| to: | (OLRandomAccessIterator *) | last | ||
| predicate: | (id< OLBoolBinaryFunction >) | pred | ||
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.
[first, (last - 1)) must be a heap as verified by the message isHeapFrom:to:predicate:.| 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 |
|
