skewheap.h

来自「数据结构」· C头文件 代码 · 共 109 行

#ifndef _skewHeap
#define _skewHeap

#include"node.h"
#include"priorityQueue.h"

#include<assert.h>

template<class T>


class skewHeap:public priorityQueue<T>
{
 public:
    skewHeap();
    skewHeap(const skewHeap<T>& v);
    virtual ~skewHeap();
    virtual void add(T value);
    virtual int isEmpty()const;
    virtual T min()const;
    virtual void removeMin();
    void deleteAllValues();
    void add(skewHeap<T>& secondHeap);
 
 private:
    node<T>*root;
    node<T>*merge(node<T>*,node<T>*);
};

template<class T>
skewHeap<T>::skewHeap():root(0)
{}

template<class T>
skewHeap<T>::skewHeap(const skewHeap<T>& v)
{  root=(v.root==0?0:v.root->copy());
}

template<class T>
void skewHeap<T>::deleteAllValues()
{
  while(root)
    {
      root->release();
      delete root;
    }
}

template<class T>
skewHeap<T>::~skewHeap()
{
  deleteAllValues();
}

template<class T>
int skewHeap<T>::  isEmpty()const
{
 return (root==0);
 }

template<class T>
void skewHeap<T>::removeMin()
{
    assert(!isEmpty());
    node<T>*top=root;
    root=merge(root->right(),root->left());
    delete top;
}

template<class T>
void skewHeap<T>::add(T val)
{
    node<T>*newnode=new node<T>(val);
    assert(newnode!=0);
    root=merge(root,newnode);
}

template<class T>
node<T>* skewHeap<T>::merge(node<T>* h1,node<T>* h2)
{
   if(!h1)return h2;
   if(!h2)return h1;
    if(h2->value<h1->value)
       return merge(h2,h1);
   node<T>*lchild=h1->left();
   if(lchild)
   {
       h1->left(merge(h1->right(),h2));
       h1->right(lchild);
   }
   else
       h1->left(h2);
   return h1;
}

template<class T>
void skewHeap<T>::add(skewHeap<T>& secondHeap)
{
    root=merge(root,secondHeap.root);
    secondHeap.root=0;
}

template<class T>
T skewHeap<T>::min()const
{
  return root->value;
}

#endif