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
|
#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> // top
inline Element const& MergeableHeap<Element>::top()const{return root->value;}
template<class Element> // size
inline size_t MergeableHeap<Element>::size() const{
return (root == NULL ? 0 : root->weight);
}
template<class Element> // empty
inline bool MergeableHeap<Element>::empty() const{ return (size() == 0); }
//////////////////////////////////////////////////////////
// **# MergeableHeap -- update: push, pop, merge #** //
//////////////////////////////////////////////////////////
template<class Element>
inline void MergeableHeap<Element>::push(Element const& _value){ // push
root = merge(root, new Node(_value));
}
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;
}
}
|
