change0

2 files changed, 92 insertions, 1 deletions

diff --git a/meowpp/dsa/KD_Tree.hpp b/meowpp/dsa/KD_Tree.hpp
index 9e9a925..ac9f868 100644
--- a/meowpp/dsa/KD_Tree.hpp
+++ b/meowpp/dsa/KD_Tree.hpp
@@ -146,7 +146,7 @@ namespace meow{
   template<class Keys, class Key, class Value>
   inline void KD_Tree<Keys, Key, Value>::build(){
     if(needRebuild){
-      std::vector<size_t> orders[dimension + 1];
+      std::vector<size_t> *orders = new std::vector<size_t>[dimension + 1];
       for(int j = 0; j < dimension + 1; j++){
         orders[j].resize(nodes.size());
       }
@@ -158,6 +158,7 @@ namespace meow{
       }
       root = build(0, (ssize_t)nodes.size() - 1, orders, 0);
       needRebuild = false;
+      delete [] orders;
     }
   }
   template<class Keys, class Key, class Value>
diff --git a/meowpp/dsa/MergeableHeap.h b/meowpp/dsa/MergeableHeap.h
new file mode 100644
index 0000000..1e47afd
--- /dev/null
+++ b/meowpp/dsa/MergeableHeap.h
@@ -0,0 +1,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__