//大根堆
 #ifndef __HEAP__
#define __HEAP__
 
 #include <algorithm>
#include <assert.h>
 
 namespace HEAP{
 
      template<typename T>
 
      class Heap{
           public:
                 Heap(const int size = 0) : m_size(size), m_datas(new T [size]){}
                 ~Heap(){
                      delete [] m_datas;
                }
 
                T get_data(const int index){
 
                      assert(index >= 0 && index < m_len);
                      return m_datas[index];  
 
                 }
 
                 // 取得堆里的最大元素 
       bool pop(T & data){
 
                      if(is_empty()){
                            return false; 
                      }
 
                      swap(m_datas[0], m_datas[--m_len]);
                      data = m_datas[m_len];
                      adjust_topDown(0);
                      return true;
 
                 }
 
                 // 把元素插入堆结构中 
       bool push(const T & data){
 
                      if (m_len >= m_size){
                            return false;
                      }
 
                      m_datas[m_len++] = data;
                      adjust_bottomUp(0, m_len);
                      return true;
 
                 }
 
                 // 使数组成为堆结构化 
       bool heapify(const T * datas, const int len){
 
                      for(int i = 0; i < len; ++i){
                            m_datas[i] = datas[i];
                      }
 
                      m_len = len;          
                      for(int i = m_len/2; i >= 0; --i){
                            adjust_topDown(i);
                      }
 
                 }
 
                 int size() const { return m_len; }
                 bool is_empty() const { return m_len == 0; }
 
           private:
                  // 向下调整堆结构 
       void adjust_topDown(const int root_coord){
 
                      int coord = root_coord;
                      int child_coord = 2*root_coord+1;
                      while(child_coord < m_len){
 
                            if(child_coord+1 < m_len){
                                  child_coord = m_datas[child_coord] > m_datas[child_coord+1] ? child_coord : child_coord+1;
 
                            }
                            if(m_datas[coord] < m_datas[child_coord]){
                                  swap(m_datas[coord], m_datas[child_coord]);
                                  coord = child_coord;
                                  child_coord = coord*2 + 1;
                            }else{
                                  break;
                            }
                      }
                 }
 
                    //向上调整堆结构 
        void adjust_bottomUp(const int root_coord, const int heap_len){
 
                      int coord = heap_len-1;
                      while(coord > root_coord && m_datas[coord] > m_datas[(coord-1)/2]){
                            swap(m_datas[coord], m_datas[(coord-1)/2]);
                            coord = (coord-1) / 2;
                      }
                 }
 
                 T * m_datas;
                 int m_size;
                 int m_len = 0;
 
      };
 
};
 
 #endif
 
 //索引堆
 //利用索引来实现堆结构，不改变原始数据的原始排列顺序，以索引方式变化实现堆
 #ifndef __INDEXHEAP__
#define __INDEXHEAP__
 
 namespace INDEXHEAP{
 // 索引堆 
 
 template<typename T>
      class IndexHeap{
                 public:
                 IndexHeap(const int size = 0) : m_size(size), m_datas(new T [size]), m_indexes(new int [size]){
 
                      for(int i = 0; i < size; ++i){
                            m_indexes[i] = i;
                      }
                 }
 
                 ~IndexHeap(){
                      delete [] m_datas;
                      delete [] m_indexes;
                }
 
                T get_data(const int index){
                      assert(index >= 0 && index < m_len);
                      return m_datas[m_indexes[index]];
                 }
                 void change_data(const int index, const T & data){
 
                      assert(index >= 0 && index < m_len);
                      m_datas[m_indexes[index]] = data;
                      adjust_topDown(index);
                      adjust_bottomUp(0, index+1);
                 }
                 
                 bool pop(T & data){
 
                      if(is_empty()){
                            return false; 
 
                      }
 
                      swap(m_indexes[0], m_indexes[--m_len]);
                      data = m_datas[m_indexes[m_len]];
                      adjust_topDown(0);
                      return true;
 
                 }
 
                 bool push(const T & data){
 
                      if (m_len >= m_size){
                            return false;
                      }
                      
                      m_datas[m_indexes[m_len++]] = data;
                      adjust_bottomUp(0, m_len);
                      return true;
 
                 }
 
                 bool heapify(const T * datas, const int len){
 
                      for(int i = 0; i < len; ++i){
                            m_datas[m_indexes[i]] = datas[i];
                      }
                      
                      m_len = len;          
                      for(int i = m_len/2; i >= 0; --i){
                            adjust_topDown(i);
 
                      }
 
                 }
 
                 int size() const { return m_len; }
                 bool is_empty() const { return m_len == 0; }
 
           private:
 
                 void adjust_topDown(const int root_coord){
 
                      int coord = root_coord;
                      int child_coord = 2*root_coord+1;
                      while(child_coord < m_len){
                            if(child_coord+1 < m_len){
                                  child_coord = m_datas[m_indexes[child_coord]] > m_datas[m_indexes[child_coord+1]] ? child_coord : child_coord+1;
                            }
 
                            if(m_datas[m_indexes[coord]] < m_datas[m_indexes[child_coord]]){
 
                                  swap(m_indexes[coord], m_indexes[child_coord]);
                                  coord = child_coord;
                                  child_coord = coord*2 + 1;
 
                            }else{
                                  break;
                            }
                      }
                 }
 
                 void adjust_bottomUp(const int root_coord, const int heap_len){
 
                      int coord = heap_len-1;
                      while(coord > root_coord && m_datas[m_indexes[coord]] > m_datas[m_indexes[(coord-1)/2]]){
                            swap(m_indexes[coord], m_indexes[(coord-1)/2]);
                            coord = (coord-1) / 2;
                      }
                 }
 
                 T * m_datas;
                 int * m_indexes;
                 int * m_rev_indexes;
                 int m_size;
                 int m_len = 0;
 
      };  
 
};
 
 #endif