左式堆(数据结构篇)

2024-06-22 00:36

文章标签 数据结构左式

本文主要是介绍左式堆(数据结构篇)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数据结构之左式堆

左式堆

概念：

左式堆是一种能够高效的支持合并操作的堆，左式堆的底层也是由二叉树实现，但是左式堆不是平衡的(不由完全二叉树实现的)，左式堆趋向于不平衡。
左式堆也像二叉堆一样拥有着堆的特性(有序性和结构性)，左式堆是最小堆
左式堆是一个拥有堆序性的二叉树(不是二叉堆)加上NPL特性的一棵树，任意节点X的NPL(X)(零路径长)为从X到一个没有两个儿子的节点的最短路径的长，因此，具有0个或1个儿子的节点的Npl为0，而Npl(NULL)=-1.

性质：

任意一个节点的零路径长比它的子节点的零路径长的最小值+1
对于堆中的每一个节点X，左儿子的零路径长大于等于右儿子的零路径长
在右路径上有r个节点的左式树必然至少有2^r-1个节点
对左式堆的右路径的插入和合并操作可能会破坏左式堆的性质，需要进行调整

合并操作

插入其实就是合并的一个特殊情况
如果两个左式堆合并，有一个堆为空就返回另外一个堆，否则比较两个堆的根值
递归进去，我们将大的根值的堆与小的根值的堆的右子堆合并
然后递归返回后，将新的堆作为原来小的根值的堆的右孩子(也叫合并)。
如果这样形成的堆的右子堆的零路径长大于左子堆的，就将左子堆跟右子堆交换，并且更新零路径长，就完成了合并的操作。

实现代码：

#include <iostream>
using namespace std;struct heapNode{int data;    //数据heapNode* left;    //左子节点指针heapNode* right;   //右子节点指针int Npl;     //零路径长
};class leftheap{
public:leftheap(){root=new heapNode;root->left= nullptr;root->right= nullptr;root->data=INT_MAX;root->Npl=0;}heapNode* createNode(int data){auto p=new heapNode;p->data=data;p->left= nullptr;p->right= nullptr;p->Npl=0;return p;}heapNode* merge(heapNode* h1,heapNode* h2){if(h1->left== nullptr){h1->left=h2;}else{h1->right= findmerge_node(h1->right,h2);if(h1->left->Npl<h1->right->Npl){heapNode* p=h1->left;h1->left=h1->right;h1->right=p;}h1->Npl=h1->right->Npl+1;}return h1;}heapNode* findmerge_node(heapNode* h1,heapNode* h2){if(nullptr==h1){return h2;}else 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(root== nullptr){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;
};