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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
|
#ifndef dsa_MergeableHeap_H__
#define dsa_MergeableHeap_H__
#include <cstdlib>
#include <algorithm>
namespace meow {
/*!
* @brief
*
* 一個用 \b 左偏樹 實作的 \c Maximum-Heap , 除了原本heap有的功能外,
* 還支援 \c merge 功能
*
* Template Class Operators Request
* --------------------------------
*
* |const?|Typename|Operator | Parameters |Return Type | Description |
* |-----:|:------:|----------:|:-------------|:----------:|:------------------|
* |const |Element |operator< |(Element \c b)|bool | 大小比較 |
*
* @note:
* 假設現在有兩個MergeableHeap \c A 和 \c B, 則:
* - 執行 \c A.merge(&B) 後 \c B 會變成空的
* - 執行 \c B.moveTo(&A) 後 \c B 會變成空的, \c A 原本擁有的資料也會覆蓋掉
*
* @author cat_leopard
*/
template<class Element>
class MergeableHeap { // maximum-heap
private:
struct Node {
Element value_;
Node* lChild_;
Node* rChild_;
size_t weight_;
Node(Element const& value):
value_(value), lChild_(NULL), rChild_(NULL), weight_(1){
}
};
Node* root_;
void clear(Node* node) {
if (node != NULL) {
clear(node->lChild_);
clear(node->rChild_);
delete node;
}
}
Node* dup(Node* node) {
if (node == NULL) return NULL;
Node* ret = new Node(node->value_);
ret->lChild_ = dup(node->lChild_);
ret->rChild_ = dup(node->rChild_);
ret->weight_ = 1;
ret->weight_ += (ret->lChild_ == NULL ? 0 : ret->lChild_->weight_);
ret->weight_ += (ret->rChild_ == NULL ? 0 : ret->rChild_->weight_);
return ret;
}
Node* merge(Node* left, Node* right) {
if (left == NULL) return right;
if (right == NULL) return left;
if (left->value_ < right->value_) {
std::swap(left, right);
}
left->rChild_ = merge(left->rChild_, right);
size_t lw = (left->lChild_ == NULL ? 0 : left->lChild_->weight_);
size_t rw = (left->rChild_ == NULL ? 0 : left->rChild_->weight_);
if (lw < rw) {
std::swap(left->lChild_, left->rChild_);
}
left->weight_ = 1 + lw + rw;
return left;
}
public:
//! @brief constructor
MergeableHeap(): root_(NULL){
}
//! @brief constructor, 並且複製資料
MergeableHeap(MergeableHeap const& heap2): root_(dup(heap2.root_)) {
}
//! @brief destructor
~MergeableHeap(){
clear(root_);
}
//! @brief 複製資料
MergeableHeap& copyFrom(MergeableHeap const& heap2) {
delete root_;
root_ = dup(heap2.root_);
return *this;
}
/*!
* @brief 將自己的資料丟給指定的heap, 從此自己一身空
*/
void moveTo(MergeableHeap* heap2){
heap2->clear();
heap2->root_ = root_;
root_ = NULL;
}
/*!
* @brief 回傳最大的那個 Element
*/
Element const& top() const {
return root_->value_;
}
/*!
* @brief 回傳資料個數
*/
size_t size() const {
return (root_ == NULL ? 0 : root_->weight_);
}
/*!
* @brief 回傳是否為空
*/
bool empty() const {
return (size() == 0);
}
/*!
* @brief 加入element
*/
void push(Element const& value) {
root_ = merge(root_, new Node(value));
}
/*!
* @brief 將最大的element移除
*/
void pop() {
Node* l = root_->lChild_;
Node* r = root_->rChild_;
delete root_;
root_ = merge(l, r);
}
/*!
* 將資料清空
*/
void clear() {
clear(root_);
root_ = NULL;
}
/*!
* 將給定的MergeableHeap的資料統統加到自己身上並且清空該heap
*/
void merge(MergeableHeap* heap2) {
root_ = merge(root_, heap2->root_);
heap2->root_ = NULL;
}
//! @brief same as \c copyFrom(heap2)
MergeableHeap& operator=(MergeableHeap const& heap2) {
return copyFrom(heap2);
}
};
} // meow
#endif // dsa_MergeableHeap_H__
|
