本文目录一览：
【数据结构】堆（优先队列）：二叉堆、d堆、左式堆、斜堆与二项队列
这是数据结构类重新复习笔记的第 五 篇，同专题的其他文章可以移步：
堆 （Heap）又称为 优先队列 （priority queue），在队列的基础上，堆允许所有队列中的元素不一定按照 先进先出 （FIFO）的规则进行，而是使得每个元素有一定的优先级，优先级高的先出队列。
优先队列至少存在两个重要的操作：
有几种简单而明显的方法实现优先队列。
二叉堆 （binary heap）是一种对于优先队列的实现，可以简称为堆
堆是一棵 完全二叉树 （complete binary tree），即所有节点都必须有左右两个子节点，除了最后一排元素从左向右填入，直到没有元素为止。
很显然，一棵高为h的完全二叉树有 2^h 到 2^(h+1)-1 个节点，即其高度为 logN 向下取整。
完全二叉树的好处在于其规律性，可以使用一个数组而不需要链表来表示
对于数组中任一位置 i 上的元素，其左儿子在位置 2i 上，右儿子在左儿子后的单元 (2i+1) 上，它的父亲则在位置 i/2 向下取整上。
因此，不仅不需要链，而且遍历该树所需要的操作也极简单，在大部分计算机上都可能运行得非常快。唯一问题是最大的堆的大小需要事先估计。
使操作可以快速执行的性质是 堆序性质 （heap-order property）：对于每一个节点X，X的父节点中的键小于等于X中的键，除没有父节点根节点外。
将待插入的元素首先放置在最后一个位置上，以保证他是一个完全二叉树，然后将该元素与其父节点（i/2向下取整）比较，如果比其父节点小，就将两者互换，互换后再和新的父节点比较，这种方式称为 上滤 （percolate up），得到一个小顶堆（min heap），如果比较的时候是较大的值向上走，就会得到一个大顶堆（max heap）
比如向一个小顶堆中插入元素14的操作：
找出、返回并删除最小元非常简单，最小元就是根节点处的元素，将其返回并删除。接下来是处理这个B。首先拿下最后一个元素X，如果元素X比B的两个子节点都小，可以直接将X插入到B的位置，如果X比B的两个子节点中的任意一个大，就不能插入，此时找到两个子节点中较小的那个放到B处，B转而移至这个子结点处。重复如上的步骤直到X可以插入B处为止。这个操作成为 下滤 （percolate down）
比如从一个小顶堆中删除根节点
decreaseKey(p, A) 操作减小在位置p处的元素的值，减少量为A，可以理解为调高了某个元素的优先级。操作破坏了堆的性质，从而需要上滤操作进行堆的调整。
increaseKey(p, A) 操作增加在位置p处的元素的值，增加量为A，可以理解为降低了某个元素的优先级。操作破坏了堆的性质，从而需要下滤操作进行堆的调整。
remove(p) 操作删除在堆中位置p处的节点，这种操作可以通过连续执行 decreaseKey(p, ∞) 和 deleteMin() 完成，可以理解马上删除某个一般优先级的元素
即将一个原始集合构建成二叉堆，这个构造过程即进行N次连续的 insert 操作完成
定理 ：包含 2^(h+1)-1 个节点且高度为h的理想二叉树（perfect binary tree）的节点的高度和为 2^(h+1)-1-(h+1)
d堆 （d-Heaps）是二叉堆的简单推广，它与二叉堆很像，但是每个节点都有d个子节点，所以二叉堆是d为2的d堆。d堆是完全d叉树。比如下边的一个3堆。
d堆比二叉堆浅很多，其insert的运行时间改进到 O(logdN) 。但是deleteMin操作比较费时，因为要在d个子节点中找到最小的一个，需要进行d-1次比较。d堆无法进行find操作，而且将两个堆合二为一是很困难的事情，这个附加操作为merge合并。
注意！ 在寻找节点的父节点、子节点的时候，乘法和除法都有因子d。如果d是一个2的幂，则可以通过使用二进制的 移位 操作计算，这在计算机中是非常省时间的。但是如果d不是一个2的幂，则使用一般的乘除法计算，时间开销会急剧增加。有证据显示，实践中，堆可以胜过二叉堆
这些高级的数据结构很难使用一个数据结构来实现，所以一般都要用到链式数据结构，这种结构可能会使得其操作变慢。
零路径长 （null path length）npl(X)：定义为从一个X节点到其不具有两个子节点的子节点的最短路径长，即具有0个或者1个子节点的节点npl=0，npl(null)=-1，任意节点的零路径长都比其各个子节点中零路径长最小值多1。
左式堆 （leftist heap）是指对于任意一个节点X，其左子节点的零路径长都大于等于其右子节点的零路径长。很显然，左式堆趋向于加深左路径。比如下边的两个堆，只有左边的是左式堆，堆的节点标示的是该节点的零路径长。
左式堆的实现中，需要有四个值：数据、左指针、右指针和零路径长。
定理 ：在右路径上有r个节点的左式堆必然至少有 2^r-1 个节点
merge 是左式堆的基本操作， insert 插入可以看成是一个单节点的堆与一个大堆的 merge ， deleteMin 删除最小值操作可以看成是首先返回、删除根节点，然后将根节点的左右子树进行 merge 。所以 merge 是左式堆的基本操作。
假设现在有两个非空的左式堆H1和H2，merge操作递归地进行如下的步骤：
例如如下的两个堆：
将H2与H1的右子树（8--17--26）进行merge操作，此时（8--17--26）和H2的merge操作中又需要（8--17--26）和H2的右子堆（7--37--18）进行merge操作……如此递归得到如下的堆：
然后根据递归的最外层（回到H1和H2的merge的第二步），将上边合并的堆成为H1的右子堆
此时根节点（3）处出现了左右子堆不符合左式堆的情况，互换左右子堆并更新零路径长的值
斜堆 （skew heap）是左式堆的自调节形式，实现起来极其简单。斜堆和左式堆的关系类似于伸展树和AVL树之间的关系。斜堆是具有堆序的二叉树，但是不存在对树的结构的现限制。不同于左式堆，关于任意结点的零路径长的任何信息都不保留。斜堆的右路径在任何时刻都可以任意长，因此，所有操作的最坏情形运行时间均为O(N)。然而，正如伸展树一样，可以证明对任意M次连续操作，总的最坏情形运行时间是 O(MlogN)。因此，斜堆每次操作的 摊还开销 （amortized cost）为O(logN)
斜堆的基本操作也是merge合并，和左式堆的合并相同，但是不需要对不满足左右子堆的左式堆条件的节点进行左右子堆的交换。斜堆的交换是无条件的，除右路径上所有节点的最大者不交换它的左右儿子外，都要进行这种交换。
比如将上述的H1和H2进行merge合并操作
首先进行第一步，除了交换左右子树的操作与左式堆不同，其他的操作都相同
将合并的堆作为H1的右子堆并交换左右子堆，得到合并后的斜堆
二项队列 （binomial queue）支持merge、insert和deleteMin三种操作，并且每次操作的最坏情形运行时间为O(logN)，插入操作平均花费常数时间。
二项队列不是一棵堆序的树，而是堆序的树的集合，成为 森林 （forest）。堆序树中的每一棵都是有约束的 二项树 （binomial tree）。二项树是每一个高度上至多存在一棵二项树。高度为0的二项树是一棵单节点树，高度为k的二项树Bk通过将一棵二项树Bk-1附接到另一棵二项树Bk-1的根上而构成的。如下图的二项树B0、B1、B2、B3和B4。
可以看到二项树Bk由一个带有儿子B0，B1，……，Bk-1的根组成。高度为k的二项树恰好有2^k个节点，而在深度d处的节点数为二项系数Cdk。
我们可以使用二项树的集合唯一地表示任意大小的优先队列。以大小为13的队列为例，13的二进制表示为1101，从而我们可以使用二项树森林B3、B2、B0表示，即二进制表示的数中，第k位为1表示Bk树出现，第k位为0表示Bk树不出现。比如上述的堆H1和堆H2可以表示为如下的两个二项队列：
二项队列额merge合并操作非常简单，以上边的二项队列H1、H2为例。需要将其合并成一个大小为13的队列，即B3、B2、B0。
首先H2中有一个B0，H1中没有，所以H2中的B0可以直接作为新的队列的B0的树
其次H1和H2中两个B1的树可以合并成一个新的B2的树，只需要将其中根节点较小的堆挂到根节点较大的堆的根节点上。这样就得到了三棵B2堆，将其中根节点最大的堆直接放到新队列中成为它的B2堆。
最后将两个B2堆合并成一个新队列中的B3堆。
二项队列的deleteMin很简单，只需要比较队列中所有二项堆的根节点，返回和删除最小的值即可，时间复杂度为O(logN)，然后进行一次merge操作，也可以使用一个单独的空间每次记录最小值，这样就可以以O(1)的时间返回。
森林中树的实现采用“左子右兄弟”的表示方法，然后二项队列可以使用一个数组来记录森林中每个树的根节点。
例如上边的合成的二项队列可以表示成如下的样子：
STL中，二叉堆是通过 priority_queue 模板类实现的，在头文件 queue 中，STL实现一个大顶堆而不是小顶堆，其关键的成员函数如下：
c语言实现队列和栈的方法
#define OVERFLOW -1
#define OK 1
#define ERROR 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define N 20
typedef char SElemType;
typedef int Status;typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;#includestdio.h
#includestdlib.hStatus CreatStack(SqStack S){
//创建栈
S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}//CreatStackStatus Push(SqStack S,SElemType e){
//插入e为新的栈顶元素
if(S.top-S.base=S.stacksize){//栈满，追加存储空间
S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base)exit (OVERFLOW);//存储空间分配失败
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}//PushStatus Pop(SqStack S ,SElemType e){
//若栈不空，删除栈顶元素，并用e返回其值
if(S.top==S.base) return ERROR;
e=*--S.top;
return OK;
}//Pop typedef char QElemType;
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QNodePtr;typedef struct{
QNodePtr front;
QNodePtr rear;
}LinkQueue;Status CreatQueue(LinkQueue Q){
//建立一个空的链式栈
Q.front=Q.rear=(QNodePtr)malloc(sizeof(QNode));
if(!Q.front)exit(OVERFLOW);
Q.front-next=NULL;
return OK;
}Status EnQueue(LinkQueue Q,QElemType e){ QNodePtr p;
p=(QNodePtr)malloc(sizeof(QNode));
if(!p)exit(OVERFLOW);
p-data=e;p-next=NULL;
Q.rear-next=p;
Q.rear=p;
return OK;
}Status DeQueue(LinkQueue Q,QElemType e){QNodePtr p;brif(Q.front==Q.rear) return ERROR;brp=Q.front-next; e=p-data;brQ.front-next=p-next;brif(Q.rear==p) Q.rear=Q.front;brfree(p);brreturn OK;br}int stackPalindrom_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0
{
printf("栈练习，请输入要判断的字符串以#作为结束符，不要超过二十个字符\n");
SqStack S;
CreatStack(S);
char c;
SElemType a;
SElemType b[N];
int count = 0;
fgets( b, N, stdin );
while((b[count])!='#')
{
Push(S,b[count]); //进栈
count++;
}
int i = 0;
while(i count)
{
Pop(S,a);
if(a!=b[i])
return ERROR;
i++;
}
return OK;}//stackPalindrom_Test int queuePalindrom_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0
{
printf("队列练习，请输入要判断的字符串以#作为结束符，不要超过二十个字符\n");
LinkQueue Q;
CreatQueue(Q); char c;
SElemType a;
SElemType b[N];
int count = 0;
fgets( b, N, stdin );
while((b[count])!='#')
{
EnQueue(Q,b[count]);; //入列
count++;
} while(count-- 0)
{
DeQueue(Q,a);
if(a!=b[count])
return ERROR;
}
return OK;
}//queuePalindrom_Test Status main(){ if(stackPalindrom_Test()==1)
printf("是回文\n");
else printf("不是回文\n"); if(queuePalindrom_Test()==1)
printf("是回文\n");
else printf("不是回文\n");
return OK;
}
C语言中怎么实现双端队列这个数据结构
双端队列数据类型
typedef
struct
qnode
{
DataType
data;
struct
qnode
*next;
}LQNode;
typedef
struct
{
LQNode
*front;
LQNode
*rear;
}LQueue;
尾出队：首先判断队列是否为空，如为空则提示队列为空，如不为空则将队尾结点
赋给临时结点。将队尾结点的前驱指针赋给队列的队尾指针，再将队尾结
点的后继指针置空。最后返回临时结点或所需要的数据。
C语言的队列如何实现和表示
我能想到的有两种方法（假设队列元素都是int）
一，用链表的方法
struct A
{
int n;
struct A *a;
} *p,*head,*rear;
head=rear=NULL；/*头指针，尾指针*/
添加元素：p=(struct A*)malloc(sizeof(struct A));......给新元素赋值.....;rear-a=p;rear=p;
当然添加第一个元素的时候要给head赋值。
删除元素：p=head;head=head-a;free(p);
用的是单向链表，当然也可以用双向链表，不过删除，添加元素的过程要麻烦点。
二，利用数组，当然也可以开辟动态储存空间
int a[N]，*head,*rear; N就是个常数
head=rear=a;
添加元素：scanf("%d",rear-a==N?rear=a:++rear);
删除元素：head-a==N?head=a:head++;
当然要检查队列是否溢出，可以设变量n=0;
每次添加元素n++
每次删除元素n--
当n0后nN数据溢出
