双堆DEAP

记录一道遇到的考研真题

特性分析：

DEAP为一颗完全二叉树，左子树小堆，右子树大堆，故左右子树分别可以用l[]、r[]数组存储，用m和n分别表示当前两完全二叉树的结点，左右子树高度差为1，且左子树的高度始终大于等于右子树的高度。

插入情况：

当均为空二叉树或者满二叉树（m=2^k-1）应该插入到小堆；小堆满后，插入到大堆。即在小堆插入要满足：

否则就要插入到大堆。

调堆情况：

在小堆m处插入节点x后，若x的值不大于大堆的m/2节点的值，则在小堆调整。否则，节点x与大堆的m/2结点交换，然后进行大堆调堆。在大堆n处插入结点x后，若x不小于小堆的n结点，则在大堆调整。否则，结点x与小堆的n结点交换，然后进行小堆调堆。

（1）插入4后

4先插入大堆，4<小堆中对应的19，和19交换。之后开始调整小堆即可。大堆显然无需调整。

（2）插入代码（有点乱，建议文字屡清楚思路）

//l[]为小堆,r[]为大堆,m、n分别为两个堆的元素个数,x为待插入元素

void insertDEPA(int l[],int r[],m,n,x)

{

  if(m>=n && m!=2^k-1 && [log2m]-[log2n]<=1) //[]这里暂时代表向下取整,k为二叉树高度

  {

      m++;

      if(x>r[m/2]) //交换

      {

          l[m]=r[m/2];

          c=m/2;

          f=c/2;

          while(f>0 && r[f]<x) //调大堆

          {

              r[c]=r[f];

              c=f;

              f=c/2;

          }

          r[c]=x;

      }

      else //调小堆

      {

        c=m;

        f=c/2;

        while(f>0 && l[f]>x)

        {

            l[c]=l[f];

            c=f;

            f=c/2;

        }

        l[c]=x;

      }

      else //调大堆

      {

            c=n;

            f=c/2;

            while(f>0 && r[f]<x)

            {

              r[c]=r[f];

              c=f;

              f=c/2;

            }

            r[c]=x;

      }

  }

}

巴特西

双堆DEAP

最新文章

热门文章