diff options
Diffstat (limited to 'meowpp/dsa/MergeableHeap.h')
| -rw-r--r-- | meowpp/dsa/MergeableHeap.h | 131 |
1 files changed, 74 insertions, 57 deletions
diff --git a/meowpp/dsa/MergeableHeap.h b/meowpp/dsa/MergeableHeap.h index 1e47afd..c1a2460 100644 --- a/meowpp/dsa/MergeableHeap.h +++ b/meowpp/dsa/MergeableHeap.h @@ -4,6 +4,19 @@ #include <cstdlib> namespace meow{ + //# + //#=== meow:: *MergeableHeap<Element>* (C++ class) + //#==== Description + //# 一個用 *左偏樹* 實作的 *Maximum-Heap* , 除了原本heap有的功能外, + //# 還支援 `merge`, `split` 等功能 + //# + //#==== Template Class Operators Request + //#[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"] + //#|===================================================================== + //#|Const?|Typename| Operator | Parameters | Return_Type| Description + //#|const |Element |operator< |(Element `v`)| bool | 大小比較 + //#|===================================================================== + //# template<class Element> class MergeableHeap{ // maximum-heap private: @@ -23,66 +36,70 @@ namespace meow{ public: MergeableHeap(); MergeableHeap(MergeableHeap const& _heap2); - // - ~MergeableHeap(); - // MergeableHeap& operator=(MergeableHeap const& _heap2); - void moveTo(MergeableHeap* _heap2); - // - Element const& top () const; - size_t size () const; - size_t empty() const; - // - void push (Element const& _value); - void pop ( ); - void clear( ); + ~MergeableHeap(); + + //#==== Support Methods + //# + //# * N <- `this` 中擁有的資料數 + //# + //#[options="header",width="100%",cols="1>m,2>s,7<,3<,3^,20<",grid="rows"] + //#|===================================================================== + //#|Const?|Name | Parameters | Return_Type| Time_Complexity| Description + + + //#||moveTo|(MergeableHeap* `h`)|void|O(M) + //#|將 `this` 的資料複寫到 `h` 上面, 同時清空自己, + //# 時間複雜度中的M是 `h` 所擁有的資料數 + void moveTo(MergeableHeap* _heap2); + + + //#|const|top|()|Element const&|O(1) + //#|回傳最大的那個 `Element` + Element const& top() const; + + + //#|const|size|()|size_t|O(1) + //#|回傳 `this` 中擁有的資料數 + size_t size() const; + + + //#|const|empty|()|bool|O(1) + //#|回傳 `this` 是否為空 + bool empty() const; + + + //#||push|(Element const& `e`)|void|O(logN) + //#|將 `e` 加入 + void push(Element const& _value); + + + //#||pop|()|void|O(logN) + //#|將最大的 `Element` 移除 + void pop(); + + + //#||clear|()|void|O(N) + //#|將資料清空 + void clear(); + + + //#||merge|(MergeableHeap* `heap2`)|void|O(logN+logM) + //#|將 `heap2` 的資料統統加到 `this` 中, 並且清空 `heap2` + //# 時間複雜度中的M是 `heap2` 的資料數 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- - *********************************************************/ + //# [WARNING] + //#============================================== + //# * 假設現在有兩個MergeableHeap `A` 和 `B`, 則: + //# ** 執行 `A.merge(&B)` 後 `B` 會變成空的 + //# ** 執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉 + //#============================================== + //# + //# ''' + //# } #include "MergeableHeap.hpp" |