Heaps
[Algorithms]

Collaboration diagram for Heaps:

Algorithms which operate on heaps. More...

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.

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

+ (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.

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

+ (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.

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

+ (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.

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

+ (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.

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

+ (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.

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

+ (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:.

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

+ (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.

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

+ (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.

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


ObjectiveLibGenerated Sun Apr 22 15:12:42 2007, © 2004-2007 Will Mason
SourceForge.net Logo