1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
#ifndef Heap_H__
#define Heap_H__
#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:
struct Node{
Element value;
Node* l_child;
Node* r_child;
size_t weight;
Node(Element const& _value);
};
//
Node* root;
//
void clear(Node* _node );
Node* dup (Node* _node2 );
Node* merge(Node* _left, Node* _right);
public:
MergeableHeap();
MergeableHeap(MergeableHeap const& _heap2);
MergeableHeap& operator=(MergeableHeap const& _heap2);
~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);
//#|==============================================
};
//# [WARNING]
//#==============================================
//# * 假設現在有兩個MergeableHeap `A` 和 `B`, 則:
//# ** 執行 `A.merge(&B)` 後 `B` 會變成空的
//# ** 執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉
//#==============================================
//#
//# '''
//#
}
#include "MergeableHeap.hpp"
#endif // Heap_H__
|
