#include <priorityqueue.h>
Public Member Functions | |
| PriorityQueue (const PriorityQueue< T > &rhs) | |
| PriorityQueue (const TQAsciiDict< T > &items) | |
| 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 |
Detailed Description
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 TQPtr*) - 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
Definition at line 57 of file priorityqueue.h.
Constructor & Destructor Documentation
◆ PriorityQueue() [1/3]
|
inline |
Definition at line 60 of file priorityqueue.h.
◆ PriorityQueue() [2/3]
|
inline |
Definition at line 61 of file priorityqueue.h.
◆ PriorityQueue() [3/3]
| KOffice::PriorityQueue< T >::PriorityQueue | ( | const TQAsciiDict< T > & | items | ) |
Definition at line 103 of file priorityqueue.h.
◆ ~PriorityQueue()
|
inline |
Definition at line 63 of file priorityqueue.h.
Member Function Documentation
◆ count()
|
inline |
Definition at line 68 of file priorityqueue.h.
◆ dump()
| void KOffice::PriorityQueue< T >::dump | ( | ) | const |
For debugging.
Definition at line 148 of file priorityqueue.h.
◆ extractMinimum()
| T * KOffice::PriorityQueue< T >::extractMinimum | ( | ) |
Definition at line 134 of file priorityqueue.h.
◆ insert()
| void KOffice::PriorityQueue< T >::insert | ( | T * | item | ) |
Definition at line 116 of file priorityqueue.h.
◆ isEmpty()
|
inline |
Definition at line 69 of file priorityqueue.h.
◆ keyDecreased()
| void KOffice::PriorityQueue< T >::keyDecreased | ( | T * | item | ) |
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.
◆ operator=()
|
inline |
Definition at line 65 of file priorityqueue.h.
◆ operator==()
|
inline |
Definition at line 66 of file priorityqueue.h.
The documentation for this class was generated from the following files: