一、定义

双端堆：是一棵完全二叉树，该完全二叉树要么为空，要么同时满足下列性质：

（1） 根节点不包含元素；

（2） 左子树是一个最小堆；

（3） 右子树是一个最大堆；

（4） 如果右子树不空，令i是左子树中任意一节点，j是i在右子树中的对应节点，则节点i的关键字小于等于j的关键字。

 

对应节点：j是右子树中与i处于相同位置的节点（如果令左右子树编号都从1开始，则j就是右子树中与i编号相同的节点）。如果j不存在，则i的父节点的对应节点就是i的节点。

 

双端堆的性质：

1）假设x1为最小堆中的任意一节点，x2为其父节点；x1和x2的对应节点分别为y1，y2，则有x2≤x1≤y1≤y2.

2）我们在最小堆中任意找一条路线，上面的节点分别为x1,x2,…xn，在最大堆中找到这n个节点的对应节点，可能有n个，也可能是n-1个，这些对应节点同样在最大堆的一条路径上。将这两条路径连接起来，可以发现，上面的节点值从x1开始是逐渐增加的。

 

说明：这里的“完全二叉树”是指树的节点按从上到下，从左到右依次排列，不会出现跳跃排列的现象。比如，先有右儿子，后有左儿子，或者先排右子树，后排左子树等，都是不允许的。

 

二、双端堆的插入

同样，我们不详细介绍边界情况，只介绍一般情况。

根据双端堆的性质，每一层都必然是从左到右逐个插入的。因此，先插最小堆，后插最大堆。

（1）假如我们插入的新元素是在最小堆，则不仅需要考虑最小堆的性质（父节点大于子节点），还需要考虑双端堆的性质（4）。

根据这两条性质的满足顺序，我们因此有两种策略：

策略一：先满足双端堆性质，再满足最小堆性质；

策略二：先满足最小堆性质，再满足双端堆性质。

下面我们分别实现这两种策略：

策略一

将新插入节点与其在最大堆中对应节点相比较，如果大于对应节点，则将两个节点元素互换，对最大堆执行max_insert操作；否则，只需对最小堆执行min_insert操作。

说明：

1）如果大于对应节点，则将两个节点元素互换，对最大堆执行max_insert操作。

这一步不需要再对最小堆执行min_insert操作。假设新节点是new，父节点是parent，对应节点是cert，则cert也是parent的对应节点，所以cert节点大于parent。new和cert交换之后，cert代替new成了parent的子节点，且大于parent，符合最小堆性质，因此不需要对最小堆进行任何操作。

2）否则，只需对最小堆执行min_insert操作

此时新节点小于对应节点，如果大于父节点，则min_insert不进行任何操作。新插入的节点小于对应节点，满足双端堆性质（4）；大于父节点，满足最小堆性质，因此，新节点不需进行任何操作即可满足这两条性质，而其他节点本来就满足，因此所有节点满足。

如果小于父节点，则执行min_insert操作后，新节点是原先的父节点，其它节点的值都小于等于原来的值，包括新的父节点。由于新节点以外的节点原先就满足双端堆性质（4），即小于对应节点值，执行完后，这个性质仍然满足。我们再看新节点，新节点元素是原先的父节点，而原先的父节点是小于其对应节点的，此时由于最大堆中与新节点对应的节点不存在，所以新节点的对应节点就是其父节点的对应节点，因此，新节点小于其对应节点，满足性质（4）。所以，所有节点满足性质（4）。同时，执行min_insert操作后，所有节点满足最小堆性质，因此所有节点满足双端堆性质。

策略二

将新插入节点与其父节点比较，如果小于父节点，则对最小堆执行min_insert操作即可；否则，将其与最大堆中对应节点比较，如果大于对应节点，则交换新节点和对应节点，对对应节点执行max_insert操作，否则，不进行任何操作。

说明：

1）如果小于父节点，则对最小堆执行min_insert操作即可；

根据策略一的说明，执行min_insert操作后，新节点是原先的父节点，其它节点都小于等于原先节点值。新节点对应节点和父节点对应节点相同，因此新节点值小于其对应节点值。而其它节点都小于等于原先节点值，自然也就小于等于其对应节点值，所以，执行完后，所有节点满足双端堆性质（4）。而经过 min_insert操作后，所有点满足最小堆性质，因此，所有点满足双端堆性质。

