脚本宝典收集整理的这篇文章主要介绍了[DS] 易于合并的堆：左式堆和斜堆C++实现，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
原始的二叉堆使用数组实现，是一个完全二叉树，其实现简单，但是在合并方面不尽人意，只能通过构建一个新的堆来实现两个堆的合并，@R_604_1304@为O（N）。
而左式堆和斜堆是两种合并高效的堆，并且左式堆以及斜堆的insert以及deleteMin等操作都是以merge操作为基础的。merge时间复杂度可以达到O（LOGN）。
左式堆（Leftist Heaps）使用指针实现，它仍然使用二叉树的结构实现，仍满足堆序性，但它不是完全二叉树。相比于二叉树，其节点上增加了一个NPL （null path length）属性，它指的是从该结点到达一个没有两个孩子的结点的最短距离，NULL的NPL为-1。而左式堆的核心约束条件就是：任意结点的左孩子的Npl大于等于右孩子的Npl。
//
// Created by chnmagnus on 16-3-30.
//
#ifndef ADSPRO3_LEFTISTHEAP_H
#define ADSPRO3_LEFTISTHEAP_H
#include <iostream>
//the declaration of node class
template <class T>
class LNode{
public:
int npl; //npl
T data; //element
LNode * left; //pointer to left child
LNode * right; //point to right child
LNode() = default; //default constructor
//constructor
LNode(T element):data(element),left(nullptr),right(nullptr),npl(0){}
};
//the declaration of leftist heap class
template <class T>
class LeftistHeap{
public:
LNode<T> * root; //the root
LeftistHeap():root(nullptr){} //constructor
//merge two heap
//and the result is current heap
//instead another heap that is merged
void merge(LeftistHeap another);
LNode<T> * imerge(LNode<T>* a,LNode<T>* b);
LNode<T> * iimerge(LNode<T>* a,LNode<T>* b);
void insert(T element);//insert element
void deleteMin();//delete the root
void preprint(LNode<T>* LNode);//preorder print the heap
void inprint(LNode<T>* LNode);//inorder print the heap
};
//the drive function of imerge and iimerge
template <class T>
void LeftistHeap<T>::merge(LeftistHeap another){
this->root = imerge(this->root,another.root);
}
template <class T>
LNode<T>* LeftistHeap<T>::imerge(LNode<T> *a ,LNode<T> *b){
if(a==nullptr) return b;
if(b==nullptr) return a;
if(a->data<b->data) return iimerge(a,b);
else return iimerge(b,a);
}
template <class T>
LNode<T>* LeftistHeap<T>::iimerge(LNode<T> *a ,LNode<T> *b){
if(a->left==nullptr){
a->left = b;
}else{
a->right = imerge(a->right,b);
if(a->left->npl<a->right->npl){
LNode<T>* tm = a->left;
a->left = a->right;
a->right = tm;
}
a->npl = a->right->npl+1;
}
return a;
}
template <class T>
void LeftistHeap<T>::insert(T element){
LNode<T>* newLNode = new LNode<T>(element);
root = imerge(root,newLNode);
}
template <class T>
void LeftistHeap<T>::deleteMin(){
if(root==nullptr) return ;
LNode<T>* tem = root;
root = imerge(root->left,root->right);
delete tem;
tem = nullptr;
}
template<class T>
void LeftistHeap<T>::preprint(LNode<T>* LNode){
if(LNode==nullptr) return ;
std::cout<<LNode->data<<" ";
if(nullptr!=LNode->left) preprint(LNode->left);
if(nullptr!=LNode->right) preprint(LNode->right);
}
template<class T>
void LeftistHeap<T>::inprint(LNode<T>* LNode){
if(LNode==nullptr) return ;
if(nullptr!=LNode->left) inprint(LNode->left);
std::cout<<LNode->data<<" ";
if(nullptr!=LNode->right) inprint(LNode->right);
}
#endif //ADSPRO3_LEFTISTHEAP_H
斜堆（Skew Heap）与左式堆非常相似，唯一的不同是，其节点上并没有NPL属性。左式堆的merge操作总是在右子树上进行，当某节点出现左子树NPL小于右子树时，则交换左右子树。而斜堆不判断NPL属性，每一次合并都会无条件交换左右子树，通过这种方式来使其摊还时间复杂度达到O（logN）。代码如下。
//
// Created by chnmagnus on 16-3-30.
//
#ifndef ADSPRO3_SKEWHEAP_H
#define ADSPRO3_SKEWHEAP_H
#include <iostream>
//the declaration of node class
template <class T>
class SNode{
public:
T data; //the data
SNode * left; //pointer to left child
SNode * right; //pointer to right child
SNode() = default; //default constructor
//constructor
SNode(T element):data(element),left(nullptr),right(nullptr){}
};
//the declaration of skew heap class
template <class T>
class SkewHeap{
public:
SNode<T> * root; // the root
SkewHeap():root(nullptr){} //constructor
//merge function
void merge(SkewHeap another);
SNode<T> * imerge(SNode<T>* a,SNode<T>* b);
SNode<T> * iimerge(SNode<T>* a,SNode<T>* b);
void insert(T element);//insert element
void deleteMin();//delete the min element
void preprint(SNode<T>* SNode); //print heap in preorder
void inprint(SNode<T>* SNode); //print heap in inorder
};
//the drive function of imerge and iimerge
template <class T>
void SkewHeap<T>::merge(SkewHeap another){
this->root = imerge(this->root,another.root);
}
template <class T>
SNode<T>* SkewHeap<T>::imerge(SNode<T> *a ,SNode<T> *b){
if(a==nullptr) return b;
if(b==nullptr) return a;
if(a->data<b->data) return iimerge(a,b);
else return iimerge(b,a);
}
template <class T>
SNode<T>* SkewHeap<T>::iimerge(SNode<T> *a ,SNode<T> *b){
if(a->right==nullptr){
a->right = b;
}else{
a->right = imerge(a->right,b);
}
SNode<T>* tm = a->left;
a->left = a->right;
a->right = tm;
return a;
}
template <class T>
void SkewHeap<T>::insert(T element){
SNode<T>* newSNode = new SNode<T>(element);
root = imerge(root,newSNode);
}
template <class T>
void SkewHeap<T>::deleteMin(){
if(root==nullptr) return ;
SNode<T>* tem = root;
root = imerge(root->left,root->right);
delete tem;
tem = nullptr;
}
template<class T>
void SkewHeap<T>::preprint(SNode<T>* SNode){
if(SNode==nullptr) return ;
std::cout<<SNode->data<<" ";
if(nullptr!=SNode->left) preprint(SNode->left);
if(nullptr!=SNode->right) preprint(SNode->right);
}
template<class T>
void SkewHeap<T>::inprint(SNode<T>* SNode){
if(SNode==nullptr) return ;
if(nullptr!=SNode->left) inprint(SNode->left);
std::cout<<SNode->data<<" ";
if(nullptr!=SNode->right) inprint(SNode->right);
}
#endif //ADSPRO3_SKEWHEAP_H
另附普通堆的实现：
//
// Created by chnmagnus on 16-3-31.
//
#ifndef ADSPRO3_ORIGINHEAP_H
#define ADSPRO3_ORIGINHEAP_H
#include <iostream>
//the declaration of heap class
template <class T>
class OriginHeap{
public:
int capacity;//the total capacity
int size; //current element num
T* Elements; //elements
//the function declaration and the comment
OriginHeap(); //constructor
OriginHeap(int capacity); //constructor
~OriginHeap(); //destructor
void percolateup(int i); //percolate up
void percolatedown(int i); //percolate down
T finfMin(); //return the root data
bool isEmpty(); //is empty?
bool isFull(); //is full?
void insert(T element); //insert element
void deleteMin(); //delete the root data
void merge(OriginHeap & another); //merge two heap
};
template <class T>
void OriginHeap<T>::percolateup(int i){
T element = Elements[i];
for(;Elements[i/2]>element&&i>=1;i/=2){
Elements[i] = Elements[i/2];
}
Elements[i] = element;
}
template <class T>
void OriginHeap<T>::percolatedown(int i){
T x = Elements[i];
int child;
for(;i*2<=size;i = child){
child = i*2;
if(child!=size&&Elements[child+1]<Elements[child])
child++;
if(x>Elements[child]){
Elements[i] = Elements[child];
}else{
break;
}
}
Elements[i] = x;
}
template <class T>
OriginHeap<T>::OriginHeap(){ //Constructor
capacity = 100;
size = 0;
Elements = new T[capacity+1];
}
template <class T>
OriginHeap<T>::OriginHeap(int capacity){
this->capacity = capacity;
size = 0;
Elements = new T[capacity+1];
}
template <class T>
OriginHeap<T>::~OriginHeap(){ //Destructor
if(Elements){
delete []Elements;
}
Elements = nullptr;
}
template <class T>
void OriginHeap<T>::insert(T element){
if(isFull()){
std::cout<<"Heap is full"<<std::endl;
return ;
}
Elements[++size] = element;
percolateup(size);
}
template <class T>
void OriginHeap<T>::deleteMin(){
if(isEmpty()){
std::cout<<"heap is empty"<<std::endl;
return ;
}
Elements[1] = Elements[size--];
percolatedown(1);
}
template <class T>
T OriginHeap<T>::finfMin(){
return Elements[1];
}
template <class T>
void OriginHeap<T>::merge(OriginHeap & another){
if(this->capacity<another.size+this->size){
std::cout<<"cannot merge"<<std::endl;
return ;
}
for(int i=1;i<=another.size;++i){
Elements[++this->size] = another.Elements[i];
}
for(int i=size/2;i>=1;--i){
percolatedown(i);
}
}
template <class T>
bool OriginHeap<T>::isEmpty(){
return size==0;
}
template <class T>
bool OriginHeap<T>::isFull(){
return size==capacity;
}
#endif //ADSPRO3_ORIGINHEAP_H
以上是脚本宝典为你收集整理的[DS] 易于合并的堆：左式堆和斜堆C++实现全部内容，希望文章能够帮你解决[DS] 易于合并的堆：左式堆和斜堆C++实现所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。