1 files changed, 84 insertions, 0 deletions
diff --git a/meowpp/dsa/Heaps.h b/meowpp/dsa/Heaps.h
new file mode 100644
index 0000000..cac3e01
--- /dev/null
+++ b/meowpp/dsa/Heaps.h
@@ -0,0 +1,84 @@
+#ifndef   Heap_H__
+#define   Heap_H__
+
+#include <cstdlib>
+
+namespace meow{
+  /*********************************************************
+    @asciidoc
+    === 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)`
+    @asciidoc-
+   *********************************************************/
+  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);
+  };
+}
+
+#include "MergeableHeap.hpp"
+
+#endif // Heap_H__