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
|
#include <cstdlib>
namespace meow{
//////////////////////////////////////////////////////////
// **# MergeableHeap--Node-- constructor #** //
//////////////////////////////////////////////////////////
template<class Element>
inline
MergeableHeap<Element>::Node::Node(Element const& _value): // Node
value(_value), l_child(NULL), r_child(NULL), weight(1){ }
//////////////////////////////////////////////////////////
// **# MergeableHeap -- clear, duplicate #** //
//////////////////////////////////////////////////////////
template<class Element>
inline void
MergeableHeap<Element>::clear(Node* _node){ //clear
if(_node != NULL){
clear(_node->l_child);
clear(_node->r_child);
delete _node;
}
}
template<class Element>
inline typename MergeableHeap<Element>::Node*
MergeableHeap<Element>::dup(Node* _node2){ // dup
if(_node2 == NULL) return NULL;
Node* ret = new Node(_node2->value);
ret->l_child = dup(_node2->l_child);
ret->r_child = dup(_node2->r_child);
ret->weight = 1;
ret->weight += (ret->l_child == NULL ? 0 : ret->l_child->weight);
ret->weight += (ret->r_child == NULL ? 0 : ret->r_child->weight);
return ret;
}
//////////////////////////////////////////////////////////
// **# MergeableHeap -- merge #** //
//////////////////////////////////////////////////////////
template<class Element>
inline typename MergeableHeap<Element>::Node*
MergeableHeap<Element>::merge(Node* _left, Node* _right){ //merge
if(_left == NULL) return _right;
if(_right == NULL) return _left;
if(_left->value < _right->value){
std::swap(_left, _right);
}
_left->r_child = merge(_left->r_child, _right);
size_t lw = (_left->l_child == NULL ? 0 : _left->l_child->weight);
size_t rw = (_left->r_child == NULL ? 0 : _left->r_child->weight);
if(lw < rw){
std::swap(_left->l_child, _left->r_child);
}
_left->weight = 1 + lw + rw;
return _left;
}
//////////////////////////////////////////////////////////
// **# MergeableHeap -- constrctors/destructors #** //
//////////////////////////////////////////////////////////
template<class Element>
inline
MergeableHeap<Element>::MergeableHeap(): //MergeableHeap
root(NULL){ }
template<class Element>
inline
MergeableHeap<Element>::MergeableHeap(MergeableHeap const& _heap2):
root(NULL){
root = dup(_heap2.root);
}
template<class Element>
inline
MergeableHeap<Element>::~MergeableHeap(){ //~MergeableHeap
clear(root);
}
//////////////////////////////////////////////////////////
//**# MergeableHeap -- copy operation/data transform #**//
//////////////////////////////////////////////////////////
template<class Element>
inline MergeableHeap<Element>&
MergeableHeap<Element>::operator=(MergeableHeap const& _heap2){ // =
root = dup(_heap2.root);
return *this;
}
template<class Element>
inline void
MergeableHeap<Element>::moveTo(MergeableHeap* _heap2){ // moveTo
_heap2->clear();
_heap2->root = root;
root = NULL;
}
//////////////////////////////////////////////////////////
// **# MergeableHeap -- access: top, size, emtpy #** //
//////////////////////////////////////////////////////////
template<class Element>
inline Element const&
MergeableHeap<Element>::top() const{ // top
return root->value;
}
template<class Element>
inline size_t
MergeableHeap<Element>::size() const{ // size
return (root == NULL ? 0 : root->weight);
}
template<class Element>
inline size_t
MergeableHeap<Element>::empty() const{ // empty
return (size() == 0);
}
//////////////////////////////////////////////////////////
// **# MergeableHeap -- update: push, pop, merge #** //
//////////////////////////////////////////////////////////
template<class Element>
inline void
MergeableHeap<Element>::push(Element const& _value){ // push
Node* new_node = new Node(_value);
root = merge(root, new_node);
}
template<class Element>
inline void
MergeableHeap<Element>::pop(){ // pop
Node* l = root->l_child;
Node* r = root->r_child;
delete root;
root = merge(l, r);
}
template<class Element>
inline void
MergeableHeap<Element>::merge(MergeableHeap* _heap2){ // merge
root = merge(root, _heap2->root);
_heap2->root = NULL;
}
//////////////////////////////////////////////////////////
// **# MergeableHeap -- refresh: clear #** //
//////////////////////////////////////////////////////////
template<class Element>
inline void
MergeableHeap<Element>::clear(){ // clear
clear(root);
root = NULL;
}
}
|
