左式堆的实现与详解

左式堆的性质:

像二叉堆那样既有结构性质，又有堆序性质。事实上，和所有使用的堆一样，左式堆具有相同的堆序性质，该性质我们已经看到过。不仅如此，左式堆也是二叉树，左式堆和二叉堆唯一的区别是:左式堆不是理想平衡的,而且事实上是趋于非常不平衡的。

零路径长：(null path length)

假设有个结点x,npl(x)定义为x到一个不具有两个儿子的结点的最短路径的长，因此，具有0个或1个儿子的结点的npl为0，而npl(null) = -1.

左式堆的操作:

由于两个左式堆需要合并，所以用数组就显得不是那么的合适了，因为需要把一个数组拷贝到另一个数组中去，对于大小相同的堆这将花费时间O(N),所以我们最好用链式结构来实现左式堆，而不是像二叉堆那样用数组(vector)去实现。

左式堆的插入:

左式堆的插入只是合并的特殊情形，因为可以把插入看成是单结点堆与一个大的堆的merge。

左式堆的合并:

假设有H1,H2两个堆需要合并，那么,如果这两个堆中有一个堆是空的，那么可以直接返回另外一个堆，否则，为了合并这两个堆，需要先比较他们的根，首先将具有大的根值的堆和具有小的根值的堆的右子堆合并。因为左式堆的子堆也应该是左式堆，所以可以利用递归这一性质来进行合并，递归的流程为:先比较两个堆根结点的大小，取根结点值大的堆和根结点值小的右子堆合并，再比较所取右子堆当前根结点和结点较大堆根结点值的大小，然后依次这样比较下去，直到结点不能再分位置，然后就可以开始执行合并，遇到一个堆为空时返回另外一个堆。然后再将其合并到h1的右子树上(h1假设总是根结点较小的那棵树),就这样下去，直到合并完成。

左式堆的删除(Deletemin):

删除根结点后，执行合并根结点的左子树和右子树的方法即可。

Findmin(返回最小值):

堆如果不为空的话，很明显最小值就是根结点，因为满足堆的性质。