2）否则，将其与最大堆中对应节点比较，如果大于对应节点，则交换新节点和对应节点，对对应节点执行max_insert操作，否则，不进行任何操作。

此时新节点大于父节点。

假设新节点为new，对应节点为cert，新节点的父节点为parent1，对应节点的父节点为parent2。则

parent2>cert

new>parent1

cert>parent1(cert也是parent1的对应节点)

如果new>cert，交换new和cert，则有

parent2>new

cert>parent1

new>parent1

cert >new

首先，由于new>parent1，所以最小堆性质保持。而cert >new，cert>parent1,即满足双端堆性质，但我们还不知道是否有parent2>cert，因此，需要对最大堆执行max_insert操作，满足最大堆性质。执行完后，最小堆不变，不用考虑，那么，是否还满足双端堆性质（4）呢？

我们知道，执行外max_insert操作后，cert有可能与parent2交换，而其他节点要么不变，要么就变得比原来更大。

由前面知道：parent2>new，new>parent1，因此parent2>parent1，所以即使cert与parent2交换，仍满足cert >new，cert>parent1,即执行后cert仍满足双端堆性质。

而其它节点本身就比最小堆中相应节点大，执行完后，要么不变，要么变得更大，因此也满足双端堆性质。

综上所述，“如果大于对应节点，则交换新节点和对应节点，对对应节点执行max_insert操作”，是正确的。

如果new<=cert，不进行任何操作

首先，由于new>parent1，所以最小堆性质保持。此时new<=cert，则new满足双端堆性质（4）。而最小堆中所有节点其它节点本就满足双端堆性质（4），因此，所有节点满足双端堆性质（4）。

因此，不需进行任何操作，即可满足双端堆性质。

（2）假如我们插入的是最大堆，则需要考虑最大堆性质及双端堆的性质（4）。

同样，我们有两种策略：

策略一：先满足双端堆性质，再满足最大堆性质；

策略二：先满足最大堆性质，再满足双端堆性质。

下面我们分别实现这两种策略：

策略一

将新插入节点与其在最小堆中对应节点相比较，如果小于对应节点，则将两个节点元素互换，对最小堆执行min_insert操作；否则，只需对最大堆执行max_insert操作。

说明：见最小堆中说明

 

策略二

将新插入节点与其父节点比较，如果大于父节点，则对最大堆执行max_insert操作即可；否则，将其与最小堆中对应节点比较，如果小于对应节点，则交换新节点和对应节点，对对应节点执行min_insert操作，否则，不进行任何操作。

说明：见最小堆中说明

 

三、双端堆的删除

1、删除最小元素

最小元素是最小堆的根节点。

与其它算法意一样，我们的基本思想是要通过最小的变动，使得剩余节点保持双端堆的性质。

策略一

现在，最小堆根节点为空，需要从剩余节点中找一个节点放入其中。我们知道，最小堆的根节点堆中最小元素，所以该节点应该是剩余节点中最小的元素。假设根节点为第0层，则这个最小元素必然是在最小堆的第1层中。将第一层中最小节点移至根节点。现在这个节点又空了，而这个节点又是一起为根的最小堆中的最小节点，所以，这个节点应该从其儿子节点中选择最小的节点进行填充。依次类推，直到找到的空节点已经没有儿子节点，即，是叶节点，我们将这条路径成为L，L上的所有节点均移至其父节点位置，最后一个叶子节点为空，假设其为S。

首先，除了S外，最小堆其余节点仍然都满足最小堆性质。

其次，除了L上的节点，其它节点没有改变，而最大堆也没变，所以这些节点的双端堆性质也仍然保持。

最后，我们看看L上的节点。我们知道L上的节点都是由原位置移至其父节点，所以对应点也应变为原对应点的父节点。根据双端堆性质，最小堆中节点不仅小于对应节点，还小于对应节点的父节点，也就是说，L上的节点仍然满足双端堆性质。

综上所述，最小堆上除S以外的所有节点都满足最小堆性质和双端堆性质。

