Thinking in C++ Vol 2 - Practical Programming |

Prev |
Home |
Next |

A heap is an array-like data structure used to implement a
priority queue, which is just a range that is organized in a way that
accommodates retrieving elements by priority according to some comparison
function. The heap operations in the standard library allow a sequence to be
treated as a heap data structure, which always efficiently returns the
element of highest priority, without fully ordering the entire sequence.

As with the sort operations, there are two versions of
each function. The first uses the object s own **operator<** to perform
the comparison; the second uses an additional **StrictWeakOrdering** object s **operator( )(a, b)** to compare two objects for **a** **<**
**b**.

void **make_heap**(RandomAccessIterator first,

RandomAccessIterator last);

void **make_heap**(RandomAccessIterator first,

RandomAccessIterator last,

StrictWeakOrdering binary_pred);

Turns an arbitrary range into a heap.

void **push_heap**(RandomAccessIterator first,

RandomAccessIterator last);

void **push_heap**(RandomAccessIterator first,

RandomAccessIterator last,

StrictWeakOrdering binary_pred);

Adds the element *(**last-1)** to the heap determined by
the range **[first, last-1)**. In other words, it places the last element in
its proper location in the heap.

void **pop_heap**(RandomAccessIterator first,

RandomAccessIterator last);

void **pop_heap**(RandomAccessIterator first,

RandomAccessIterator last,

StrictWeakOrdering binary_pred);

Places the largest element (which is actually in ***first**,
before the operation, because of the way heaps are defined) into the position ***(last-1)**
*and* reorganizes the remaining range so that it s still in heap order. If
you simply grabbed ***first**, the next element would not be the
next-largest element; so you must use **pop_heap( )** if you want to
maintain the heap in its proper priority-queue order.

void **sort_heap**(RandomAccessIterator first,

RandomAccessIterator last);

void **sort_heap**(RandomAccessIterator first,

RandomAccessIterator last,

StrictWeakOrdering binary_pred);

This could be thought of as the complement to **make_heap( )**.
It takes a range that is in heap order and turns it into ordinary sorted order,
so it is no longer a heap. That means that if you call **sort_heap( )**,
you can no longer use **push_heap( )** or **pop_heap( )** on
that range. (Rather, you can use those functions, but they won t do anything
sensible.) This is not a stable sort.

Thinking in C++ Vol 2 - Practical Programming |

Prev |
Home |
Next |