lib
KOffice::PriorityQueue< T > Class Template Reference
#include <priorityqueue.h>
Detailed Description
template<class T>
class KOffice::PriorityQueue< T >
This PriorityQueue class is implemented as "upside down" heap, i.e.
the item with the smallest key is at the root of the heap. If you feel like using that class your template parameter has to have a public method "unsigned int key() const" which returns - surprise - the key. The supplied key must not be "negative." We use UINT_MAX as value to represent "infinity" for the shortest path algorithm. As this is a very specialized class we also demand a "void setIndex(int i)" method in order to tell nodes where they are located inside the heap. This is a very ugly approach, but it's the only way I see if you want to avoid a O(n) search for the item where you decreased the key :} Just to make it even worse we also use a "int index() const" method to fetch the index... well, you most likely would need one anyway ;) Note: This class is pointer based (like QPtr*) - if you create PriorityQueue<X> we actually operate on X* ! We don't care about deleting your pointers at all. We don't copy them, we don't create new ones,... - you own them, you have to delete them :)
In case you change a key value make sure to call keyDecreased and pass the item you touched. This is running in O(log n) according to Cormen...
All the ideas are stol^H^H^H^Hborrowed from "Introduction to Algorithms", Cormen et al
- Author:
- Werner Trobin <trobin@kde.org>
Definition at line 57 of file priorityqueue.h.
Public Member Functions | |
PriorityQueue () | |
PriorityQueue (const PriorityQueue< T > &rhs) | |
PriorityQueue (const QAsciiDict< T > &items) | |
~PriorityQueue () | |
PriorityQueue< T > & | operator= (const PriorityQueue< T > &rhs) |
bool | operator== (const PriorityQueue< T > &rhs) |
unsigned int | count () const |
bool | isEmpty () const |
void | insert (T *item) |
void | keyDecreased (T *item) |
T * | extractMinimum () |
void | dump () const |
Member Function Documentation
|
For debugging.
Definition at line 148 of file priorityqueue.h. |
|
Call this method after decreasing the key of the ith item. The heap properties will no longer be valid if you either forget to call that method, or if you increase the key. Definition at line 126 of file priorityqueue.h. |
The documentation for this class was generated from the following file: