image.png
    堆结构一般是采用固定长度的数组来实现的，虽然经典，但是存在扩容的负担，往往采用复制+预分配的策略进行。但是由于存在复制，在时间复杂度上就不是那么让人满意，为了解决这个问题，我们基于满二叉树来生成没有扩容负担的堆结构，时间复杂度降到O(logN)。
    image.png
    根据堆的特点，需要有建堆和维护堆这两个操作：

    添加节点的时候进行建堆(从叶子往根)，弹出根节点的时候进行维护堆操作(从根往叶子)。

    根据满二叉树的特点，总是在最后添加新节点，需要一个指针last来引导节点添加的位置：

    添加在last的前序遍历的后继节点上。删除节点时，将根节点的值作为返回值，再将last节点的值放入到根节点处，更新last，指向last前序遍历的前驱结点，然后进行维护堆操作。

    1.         typedef struct HeapNode {
    2.             int val;
    3.             HeapNode* left = nullptr;
    4.             HeapNode* right = nullptr;
    5.             HeapNode* parent = nullptr;
    6.             HeapNode(int v):val(v){}
    7.         } heapNode;

    扩容堆结构：

    1.         class FlexHeap {
    2.             public:
    3.                 typedef std::function< bool(int n1, int n2)> cmptor;
    4.                 FlexHeap(cmptor& cmp):cmpare(cmp){}
    5.                 void addNode(int val);
    6.                 int popRoot();
    7.             private:
    8.                 cmptor cmpare;
    9.             private:
    10.                 heapNode* last = nullptr;
    11.                 heapNode* root = nullptr;
    12.                 int size = 0;
    13.         };

    添加时：

    image.png
    弹出根节点时：

    删除节点时，将根节点的值作为返回值，再将last节点的值放入到根节点处，更新last，使其指向last前序遍历的前驱结点，然后进行堆的维护操作。

    image.pngimage.png