Heap operations – HP Integrity NonStop H-Series User Manual
Page 194
Click on the banner to return to the user guide home page.
©Copyright 1996 Rogue Wave Software
Heap Operations
A heap is a binary tree in which every node is larger than the values associated with either
child. A heap (and, for that matter, a binary tree) can be very efficiently stored in a vector, by
placing the children of node i in positions 2 * i + 1 and 2 * i + 2.
Using this encoding, the largest value in the heap will always be located in the initial position,
and can therefore be very efficiently retrieved. In addition, efficient (logarithmic) algorithms
exist that both permit a new element to be added to a heap and the largest element removed
from a heap. For these reasons, a heap is a natural representation for the
priority_queue
data
.
The default operator is the less-than operator (operator <) appropriate to the element type. If
desired, an alternative operator can be specified. For example, by using the greater-than
operator (operator >), one can construct a heap that will locate the smallest element in the first
location, instead of the largest.
Heaps and Ordered Collections
The algorithm make_heap() takes a range, specified by random access iterators, and converts it
into a heap. The number of steps required is a linear function of the number of elements in the
range.
void make_heap (RandomAccessIterator first,
RandomAccessIterator last [, Compare ]);
A new element is added to a heap by inserting it at the end of a range (using the push_back()
member function of a vector or deque, for example), followed by an invocation of the algorithm
push_heap(). The push_heap() algorithm restores the heap property, performing at most a
logarithmic number of operations.
void push_heap (RandomAccessIterator first,
RandomAccessIterator last [, Compare ]);
The algorithm pop_heap() swaps the first and final elements in a range, then restores to a heap
the collection without the final element. The largest value of the original collection is therefore
still available as the last element in the range (accessible, for example, using the back() member
function in a vector, and removable using the pop_back() member function), while the
remainder of the collection continues to have the heap property. The pop_heap() algorithm