blob: 1e47afd1e2ea0c7ca0afc2e53e98a9e8b56ba8e4 (
plain) (
blame)
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
|
#ifndef Heap_H__
#define Heap_H__
#include <cstdlib>
namespace meow{
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();
//
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( );
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-
*********************************************************/
}
#include "MergeableHeap.hpp"
#endif // Heap_H__
|
