#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__