如果S是原双端堆中的最后一个节点，则不需再进行任何操作。否则，需要找到一个点来对其填充。

我们知道，此时双端堆节点个数少了一个，所以最后一个节点需要删除，存放在那里的元素将无处存放。我们就先将这个元素放在S上。

根据前面双端堆在最小堆插入的说明，如果S小于其父节点，则只需对最小堆进行min_insert操作即可。

如果大于父节点小于对应节点，则不需进行任何操作；

如果大于对应节点，则将S与对应节点互换，并对最大堆进行max_insert操作。

策略二：

策略二是对策略一的改进。在策略一中，先对最小堆进行处理，然后加入S，如果此时S小于父节点，则需要再对最小堆进行处理。

这里我们先将S放在最小堆空着的根节点处，然后对最小堆进行调整，即执行min_insert2操作。如果S的最终位置在叶子节点，则就与策略一相同，即比较S与对应节点的大小，根据比较结果做出处理。但如果S节点最终位置不在叶节点，则可直接结束程序。

 

2、删除最大元素

最大元素是最大堆的根节点。同样有两种策略：

策略一

对最大堆进行处理，直到某个叶节点S为空，将最后一个节点元素X放在S处。如果S大于父节点，则对最大堆进行max_insert操作，否则，找到S在最小堆中对应节点（叶节点），将S与对应节点互换，对最小堆进行min_insert操作。

策略二

将最后一个节点的元素x放到最大堆根节点处，对最大堆进行处理，类似于冒泡法，如果X最后不是在叶节点上，则程序结束。

如果X在叶节点上，则找到X在最小堆中对应节点S（叶节点）。如果S小于X，则程序结束；如果S大于X，则交换S和X，对最小堆进行min_insert操作。

 

四、C语言实现

#include <stdio.h>

#include <stdlib.h>

 

#define MAX_SIZE 100 

#define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))

 

typedef struct{

       int key;

      

}element;

element deap[MAX_SIZE];

 

void show(element heap[],int n);

void deap_insert(element deap[], int *n, element x);

void max_insert(element deap[],int num1, int num2);

void min_insert(element deap[],int num1, int num2);

element deap_delete_min(element deap[],int *n);

element deap_delete_max(element deap[],int *n);

int type(int i);

void modified_deap_insert(element deap[], int size, int pos);

int min_insert2(element deap[],int num1, int num2);

element deap_delete_min2(element deap[],int *n);

 

int main(void)

{

       int n=1;

       int i,j;

       element arr[23]={ {7},{3},{70},{20},{40},{80},{30},{5},{9},{17},{10},{100},

{15},{3},{45},{0},{50},{2},{30},{88},{20},{99},{12}};

    for(i=0;i<23;i++)

        deap_insert(deap,&n, arr[i]);  //将节点依次插入，构造双端堆

       show(deap,n);

      

       element temp;

       for(i=0;i<23;i++)

       {

              temp=deap_delete_min2(deap,&n);

              printf("the deleted element is %d\n",temp.key);

       }

      

  system("PAUSE");

       return 0;

} 

 

 

void show(element heap[],int n)

{

       int j;

       if(n==1)

           return;

       printf("n=%d\n",n);

       printf("The deap is:\n");

    for(j=2;j<=n;j++)  //双端堆第一个元素存在数组下标为2的地方

           printf("%d ",heap[j].key);

       printf("\n");

}

 

 

 

void deap_insert(element deap[], int *n, element x)

