blob: 8058527d6e49d68a2e0103b77e09e27c7d1c771e (
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
|
==== hi!!
=== MergeableHeap<Key, Value>
.Description
MergeableHeap is a kind of maximum-heap with an extra method `merge`,
which will merge another MergeableHeap into itself.
.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,5<,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)`
|
