|
|||
|
|
|
|||
|
|
#include <ogdf/basic/BinaryHeap.h>
Classes | |
| class | Element |
Public Member Functions | |
| BinaryHeap (INDEX c) | |
| construct a binary heap with capacity c | |
| ~BinaryHeap () | |
| destructor | |
| bool | empty () const |
| return true if heap is empty | |
| INDEX | size () const |
| return the number of elements in the heap | |
| void | decPriority (const Element &elem, Priority prior) |
| decrease the priority of elem | |
| const Element & | insert (X obj, Priority prior) |
| insert elem and return a handle | |
| const Element & | push (X obj, Priority prior) |
| ! insert elem and return a handle [same as insert] | |
| const X & | getMin () const |
| return the Object with the min. score | |
| const X & | top () const |
| return the Object with the min. score [same as getMin] | |
| X | extractMin () |
| return the smallest element and remove it from heap | |
| X | pop () |
| return the smallest element and remove it from heap [same as extractMin] | |
| void | clear () |
| empty the heap | |
| const X & | operator[] (INDEX idx) const |
| obtain const references to the element at index idx (the smallest heap array index is 0.). | |
Private Member Functions | |
| INDEX | capacity () const |
| return current capacity of the heap | |
| void | swap (INDEX pos1, INDEX pos2) |
| void | minHeapify (INDEX pos) |
| INDEX | getParent (INDEX pos) const |
| INDEX | getLeft (INDEX pos) const |
| INDEX | getRight (INDEX pos) const |
Private Attributes | |
| Array< Element *, INDEX > | data |
| INDEX | s |
Definition at line 66 of file BinaryHeap.h.
| ogdf::BinaryHeap< X, Priority, INDEX >::BinaryHeap | ( | INDEX | c | ) | [inline] |
construct a binary heap with capacity c
Definition at line 102 of file BinaryHeap.h.
| ogdf::BinaryHeap< X, Priority, INDEX >::~BinaryHeap | ( | ) | [inline] |
destructor
Definition at line 105 of file BinaryHeap.h.
| INDEX ogdf::BinaryHeap< X, Priority, INDEX >::capacity | ( | ) | const [inline, private] |
return current capacity of the heap
Definition at line 210 of file BinaryHeap.h.
| void ogdf::BinaryHeap< X, Priority, INDEX >::clear | ( | ) | [inline] |
empty the heap
Definition at line 190 of file BinaryHeap.h.
| void ogdf::BinaryHeap< X, Priority, INDEX >::decPriority | ( | const Element & | elem, | |
| Priority | prior | |||
| ) | [inline] |
decrease the priority of elem
Definition at line 121 of file BinaryHeap.h.
| bool ogdf::BinaryHeap< X, Priority, INDEX >::empty | ( | ) | const [inline] |
return true if heap is empty
Definition at line 113 of file BinaryHeap.h.
| X ogdf::BinaryHeap< X, Priority, INDEX >::extractMin | ( | ) | [inline] |
return the smallest element and remove it from heap
Definition at line 170 of file BinaryHeap.h.
| INDEX ogdf::BinaryHeap< X, Priority, INDEX >::getLeft | ( | INDEX | pos | ) | const [inline, private] |
Definition at line 242 of file BinaryHeap.h.
| const X& ogdf::BinaryHeap< X, Priority, INDEX >::getMin | ( | ) | const [inline] |
return the Object with the min. score
Definition at line 160 of file BinaryHeap.h.
| INDEX ogdf::BinaryHeap< X, Priority, INDEX >::getParent | ( | INDEX | pos | ) | const [inline, private] |
Definition at line 240 of file BinaryHeap.h.
| INDEX ogdf::BinaryHeap< X, Priority, INDEX >::getRight | ( | INDEX | pos | ) | const [inline, private] |
Definition at line 244 of file BinaryHeap.h.
| const Element& ogdf::BinaryHeap< X, Priority, INDEX >::insert | ( | X | obj, | |
| Priority | prior | |||
| ) | [inline] |
insert elem and return a handle
Definition at line 139 of file BinaryHeap.h.
| void ogdf::BinaryHeap< X, Priority, INDEX >::minHeapify | ( | INDEX | pos | ) | [inline, private] |
Definition at line 223 of file BinaryHeap.h.
| const X& ogdf::BinaryHeap< X, Priority, INDEX >::operator[] | ( | INDEX | idx | ) | const [inline] |
obtain const references to the element at index idx (the smallest heap array index is 0.).
Definition at line 199 of file BinaryHeap.h.
| X ogdf::BinaryHeap< X, Priority, INDEX >::pop | ( | ) | [inline] |
return the smallest element and remove it from heap [same as extractMin]
Definition at line 185 of file BinaryHeap.h.
| const Element& ogdf::BinaryHeap< X, Priority, INDEX >::push | ( | X | obj, | |
| Priority | prior | |||
| ) | [inline] |
! insert elem and return a handle [same as insert]
Definition at line 155 of file BinaryHeap.h.
| INDEX ogdf::BinaryHeap< X, Priority, INDEX >::size | ( | ) | const [inline] |
return the number of elements in the heap
Definition at line 116 of file BinaryHeap.h.
| void ogdf::BinaryHeap< X, Priority, INDEX >::swap | ( | INDEX | pos1, | |
| INDEX | pos2 | |||
| ) | [inline, private] |
Definition at line 212 of file BinaryHeap.h.
| const X& ogdf::BinaryHeap< X, Priority, INDEX >::top | ( | ) | const [inline] |
return the Object with the min. score [same as getMin]
Definition at line 165 of file BinaryHeap.h.
Array<Element *, INDEX> ogdf::BinaryHeap< X, Priority, INDEX >::data [private] |
Definition at line 206 of file BinaryHeap.h.
INDEX ogdf::BinaryHeap< X, Priority, INDEX >::s [private] |
Definition at line 207 of file BinaryHeap.h.