{

       (*n)++;

       if(*n==2)

       {

              deap[2]=x;

              return;

       }

 

       if(*n==MAX_SIZE)  //堆已满

       {

              fprintf(stderr,"The deap is full.\n");

              exit(1);

       }

     

       deap[*n]=x;

       int i,k;

       element temp;

       if(type(*n))  // type (*n)=1,表示新节点在最小堆上

       {

        //新节点在最小堆，说明其最大堆中与其同一位置的节点为空，所以其对应节//点是其父节点的对应节点。

              i=(*n)/2;

              if(deap[i].key>deap[(*n)].key)

                  min_insert(deap,(*n),2);

        //新节点小于父节点，只需对最小堆进行min_insert即可

              else

              {           

                  k=log2(i);  //i所在层数 ，根节点为第0层

                  i=(i+pow(2,k-1));//i在右堆上的对应节点

                  if(deap[i].key<deap[*n].key)

            //如果新节点大于对应节点，则交换两节点并对最大堆进行max_insert

                  {

                   SWAP(deap[i],deap[*n],temp);

                   max_insert(deap,i,3);

}

              }

       }

       else   //在最大堆上

    {           

              i=(*n)/2; //i是新节点的父节点

              if(i>=3 && deap[i].key<deap[(*n)].key)

       //如果父节点存在且小于新节点，则只需对最大堆执行max_insert

                  max_insert(deap,(*n),3);

              else

       //如果i<3或deap[i].key>deap[(*n)].key，则需与最小堆中处于叶节点的对应节

//点进行比较

              {               

                  k=log2(*n);  //所在层数 ，根节点为第0层

                  i=(*n)-pow(2,k-1);  //最堆上的对应叶节点

               if(deap[i].key>deap[*n].key)

            //若对应节点大于新节点，则交换两节点，并对最小堆执行min_insert

               {

                   SWAP(deap[i],deap[*n],temp);

                   min_insert(deap,i,2);

                  }

           }

       }

}

 

 

 

 

 

void modified_deap_insert(element deap[], int size, int pos)

{

       if(pos>size)

       {

              fprintf(stderr,"The position exceeds the scale of the deap.\n");

              exit(1);

       }

 

       int i,j,k;

       element temp;

       if(type(pos))   // pos在最小堆上，

       {

              k=log2(pos); //所在层数

              i=pos+pow(2,k-1); //在右堆的对应节点

              if(i>size)    //相同位置处无节点，对应节点就应该是其父节点

                  i=i/2;   //i为pos在最大堆中对应的节点

              if(i>=3 && deap[i].key<deap[pos].key)

              {

               SWAP(deap[i],deap[pos],temp);

               max_insert(deap,i,3);

              }

           else

                  min_insert(deap,pos,2);

       }

       else   //等于0,表示在最大堆上

    {           

              k=log2(pos);

              i=(pos)-pow(2,k-1);

              if(2*i<=size)

        //最小堆对应节点有子节点，则应与子节点比较，

              {

                     j=2*i;

                     if(2*i+1<=size && deap[2*i].key<deap[2*i+1].key)

                         j=2*i+1;

            // pos应比两个子节点都大，所以j指向子节点中最大的节点

              }

              else //i没有子节点，则对应节点就是i

                  j=i;

                 

              if(deap[pos].key<deap[j].key)

        {

                     SWAP(deap[j],deap[pos],temp);

                     min_insert(deap,j,2);

              }

              else

                     max_insert(deap,pos,3);

       }

}

 

 

 

 

 

 

 

 

void max_insert(element deap[],int num1, int num2)

{

    int parent;

    element temp;

   

    if(num1==num2)

        return;

    for(parent=num1/2;parent>=num2;)

    {

              if(deap[parent].key<deap[num1].key)

{

                  SWAP(deap[parent],deap[num1],temp);

                  num1=parent;

                  parent=num1/2;

         }

         else

            break;

       }

}

 

 

 

 

 

 

 

void min_insert(element deap[],int num1, int num2)

{

    int parent;

    element temp;

   

    if(num1==num2)

        return;

 

    for(parent=num1/2;parent>=num2;)

    {

              if(deap[parent].key>deap[num1].key)

              {

                  SWAP(deap[parent],deap[num1],temp);

                  num1=parent;

                  parent=num1/2;

           }

           else

               break;

       }

}

 

 

 

 

 

 

 

 

int min_insert2(element deap[],int num1, int num2)

{

    int i=num1,j;

    element temp;

  

    for(;2*i<=num2;)

    {

              j=2*i;

              if(2*i+1<=num2 && deap[2*i+1].key<deap[2*i].key)

                  j++;

              if(deap[j].key<deap[i].key)

              {

                     SWAP(deap[i],deap[j],temp);

                     i=j;

              }

              else

                  break; //跳出for循环

       }    

      

       return i;

}

 

int max_insert2(element deap[],int num1, int num2)

