堆

1.概念

堆是一种完全二叉树（除了最底层，其它层都必须填满，最后一层可以从左到右填满），堆的每一个节点都有一个值。

数据结构里的堆是由一些按照某种优先级来组织成的队列，所以堆又叫做优先队列，在STL中可以用priority_queue实现。

2.分类

堆可以分为最大堆和最小堆：

• 最大堆：每个父节点都大于各孩子节点

• 最小堆：每个父节点都小于各孩子节点

  3.存储和性质

  堆是一棵完全二叉树，所以使用数组可以高效的存储数据。

性质：

• 对于一个非根节点的节点 i 来说，如果它的下标为 k，那么它的父节点的下标为 (k -1)/2，子节点的下标为2 *k +1和2 *k + 2
• 每个结点的左子树和右子树都是一个二叉堆

4.堆的实现

现有数组 int* a={10,5,7,12,13,11,20,25,14,30};
根据这个数组建出一个带值的完全二叉树。
现在我们要使这个完全二叉树变成最大堆，就是让整棵树中的双亲节点都大于孩子节点。所以我们要从叶子结点开始调整，直到调整到根节点结束。

template<class T>
struct Less {
    bool operator()(const T& a,const T& b) {
        return a<b;
    }
};
template<class T>
struct Greater {
    bool operator()(const T& a,const T& b) {
        return a>b;
    }
};

template<typename T,class com = Greater<int>>
class Heap {
public:
    //构造函数
    Heap(){}
    //建堆
    Heap(T* a, size_t n)
        :_a(a,a+n) {
        for (int i = (_a.size()-2)/2; i>=0; i--) {
            _Adjustdown(i);
        }
    }
    //尾插
    void Push(const T& x) {
        _a.push_back(x);
        _Adjustup(_a.size()-1);
    }
    //尾删
    void Pop() {
        swap(_a[0],_a[_a.size()-1]);
        _a.pop_back();
        _Adjustdown(0);
    }
    //求堆里元素的个数
    size_t Size() {
        return _a.size();
    }
    //求堆顶的元素
    T& Top() {
        return _a[0];
    }
    //判断堆是否为空
    bool Empty() {
        return _a.size()==0;
    }

protected:
    void _Adjustdown(int root) {//下调
        int parent = root;
        int child = parent*2+1;
        while (child<_a.size()) {
            //找左右孩子中值最大的
            if (child+1<_a.size() && com()(_a[child+1],_a[child])) {
                ++child;
            }
            //将孩子和父母做比较
            if (com()(_a[child],_a[parent])) {
                swap(_a[child],_a[parent]);
                parent = child;
                child = parent*2+1;
            } else {
                break;
            }
        }
    }
    //上调
    void _Adjustup(int i) {
        //Compare com;
        int child = i;
        int parent = (i-1)/2;
        while (child >= 0) {
            if (com()(_a[child] , _a[parent])) {
                swap(_a[child],_a[parent]);
                child = parent;
                parent = (parent-1)/2;
            } else {
                break;
            }
        }
    }
  protected:
      vector<T> _a;
};
template<class T,class com = Greater<int>>
class PriorityQueue {
  public:
    //构造函数
      PriorityQueue() {}
      void Push_Back(const T& x) {
        _hp.Push(x);
    }
      void Pop_Front() {
          _hp.Pop();
      }
      size_t PQ_Size() {
          return _hp.Size();
      }
      T& PQ_Top() {
          return _hp.Top();
      }
      bool PQ_Empty() {
          return _hp.Empty();
      }
  protected:
      Heap<T,com> _hp;
};