斜堆(数据结构篇)

数据结构之斜堆

斜堆

概念：

• 斜堆是左式堆的自调节形式，斜堆和左式堆间的关系类似于伸展树和AVL树间的关系
• 斜堆是具有堆序性的二叉树，但是不存在对树的结构限制
• 不同于左式堆，关于任意节点的零路径长的任何信息都不保留，因为斜堆的右路径在任何时刻都可以任意长

合并操作

• 斜堆的合并大概都跟左式堆的合并操作一样，但是交换操作不一样，斜堆的交换是无条件的
• 就是说当进行将大的根值的堆与小的根值的堆的右子堆合并后，我们就需要进行左子树跟右子树交换的操作，并不是只有到最后小的根值的堆跟新的堆合并后在进行交换
• 就是每个合并的步骤就需要交换左右子树。

实现代码：

struct heapNode{int data;heapNode* left;heapNode* right;
};class skewheap{
public:skewheap(){root=new heapNode;root->data=INT_MAX;root->left= nullptr;root->right= nullptr;}heapNode* createNode(int data){auto p=new heapNode;p->data= data;p->left= nullptr;p->right= nullptr;return p;}heapNode* merge(heapNode* h1,heapNode* h2){if(h1->left== nullptr){h1->left=h2;}else{h1->right= findmerge_node(h1->right,h2);heapNode* p=h1->left;h1->left=h1->right;h1->right=p;}return h1;}heapNode* findmerge_node(heapNode* h1,heapNode* h2){if(nullptr==h1){return h2;}if(nullptr==h2){return h1;}if(h1->data<h2->data){return merge(h1,h2);}else{return merge(h2,h1);}}void insert(int data){heapNode* add= createNode(data);if(root->data==INT_MAX){root=add;}elseroot=findmerge_node(root,add);}void delmin(){if(nullptr==root){return;}heapNode* h1=root->left;heapNode* h2=root->right;delete root;root= findmerge_node(h1,h2);}int getmin(){return root->data;}heapNode* print(heapNode* p){if(p!= nullptr){cout<<p->data<<" ";print(p->left);print(p->right);}return p;}void print(){if(root== nullptr){return;}print(root);}
private:heapNode* root;
};

尾言

完整版笔记也就是数据结构与算法专栏完整版可到我的博客进行查看，或者在github库中自取(包含源代码)

• 博客1： codebooks.xyz
• 博客2：moonfordream.github.io
• github项目地址：Data-Structure-and-Algorithms