堆结构一般是采用固定长度的数组来实现的,虽然经典,但是存在扩容的负担,往往采用复制+预分配的策略进行。但是由于存在复制,在时间复杂度上就不是那么让人满意,为了解决这个问题,我们基于满二叉树来生成没有扩容负担的堆结构,时间复杂度降到O(logN)。
根据堆的特点,需要有建堆和维护堆这两个操作:
添加节点的时候进行建堆(从叶子往根),弹出根节点的时候进行维护堆操作(从根往叶子)。
根据满二叉树的特点,总是在最后添加新节点,需要一个指针last来引导节点添加的位置:
添加在last的前序遍历的后继节点上。删除节点时,将根节点的值作为返回值,再将last节点的值放入到根节点处,更新last,指向last前序遍历的前驱结点,然后进行维护堆操作。
typedef struct HeapNode {
int val;
HeapNode* left = nullptr;
HeapNode* right = nullptr;
HeapNode* parent = nullptr;
HeapNode(int v):val(v){}
} heapNode;
扩容堆结构:
class FlexHeap {
public:
typedef std::function< bool(int n1, int n2)> cmptor;
FlexHeap(cmptor& cmp):cmpare(cmp){}
void addNode(int val);
int popRoot();
private:
cmptor cmpare;
private:
heapNode* last = nullptr;
heapNode* root = nullptr;
int size = 0;
};
添加时:
弹出根节点时:
删除节点时,将根节点的值作为返回值,再将last节点的值放入到根节点处,更新last,使其指向last前序遍历的前驱结点,然后进行堆的维护操作。