Siemel said:
Then maybe we can use the protected member 'c'.
'std:
riority_queue' actually just uses 'std::make_heap', etc. Anyway,
accessing the member directly is no good: the internal organization of
the heap essentially makes immediate stability without some tool
impossible.
Anyway, what is a priority_queue? Is it just like a queue, except that
items with the highest priority get retrieved by top() and pop() first?
This is the interface description: It has operations 'empty()', 'top()',
'pop()', and 'push()' like a 'std::stack' and what a 'std::queue' should
have, too (unfortunately, the latter uses 'front()' instead of 'top()').
However, the internal organization of the priority queue is a little bit
more involved.
How do they achieve O(lg(N)) for both push and pop (ie. how does the heap
work?).
The essential idea of several heap structure is to maintain the heap
property: the heap is viewed as a tree and each tree has its minimum
element in the root (reverse the comparison and it has the maximum
element in the root; this does not really matter as long as you stick
with one definition - I will use the minimum). In the container stored
in the 'std:
riority_queue' a binary tree is implicitly stored: the
element with index '0' is the root. The children of a node with index
'n' are the nodes with '2 * (n + 1) - 1' and '2 * (n + 1)'. The parent
of the node 'n' is the node '(n - 1) / 2' (I guess, I got the numbers
wrong somewhere; just draw a picture and number the nodes and things
should be relatively easy to work out). In any case, the tree is fully
balanced.
Inserting into a heap is pretty simple: you add a node to the lowest
level and exchange it with its parent if the parent has a bigger key.
This far, the representation of the tree does not at all matter and
other heaps, eg. a Fibonacci-heap, use a different structure than an
array to hold a heap although they also maintain the heap property.
Since the heap in the array is balanced, insertion takes at most
O(log n) steps.
Extracting from a heap, is also simple: you simply exchange the root
with the last element and bubble down the root again: check which of
the child nodes is the smaller one and exchange the node with this
child until the node is smaller than both children. This again takes
at most O(log n) steps.
This form of heap is called a "d-heap" in its general form where "d"
is the arity of the tree: the same approach works with non-binary
trees, too, although the computation of child and parent nodes changes
slightly. When I compared different priority queues, I found that
"d == 5" had the best performance for integer values stored in the
heap. An even bigger 'd' is probably better if the nodes itself become
bigger. Of course, this was based on a few tests with my own
implementation and probably does not hold up to a scientific analysis.
Other forms of priority queues provide additional capabilities, eg.
ability to change the key for the priority fast. Of some interest in
this direction are Fibonacci-heaps which can do changes of the keys
in such a form that it becomes amortized constant, at least when using
it for Dijkstra's algorithms for finding shortest paths (I don't
remember the details; it is possible that it is amortized constant in
general applications, too).