相关问题：(利用链表实现可合并堆) 可合并堆支持以下操作：MAKE-HEAP(创建一个空的可合并堆)，INSERT，MAXIMUM，EXTRACT-MAX和UNION。说明在下列前提下如何用链表实现可合并堆。试着使各操作尽可能高效。分析每个操作按动态集合规模的运行时间。
由于对于堆操作需要查找父结点，以及左右孩子结点，所以本程序中用到了非递归非辅助栈的遍历与查找操作，它需要O(nlgn)时间，
a.链表已排序。
INSERT：尽管链表已排序。但是由于插入时，需要查找其父结点，所以运行时间也要O(nlgn)
MAXIMUM：因为已经排序，所以我们直接返回根结点即可找到最大值。
EXTRACT-MAX：删除时，涉及到了第一个结点（根结点）和最后一个结点（最小值结点），由于没有保存最后一个结点，所以又要进行查询操作，这样时间还是O(nlgn)时间，
UNION：用遍历树形链表的方法进行循环将第一颗树的结点插入到第二颗树中，那么总的运行时间为O((n^2)lgn).
b.链表未排序。
需要说明的就是MAXIMUM函数运行时间达到了O(n)，因为在查询最大值前，要进行建堆操作。其他操作都一样。
c.链表未排序，且待合并的动态集合是不想交的。
不相交，就是没有相同元素，省略了对相同数据进行可合并堆的各种操作。
以下代码展示了链表未排序时的可合并堆的各项操作。
#include <iostream>
using namespace std;
#define LEN sizeof(struct Tree)
int heap_size1=0, heap_size2=0;;
#define Print 0
#define search 1
struct Tree*head1=NULL;
struct Tree*head2=NULL;
struct Tree
{
int key;
int num;
struct Tree*lchild;
struct Tree*rchild;
struct Tree*parent;
};
void Make_heap(struct Tree*&p)
{
p=NULL;
}
int PARENT(int i)
{
return i/2;
}
int LEFT(int i)
{
return 2*i;
}
int RIGHT(int i)
{
return 2*i+1;
}
void create(struct Tree **p,int flag)
{
static struct Tree *head=NULL;
static struct Tree *p1=NULL;//p1保存当前结点的父亲结点
*p=new struct Tree [LEN];
cout<<"请输入结点的数据：";
cin>>(*p)->key;
(*p)->num=0;
(*p)->parent=p1;
p1=*p;
if ((*p)->key!=0)
{
cout<<"请输入非空结点的下标：";//下标我们自己定，注意按照堆的下标顺序设置，每层从左到右由小到大依次设置，但是在输入时和堆的下标设置次序可能不一样，
cin>>(*p)->num;
if (head==NULL||flag!=2)
{
if (flag==1)
{
head1=head=*p;
}
if (flag==0)
{
head2=head=*p;
}
(*p)->parent=NULL;
flag=2;
}
if (head==head1)
{
heap_size1++;
}
if (head==head2)
{
heap_size2++;
}
create((&(*p)->lchild),flag);
p1=*p;
create((&(*p)->rchild),flag);
}
}
struct Tree * InOderTraverse(struct Tree *p,int i,int flag)
{
if(!p->key) return NULL;
struct Tree *x=NULL;
while(1)//O(nlgn)
{
//访问左孩子
if(x != p->lchild)
{
while(p->lchild->key)//O(lgn)
{
p=p->lchild;
}
}
if (flag==1)
{
if (p->num==i)
{
return p;
}
}
if(flag==0)
{
cout<<"A["<<p->num<<"]="<<p->key<<" ";
}
//访问右孩子
if(p->rchild->key)
{
p=p->rchild;
continue;
}
//回溯
do//O(lgn)
{
x=p;
p=p->parent;
//访问到根节点的父节点（NULL)
if(!p) return NULL;
}while(x==p->rchild);
}
}
void HEAP_INCREASE_KEY(struct Tree*p,struct Tree*head,int i,int k)
{
i=PARENT(i);
struct Tree*p2=InOderTraverse(head, i,search);//O(nlgn)
if (k<p->key)
{
return ;
}
p->key=k;
if (head==head1)
{
p->num=heap_size1;
}
else p->num=heap_size2;
while (p2!=NULL&&p2->key<p->key) //O(n)
{
swap(p->key,p2->key);
p=p2;
p2=p2->parent;
}
}
void MAX_HEAP_INSERT(struct Tree*head,int k) //O(nlgn)
{
int j;
if (head==head1)
{
heap_size1++;
j=heap_size1;
}
else
{
heap_size2++;
j=heap_size2;
}
struct Tree*p=new struct Tree[LEN];
p->key=-0x7fffffff;
int i;
if (head==head1)
{
i=PARENT(heap_size1);
}
if (head==head2)
{
i=PARENT(heap_size2);
}
struct Tree*p1=InOderTraverse(head,i,search);//O(nlgn)
p->parent=p1;
if (head==head1)
{
if (LEFT(i)==heap_size1)
{
p1->lchild=p;
}
else
{
p1->rchild=p;
}
}
else
{
if (LEFT(i)==heap_size2)
{
p1->lchild=p;
}
else
{
p1->rchild=p;
}
}
p->lchild=new struct Tree[LEN];
p->lchild->key=0;
p->rchild=new struct Tree[LEN];
p->rchild->key=0;
HEAP_INCREASE_KEY(p,head,j,k); //O(nlgn)
}
void MAX_HEAPIFY(struct Tree*p,int i)
{
struct Tree*largest=NULL;
struct Tree*I=InOderTraverse(p, i,search);//找出下标为i的结点指针
if (I->lchild!=NULL&&I->lchild->key>I->key)
{
largest=I->lchild;
}
else largest=I;
if (I->rchild!=NULL&&I->rchild->key>largest->key)
{
largest=I->rchild;
}
if (largest!=I)
{
swap(I->key,largest->key);
MAX_HEAPIFY(p,largest->num);
}
}
void BUILD_MAX_HEAP(struct Tree*p)
{
int heap_size=0;
if (p==head1)
{
heap_size=heap_size1;
}
else
{
heap_size=heap_size2;
}
for (int i=heap_size/2+1;i>0;i--)
{
MAX_HEAPIFY(p,i);
}
}
int MAXIMUM(struct Tree*p)//前提是要先调用建堆函数BUILD_MAX_HEAP，建好堆才能求最大值。O(nlgn)
{
return p->key;
}
int HEAP_EXTRACT_MAX(struct Tree*p) //前提是要先调用建堆函数BUILD_MAX_HEAP，建好堆才能删除最大值
{ //O(nlgn)
int heap_size=0;
if (p==head1)
{
heap_size=heap_size1;
}
if (p==head2)
{
heap_size=heap_size2;
}
if (heap_size<1)
{
cout<<"heap underflow"<<endl;
exit(0);
}
struct Tree*p1,*p2,*p3;
p3=p1=InOderTraverse(p,1,search);
p2=InOderTraverse(p,heap_size,search);
p1->key=p2->key;
heap_size--;
if (p==head1)
{
heap_size1=heap_size;
}
if(p==head2)
{
heap_size2=heap_size;
}
MAX_HEAPIFY(p,1);
p2->key=0;
return p3->key;
}
struct Tree * UNION(struct Tree *p1,struct Tree *p2)//O((n^2)lgn)
{//将p2中的元素合并到p1中去。
if (p1->key==0)
{
return p2;
}
if (p2->key==0)
{
return p1;
}
struct Tree *x=NULL;
while(1)
{
//访问左孩子
if(x != p2->lchild)
{
while(p2->lchild->key)
{
p2=p2->lchild;
}
}
MAX_HEAP_INSERT(p1,p2->key);
//访问右孩子
if(p2->rchild->key)
{
p2=p2->rchild;
continue;
}
//回溯
do
{
x=p2;
p2=p2->parent;
//访问到根节点的父节点（NULL)
if(!p2) return NULL;
}while(x==p2->rchild);
}
}
void main()
{
struct Tree*p1,*p2;
Make_heap(p1);
Make_heap(p2);
cout<<"请输入第一棵树数据："<<endl;
create(&p1,1);
cout<<"请输入第二棵树数据："<<endl;
create(&p2,0);
cout<<"创建树型链表1后：";
InOderTraverse(p1,0,Print);
cout<<endl;
cout<<"创建树型链表2后：";
InOderTraverse(p2,0,Print);
cout<<endl;
MAX_HEAP_INSERT(p1,22);
MAX_HEAP_INSERT(p1,102);
cout<<"插入数据后,第一棵树数据：";
InOderTraverse(p1,0,Print);
cout<<endl;
MAX_HEAP_INSERT(p2,18);
cout<<"插入数据后,第二棵树数据：";
InOderTraverse(p2,0,Print);
cout<<endl;
BUILD_MAX_HEAP(p1);
cout<<"建堆后：第一棵树数据：";
InOderTraverse(p1,0,Print);
cout<<endl;
BUILD_MAX_HEAP(p2);
cout<<"建堆后：第二棵树数据：";
InOderTraverse(p2,0,Print);
cout<<endl;
cout<<"MAX1="<<MAXIMUM(p1)<<endl;
cout<<"删除最大值后：第一棵树"<<endl;
HEAP_EXTRACT_MAX(p1);
InOderTraverse(p1,0,Print);
cout<<endl;
cout<<"MAX2="<<MAXIMUM(p2)<<endl;
cout<<"删除最大值后：第二棵树"<<endl;
HEAP_EXTRACT_MAX(p2);
InOderTraverse(p2,0,Print);
cout<<endl;
UNION(p1,p2);//p2元素依次插入到p1中，所以p1得头结点时合并后的总的头结点
cout<<"合并后的二叉树："<<endl;
InOderTraverse(p1,0,Print);
cout<<endl;
}原文：http://blog.csdn.net/z84616995z/article/details/21174463