{

    int i=num1,j;

    element temp;

  

    for(;2*i<=num2;)

    {

              j=2*i;

              if(2*i+1<=num2 && deap[2*i+1].key>deap[2*i].key)

                  j++;

              if(deap[j].key>deap[i].key)

              {

                     SWAP(deap[i],deap[j],temp);

                     i=j;

              }

              else

                  break; //跳出for循环

       }    

      

       return i;

}

 

 

element deap_delete_min(element deap[],int *n)

{

       (*n)--;

       if((*n)==0)

       {

              fprintf(stderr,"The deap is empty.\n");

              exit(1);

       }

       deap[0]=deap[2];

      

       int i,j;

       for(i=2;i*2<=*n;) //

       {

              j=2*i;

              if(j+1<=*n)

                  if(deap[j].key>deap[j+1].key)

                      j=j+1; //deap[j+1]应该上移

              deap[i]=deap[j];

              i=j;

       }

   //上述for循环是先对最小堆进行处理，空出一个叶节点

 

       deap[i]=deap[*n+1];

//将原堆中最后一个节点放到空的叶节点处

       modified_deap_insert(deap,*n,i);

//将新的堆调整为双端堆

       return     deap[0];

}

 

 

element deap_delete_min2(element deap[],int *n)

 

{

       if((*n)==1)

       {

              fprintf(stderr,"The deap is empty.\n");

              exit(1);

       }

       deap[0]=deap[2];

      

       deap[2]=deap[(*n)--];

//先将原堆最后一个元素放到最小堆的根节点处

       if((*n)<=2)

           return deap[0];

          

       int i,j;

       i=min_insert2(deap,2,*n);

       //对最小堆进行调整，同时返回i记录最后一个元素的最终位置

       if(2*i<=*n)

           return deap[0];

       //如果最终位置不是叶节点，整个程序结束

 

   //如果是叶节点，那么接下来就需要找出其在最大堆的对应节点

       int k=log2(i);

       j=i+pow(2,k-1); //在右堆的对应节点

              if(j>*n)

                  j=j/2;   //j为i在最大堆中对应的节点

      

       if(deap[j].key>=deap[i].key)

           return deap[0];

    //如果对应节点大于该叶节点，则程序结束

  

       element temp;

       SWAP(deap[i],deap[j],temp);

       //对应节点小于该叶节点，交换两节点，并对最大堆执行max_insert

 

       max_insert(deap,j,3);

       return     deap[0];

}

 

 

 

 

element deap_delete_max(element deap[],int *n)

 

{

       (*n)--;

       if((*n)==0)

       {

              fprintf(stderr,"The deap is empty.\n");

              exit(1);

       }

       if((*n)==1)

       {

              deap[0]=deap[2];

              return deap[0];

       }

       if((*n)==2)

       {

              deap[0]=deap[3];

              return deap[0];

       }

      

    deap[0]=deap[3]; //((*n)>=2)

   

    int i,j;

       for(i=3;i*2<=*n;) //

       {

              j=2*i;

              if(j+1<=*n)

                  if(deap[j].key<deap[j+1].key)

                      j=j+1; //deap[j+1]应该上移

              deap[i]=deap[j];

              i=j;

       }

 

       deap[i]=deap[*n+1];

       modified_deap_insert(deap,*n,i);

       return     deap[0];

}

 

int type(int i)

//type(*n)==1,表示节点i在最小堆上，0表示在最大堆上

{

       int layer=log2(i);

 

       if(i<=(pow(2,layer-1)*3-1))

           return 1;

       return 0;

}

 

说明：删除最大元素的策略二，本程序并未实现，但参考deap_delete_min2并不难实现。

程序运行结果：

0 100 2 3 80 99 5 3 15 9 45 50 70 88 12 10 40 7 20 30 17 20 30

the deleted element is 0

the deleted element is 2

the deleted element is 3

the deleted element is 3

the deleted element is 5

the deleted element is 7

the deleted element is 9

the deleted element is 10

the deleted element is 12

the deleted element is 15

the deleted element is 17

the deleted element is 20

the deleted element is 20

the deleted element is 30

the deleted element is 30

the deleted element is 40

the deleted element is 45

the deleted element is 50

the deleted element is 70

the deleted element is 80

the deleted element is 88

the deleted element is 99

the deleted element is 100