如何做网站的薪酬调查,东莞seo建站公司哪家好,重庆sem优化,做美食视频的网站数据结构之斜堆
斜堆
概念#xff1a;
斜堆是左式堆的自调节形式#xff0c;斜堆和左式堆间的关系类似于伸展树和AVL树间的关系斜堆是具有堆序性的二叉树#xff0c;但是不存在对树的结构限制不同于左式堆#xff0c;关于任意节点的零路径长的任何信息都不保留#xff…数据结构之斜堆
斜堆
概念
斜堆是左式堆的自调节形式斜堆和左式堆间的关系类似于伸展树和AVL树间的关系斜堆是具有堆序性的二叉树但是不存在对树的结构限制不同于左式堆关于任意节点的零路径长的任何信息都不保留因为斜堆的右路径在任何时刻都可以任意长
合并操作
斜堆的合并大概都跟左式堆的合并操作一样但是交换操作不一样斜堆的交换是无条件的就是说当进行将大的根值的堆与小的根值的堆的右子堆合并后我们就需要进行左子树跟右子树交换的操作并不是只有到最后小的根值的堆跟新的堆合并后在进行交换就是每个合并的步骤就需要交换左右子树。
实现代码
struct heapNode{int data;heapNode* left;heapNode* right;
};class skewheap{
public:skewheap(){rootnew heapNode;root-dataINT_MAX;root-left nullptr;root-right nullptr;}heapNode* createNode(int data){auto pnew heapNode;p-data data;p-left nullptr;p-right nullptr;return p;}heapNode* merge(heapNode* h1,heapNode* h2){if(h1-left nullptr){h1-lefth2;}else{h1-right findmerge_node(h1-right,h2);heapNode* ph1-left;h1-lefth1-right;h1-rightp;}return h1;}heapNode* findmerge_node(heapNode* h1,heapNode* h2){if(nullptrh1){return h2;}if(nullptrh2){return h1;}if(h1-datah2-data){return merge(h1,h2);}else{return merge(h2,h1);}}void insert(int data){heapNode* add createNode(data);if(root-dataINT_MAX){rootadd;}elserootfindmerge_node(root,add);}void delmin(){if(nullptrroot){return;}heapNode* h1root-left;heapNode* h2root-right;delete root;root findmerge_node(h1,h2);}int getmin(){return root-data;}heapNode* print(heapNode* p){if(p! nullptr){coutp-data ;print(p-left);print(p-right);}return p;}void print(){if(root nullptr){return;}print(root);}
private:heapNode* root;
};尾言
完整版笔记也就是数据结构与算法专栏完整版可到我的博客进行查看或者在github库中自取(包含源代码) 博客1 codebooks.xyz博客2moonfordream.github.iogithub项目地址Data-Structure-and-Algorithms
