diff options
Diffstat (limited to 'meowpp/dsa/Heaps.h')
| -rw-r--r-- | meowpp/dsa/Heaps.h | 84 |
1 files changed, 45 insertions, 39 deletions
diff --git a/meowpp/dsa/Heaps.h b/meowpp/dsa/Heaps.h index cac3e01..1e47afd 100644 --- a/meowpp/dsa/Heaps.h +++ b/meowpp/dsa/Heaps.h @@ -4,45 +4,6 @@ #include <cstdlib> namespace meow{ - /********************************************************* - @asciidoc - === MergeableHeap<Key, Value> - .Description - MergeableHeap is a kind of maximum-heap with an extra method `merge`, - which will merge another MergeableHeap into itself. - - .Support methods - * N <- number of elements in the heap - * M <- number of elements in the other heap if need - [options="header",width="100%",cols="1>,1<s,5<,1<,1<,10<",grid="rows"] - |======================================================================= - |Const?|Name| Parameters| Return Type| Time Complexity| Description - ||operator= | (MergeableHeap const&)| *this | O(N) - | Copy operator. - ||moveTo | (MergeableHeap*) | void | O(M) - | Transform the this->data to the heap specified in parameters - |const|top | () | Element | O(1) - | Return the maximum element in the heap. - |const|size | () | size_t | O(1) - | Return the number of elements in the heap. - |const|empty| () | bool | O(1) - | Return whether the heap is empty or not. - ||push |(Element) |void | O(log N) - | Add a element into the heap - ||pop |() |void | O(log N) - | Delete the maximum element from the heap - ||merge |(MergeableHeap*) |void | O(log M) - | Merge the specified MergeableHeap(with size=M) into itself - ||clear |() |void | O(N) - | Delete all elements from the heap - |======================================================================= - -WARNING: Consider there are two MergeableHeap `A` and `B`. -`B` will become empty after you call `A.merge(&B)`. -The data in `B` will override by data in `A` and `A` will become empty after -you call `A.moveTo(&B)` - @asciidoc- - *********************************************************/ template<class Element> class MergeableHeap{ // maximum-heap private: @@ -77,6 +38,51 @@ you call `A.moveTo(&B)` void clear( ); void merge(MergeableHeap* _heap2); }; + + /********************************************************* + @asciidoc + === meow:: *MergeableHeap<Key, Value>* (C++ class) + .Description + MergeableHeap is a kind of maximum-heap with a special method `merge`, + which will merge another MergeableHeap into itself in O(logN) time. + + .Template Request + * `Key` should has `operator<` + + .Support methods + * N <- number of elements in the heap + * M <- number of elements in the other heap if need + [options="header",width="100%",cols="1>,1<s,3<,1<,1<,10<",grid="rows"] + |======================================================================= + |Const?|Name| Parameters| Return Type| Time Complexity| Description + ||operator= | (MergeableHeap const&)| *this | O(N) + | Copy operator. + ||moveTo | (MergeableHeap*) | void | O(M) + | Transform the this->data to the heap specified in parameters + |const|top | () | Element | O(1) + | Return the maximum element in the heap. + |const|size | () | size_t | O(1) + | Return the number of elements in the heap. + |const|empty| () | bool | O(1) + | Return whether the heap is empty or not. + ||push |(Element) |void | O(log N) + | Add a element into the heap + ||pop |() |void | O(log N) + | Delete the maximum element from the heap + ||merge |(MergeableHeap*) |void | O(log M) + | Merge the specified MergeableHeap(with size=M) into itself + ||clear |() |void | O(N) + | Delete all elements from the heap + |======================================================================= + +WARNING: Consider there are two MergeableHeap `A` and `B`. + +`B` will become empty after you call `A.merge(&B)`. + +The data in `B` will override by data in `A` and `A` will become empty after +you call `A.moveTo(&B)` + +''' +@asciidoc- + *********************************************************/ } #include "MergeableHeap.hpp" |