算法与数据结构——大顶堆 and 小顶堆

0.定义

大顶堆：树中所有根节点必须大于等于其左儿子和右儿子，因此根节点是最大值。
小顶堆：树中所有根节点必须大于等于其左儿子和右儿子，因此根节点是最小值。

1.自己实现大顶堆和小顶堆

#pragma once  #include <vector> #include <iostream> #include <assert.h> using namespace std;   // 小顶堆 template <class T> struct myGreater {     bool operator()(const T &left, const T &right) { return left > right; } };  // 大顶堆 template <class T> struct myLess {     bool operator()(const T &left, const T &right) { return left < right; } };  template <class T, class Compare = myLess<T>> class myHeap { public:     myHeap() {}      myHeap(vector<T> vec)     {         _array.reserve(vec.size());         _array.assign(vec.begin(), vec.end());          // 建堆         for (int i = _array.size() / 2 - 1; i >= 0; i--)             AjustDown(i);     }      bool empty() const { return _array.empty(); }      size_t size() const { return _array.size(); }      T &top()     {         assert(!_array.empty());         return _array[0];     }      void push(T elem)     {         _array.push_back(elem);         AjustUp(_array.size() - 1);     }      void pop()     {         assert(!_array.empty());         swap(_array[0], _array[_array.size() - 1]);         _array.pop_back();         AjustDown(0);     }  private:     void AjustDown(int parent)     {         int child = parent * 2 + 1; // left child idx         while (child < _array.size())         {             if (child + 1 < _array.size() && cmp(_array[child], _array[child + 1]))                 ++child;              if (cmp(_array[parent], _array[child]))             {                 swap(_array[parent], _array[child]);                 parent = child;                 child = 2 * parent + 1;             }             else                 break;         }     }      void AjustUp(int child)     {         int parent = (child - 1) / 2;         while (parent >= 0)         {             if (cmp(_array[parent], _array[child]))             {                 swap(_array[parent], _array[child]);                 child = parent;                 parent = (child - 1) / 2;             }             else                 break;         }     }      vector<T> _array;     Compare cmp; };  template <typename T> using maxHeap = myHeap<T,myLess<T>>;  template <typename T> using minHeap = myHeap<T,myGreater<T>>;   int main() {     vector<int> a = {11, 10, 13, 12, 16, 18, 15, 17, 14, 19};     myHeap<int> hp1(a);      cout << hp1.top() << endl;     hp1.push(90);     hp1.push(900);     cout << hp1.top() << endl;     hp1.pop();     hp1.pop();     hp1.pop();     hp1.pop();     hp1.pop();     hp1.pop();     hp1.pop();      // system("pause");     return 0; }  

比较重要的是：

1. 仿函数的写法：大顶堆是left<right，命名为Less;小顶堆是left>right，命名为Greater。
2. 堆调整是cmp(_array[parent], _array[child])或者cmp(_array[left_child], _array[right_child])，这个顺序是和第一步仿函数的写法对应。这个过程详细描述如下：（以Less为例），Less是left<right写法，
   第一步，进行左孩子取值 < 右孩子取值比较，如果为真，使用右孩子与父节点比较，否则使用做孩子与父节点比较（见 AjustDown 函数体内 while 循环后第一个 if 语句）；
   第二步，在父节点取值 < 孩子节点取值时，交换父和子，于是取值较大的孩子节点成为根节点（也就是说这个堆是大顶堆）。

2.STL优先队列

给自己打个广告：找工作准备刷题day1 栈与队列

优先队列练手：Leetcode347.前K个高频元素

自己写完以后更好地理解 为什么 小顶堆 的仿函数 是 >