左式堆(数据结构篇)

数据结构之左式堆

左式堆

概念：

左式堆是一种能够高效的支持合并操作的堆，左式堆的底层也是由二叉树实现，但是左式堆不是平衡的(不由完全二叉树实现的)，左式堆趋向于不平衡。
左式堆也像二叉堆一样拥有着堆的特性(有序性和结构性)，左式堆是最小堆
左式堆是一个拥有堆序性的二叉树(不是二叉堆)加上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;
        } else
            root=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;
};