左式堆的代码如下:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
class UnderflowException
{};
template<typename Comparable>
class LeftistHeap
{
public:
    LeftistHeap():root(NULL)
    {}
    LeftistHeap(const LeftistHeap &rhs)
    {
        *this = rhs;
    }
    ~LeftistHeap()
    {
        makeEmpty();
    }
    bool isEmpty() const;
    const Comparable & findMin() const;
    void insert(const Comparable & x);
    void deleteMin();
    void deleteMin(Comparable & minItem);
    void makeEmpty();
    void merge(LeftistHeap & rhs);
    const LeftistHeap & operator = (const LeftistHeap & rhs)
    {
        if(this != &rhs)
        {
            makeEmpty();
            root = clone(rhs.root);
        }
        return *this;
    }
private:
    struct LeftistNode
    {
        Comparable element;
        LeftistNode *left;
        LeftistNode *right;
        int npl; //零路径长(到不具有两个儿子结点的最小路径)
        LeftistNode(const Comparable &theElement,LeftistNode *lt = NULL,LeftistNode *rt = NULL,int np = 0)
        :element(theElement),left(lt),right(rt),npl(np) {}
    };
    LeftistNode *root;
    LeftistNode *merge(LeftistNode *h1,LeftistNode *h2);
    LeftistNode *merge1(LeftistNode *h1,LeftistNode *h2);
    void swapChildren(LeftistNode *t); //交换左右子树
    void reclaimMemory(LeftistNode *t);
    LeftistNode *clone(LeftistNode *t) const
    {
        if(t == NULL)
            return NULL;
        else
            return new LeftistNode(t->element,clone(t->left),clone(t->right));
    }
};
template<typename Comparable>
void LeftistHeap<Comparable>::merge(LeftistHeap &rhs)
{
    if(this == &rhs)   //避免自己和自己合并
    {
        return;
    }
    root = merge(root,rhs.root);
    rhs.root = NULL; //合并完那棵树就没了
}
template<typename Comparable>
typename LeftistHeap<Comparable>::LeftistNode *LeftistHeap<Comparable>::merge(LeftistNode *h1,LeftistNode *h2)
{
    if(h1 == NULL)
        return h2;
    if(h2 == NULL)
        return h1;
    if(h1->element < h2->element)  //第一个参数为根结点小的那个
        return merge1(h1,h2);
    else
        return merge1(h2,h1);
}
template<typename Comparable>
typename LeftistHeap<Comparable>::LeftistNode *LeftistHeap<Comparable>::merge1(LeftistNode *h1,LeftistNode *h2)
{
    if(h1->left == NULL) //单个结点
    {
        h1->left = h2;
    }
    else  //递归的思路就是 :合并小的左式堆，一直合并，最后变成所要求的左式堆
    {
        h1->right = merge(h1->right,h2); //一直取当前根结点小的h1的右子树和h2合并，然后成为h1的右子树
        if(h1->left->npl <h1->right->npl) //如果合并后破坏了左式堆的性质，那就交换左右子堆
        {
            swapChildren(h1);
        }
        h1->npl = h1->right->npl + 1;
    }
    return h1;
}
template<typename Comparable>
void LeftistHeap<Comparable>::insert(const Comparable &x)
{
    root = merge(new LeftistNode(x),root);
}
template<typename Comparable>
const Comparable &LeftistHeap<Comparable>::findMin() const
{
    if(!isEmpty())
    return root->element;
}
template<typename Comparable>
bool LeftistHeap<Comparable>::isEmpty() const
{
    return root == NULL;
}
template<typename Comparable>
void LeftistHeap<Comparable>::reclaimMemory(LeftistNode *t)
{
    if(t != NULL)
    {
        reclaimMemory(t->left);
        reclaimMemory(t->right);
        delete t;
    }
}
template<typename Comparable>
void LeftistHeap<Comparable>::makeEmpty()
{
    reclaimMemory(root);
    root = NULL;
}
template<typename Comparable>
void LeftistHeap<Comparable>::swapChildren(LeftistNode *t) //如果破坏了左式堆的性质，那么就交换根结点的左右子堆
{
    LeftistNode *tmp = t->left;
    t->left = t->right;
    t->right = tmp;
}
template<typename Comparable>
void LeftistHeap<Comparable>::deleteMin()
{
    if(isEmpty())
    {
        throw UnderflowException();
    }
    LeftistNode *oldRoot = root;
    root = merge(root->left,root->right); //删除根结点,让左子堆和右子堆合并
    delete oldRoot;
}
template<typename Comparable>
void LeftistHeap<Comparable>::deleteMin(Comparable & minItem)
{
    minItem = findMin();
    deleteMin();
}
int main()
{
    LeftistHeap<int> leftistHeap1,leftistHeap2;
    cout<<"enter first heap,total m numbers:"<<endl;
    int m,n,num;
    //freopen("111","r",stdin);
    cin>>m;
    for(int i=0;i<m;i++)
    {
        cin>>num;
        leftistHeap1.insert(num); //第一个堆
    }
    cout<<"enter first heap,total n numbers:"<<endl;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>num;
        leftistHeap2.insert(num); //第二个堆
    }
    leftistHeap1.merge(leftistHeap2);
    cout<<"minimum is:"<<leftistHeap1.findMin()<<endl;
    if(leftistHeap1.isEmpty())
    {
        cout<<"leftistHeap1 is empty!"<<endl;
    }
    else
    {
        cout<<"leftistHeap1 is not empty!"<<endl;
    }
    if(leftistHeap2.isEmpty())
    {
        cout<<"leftistHeap2 is empty!"<<endl;
    }
    else
    {
        cout<<"leftistHeap2 is not empty!"<<endl;
    }
    int t;
    while(leftistHeap1.isEmpty() == false)
    {
        leftistHeap1.deleteMin(t);
        cout<<t<<" ";
    }
    cout<<endl;
    if(leftistHeap1.isEmpty())
    {
        cout<<"leftistHeap1 is empty!"<<endl;
    }
    else
    {
        cout<<"leftistHeap1 is not empty!"<<endl;
    }
    return 0;
}