#ifndef   Heap_H__
#define   Heap_H__

#include <cstdlib>

namespace meow{
  //#
  //#=== meow:: *MergeableHeap<Element>* (C++ class)
  //#==== Description
  //#  一個用 *左偏樹* 實作的 *Maximum-Heap* , 除了原本heap有的功能外,
  //#  還支援 `merge`, `split` 等功能
  //#
  //#==== Template Class Operators Request
  //#[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"]
  //#|=====================================================================
  //#|Const?|Typename| Operator  | Parameters  | Return_Type| Description
  //#|const |Element |operator<  |(Element `v`)| bool       | 大小比較
  //#|=====================================================================
  //#
  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& operator=(MergeableHeap const& _heap2);
      ~MergeableHeap();

      //#==== Support Methods
      //#
      //# * N <- `this` 中擁有的資料數
      //#
      //#[options="header",width="100%",cols="1>m,2>s,7<,3<,3^,20<",grid="rows"]
      //#|=====================================================================
      //#|Const?|Name | Parameters   | Return_Type| Time_Complexity| Description


      //#||moveTo|(MergeableHeap* `h`)|void|O(M)
      //#|將 `this` 的資料複寫到 `h` 上面, 同時清空自己, 
      //# 時間複雜度中的M是 `h` 所擁有的資料數
      void moveTo(MergeableHeap* _heap2);


      //#|const|top|()|Element const&|O(1)
      //#|回傳最大的那個 `Element`
      Element const& top() const;


      //#|const|size|()|size_t|O(1)
      //#|回傳 `this` 中擁有的資料數
      size_t size() const;


      //#|const|empty|()|bool|O(1)
      //#|回傳 `this` 是否為空
      bool empty() const;


      //#||push|(Element const& `e`)|void|O(logN)
      //#|將 `e` 加入
      void push(Element const& _value);


      //#||pop|()|void|O(logN)
      //#|將最大的 `Element` 移除
      void pop();


      //#||clear|()|void|O(N)
      //#|將資料清空
      void clear();


      //#||merge|(MergeableHeap* `heap2`)|void|O(logN+logM)
      //#|將 `heap2` 的資料統統加到 `this` 中, 並且清空 `heap2`
      //# 時間複雜度中的M是 `heap2` 的資料數
      void merge(MergeableHeap* _heap2);

      //#|==============================================
  };
  //# [WARNING]
  //#==============================================
  //# * 假設現在有兩個MergeableHeap `A` 和 `B`,  則:
  //# ** 執行 `A.merge(&B)` 後 `B` 會變成空的
  //# ** 執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉
  //#==============================================
  //# 
  //# '''
  //# 
}

#include "MergeableHeap.hpp"

#endif // Heap_H__