最小最大堆min-max Heap

(1)由性质5只能插在奇数层，即根节点处，7下沉到右堆的min level，10下沉到max level，插入后满足min-max heap性质，很容易画出：

(2)由性质80也是向右堆插入，且插入到偶数层，处在max level，40则要下沉，为了满足性质，故直接下沉至10的右子树位置，即max level层

(3)一般前两题画图是为写代码做铺垫，先分析一下：

从插入位置进行调整,调整过程由下到上。首先根据元素个数求出插入元素所在层次数,以确定其插入层是最大层还是最小层。

若插入元素在最大层，则先比较插入元素是否比双亲小，如是，则先交换。之后，将小堆与祖先调堆,直到满足小堆定义或到达根结点:若插入元素不小于双亲，则调大堆,直到满足大堆定义。

若插入结点在最小层,则先比较插入元素是否比双亲大，如是，则先交换，之后，将大堆与祖先调堆;若插入结点在最小层且小于双亲，则将小堆与祖先调堆，直到满足小堆定义或到达根结点。

void MinMaxHeapIns(RecType R[],int n)

{

  //假设R[1..n-1]是最小最大堆，插入第n个元素，把R[1..n]调成最小最大堆

  j=n; R[0]=R[j];

  h=[log2n]+1; //求高度这里[]表示向下取整

  if(h%2==0) //插入元素在偶数层，是最大层

  {

    i=n/2;

    if(R[0].key<R[i].key)

    {

      //插入元素小于双亲，先与双亲交换，然后调小堆

      R[j]=R[i];

      j=i/4;

      while(j>0 && R[j]>R[i])

      {

        //调小堆

        R[i]=R[j];

        i=j;

        j=i/4;

      }

      R[i]=R[0];

    }

    else

    {

      //插入元素大于双亲，调大堆

      i=n;

      j=i/4;

      while(j>0 && R[j]<R[i])

      {

        R[i]=R[j];

        i=j;

        j=i/4;

      }

      R[i]=R[0];

    }

  }

  else //插入元素在奇数层，是最小层

  {

    i=n/2;

    if(R[0].key>R[i].key)

    {

      //插入元素大于双亲，先与双亲交换，然后调大堆

      R[j]=R[i];

      j=i/4;

      while(j>0 && R[j]<R[i])

      {

        //调大堆

        R[i]=R[j];

        i=j;

        j=i/4;

      }

      R[i]=R[0];

    }

    else

    {

      //插入元素小于双亲，调小堆

      i=n;

      j=i/4;

      while(j>0 && R[j]>R[i])

      {

        R[i]=R[j];

        i=j;

        j=i/4;

      }

      R[i]=R[0];

    }

  }

}

巴特西

最小最大堆min-max Heap

最新文章

热门文章