当前位置：首页 > news >正文

斜堆(数据结构篇)

news 2025/7/19 11:44:18

数据结构之斜堆

斜堆

概念：

斜堆是左式堆的自调节形式，斜堆和左式堆间的关系类似于伸展树和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;
};