ポインタを用いた（配列を使わない）2分ヒープの実装 - 親参照バージョン

前書き

以前、次のような記事を書きました。

その中で、

ヒープでは「親子ノードの入れ替え」という操作が必要になるので、親ノードへのポインタも持っている方が良いように思うかも知れませんが、それは必須ではなく、むしろそれによってポインタつなぎ変え操作が煩雑になるので避けました。

と書いたのですが、ノード接続操作を整理すればそれほど煩雑にはならないと気付いたので、修正しました。ノードからの親参照が可能なバージョンです。

データ構造再定義

修正したノードの定義は次の通りです。

typedef struct __heap_t{
  struct __heap_t *parent;
  struct __heap_t *child[2];
  uint size;
  int data;
} Heap;

parentが増えただけです。

初期化操作にも次のようにparentを追加します。

Heap *HeapInit(Heap *node)
{
  node->parent = node->child[0] = node->child[1] = NULL;
  node->size = 0;
  return node;
}

親子ノードの入れ替え

割と自明な操作ですが、次の親子バインドを定義します。

void HeapBindParentChild(Heap *parent, int id, Heap *child)
{
  if( ( parent->child[id] = child ) ) child->parent = parent;
}

これを用いて、親子ノードの入れ替え操作を次のように修正します。

void HeapNodeSwap(Heap *node, int cid)
{
  Heap *parent, *tmp;
  int id;

  parent = node->parent;
  id = HeapParentID( node );
  HeapBindParentChild( parent, id, node->child[cid] );
  HeapBindParentChild( node, cid, node->child[cid]->child[cid] );
  HeapBindParentChild( parent->child[id], cid, node );
  tmp = node->child[1-cid];
  HeapBindParentChild( node, 1-cid, parent->child[id]->child[1-cid] );
  HeapBindParentChild( parent->child[id], 1-cid, tmp );
}

元の関数でchildだけ指定していた箇所を、上記のHeapBindParentChild()で置き換えた格好です。
操作の考え方は元と同じなのですが、ノードが自分の親を知っているので引数で与える必要が無くなります。
HeapParentID()は、親から見て自分がどちらのノードかを知るための次のマクロです。

# define HeapParentID(n) ( (n)->parent->child[0] == (n) ? 0 : ( (n)->parent->child[1] =
= (n) ? 1 : -1 ) )

ノード挿入

ノード挿入操作は次のように大きく変えます。

Heap *HeapAddComplete(Heap *tree, int val)
{
  Heap *node, *np_new;
  uint mask, cid;

  if( !( np_new = HeapNodeAlloc( val ) ) ) return NULL;
  if( ++tree->size == 1 ){
    HeapBindParentChild( tree, 0, np_new );
    return tree->child[0];
  }
  HeapMaskInit( tree, &mask );
  for( node=tree->child[0]; ; node=node->child[cid], mask>>=1 ){
    cid = mask & tree->size ? 1 : 0;
    if( mask == 1 ) break;
  }
  HeapBindParentChild( node, cid, np_new );
  return np_new;
}

Heap *HeapUp(Heap *tree, Heap *node, int (* cmp)(Heap*,Heap*,void*), void *util)
{
  while( node->parent != tree && !cmp( node->parent, node, util ) )
    HeapNodeSwap( node->parent, HeapParentID( node ) );
  return node;
}

Heap *HeapAdd(Heap *tree, int val, int (* cmp)(Heap*,Heap*,void*), void *util)
{
  return HeapUp( tree, HeapAddComplete( tree, val ), cmp, util );
}

HeapNodeAlloc()、HeapMaskInit()は前回定義したものと同じです。
HeapUp()を明示的に分離したのは、

• 挿入のタイミング以外にもノード上昇処理をしたい時があった
• 再帰を無くしたかった

という二つの理由によります。

ノード削除

ノード削除の方も再帰を無くしました。

Heap *HeapDown(Heap *node, int (* cmp)(Heap*,Heap*,void*), void *util)
{
  uint cid;

  while( node->child[0] ){
    cid = !node->child[1] ? 0 : ( cmp( node->child[0], node->child[1], util ) ? 0 : 1 );
    if( cmp( node, node->child[cid], util ) ) break;
    HeapNodeSwap( node, cid );
  }
  return node;
}

Heap *HeapDelete(Heap *tree, int (* cmp)(Heap*,Heap*,void*), void *util)
{
  Heap *ret, *np;

  uint mask, cid;
  HeapMaskInit( tree, &mask );
  for( np=tree->child[0]; np; mask>>=1, np=np->child[cid] ){
    cid = mask & tree->size ? 1 : 0;
    if( mask == 1 ) break;
  }
  ret = tree->child[0];
  if( !np ){
    tree->child[0] = NULL;
  } else if( np->child[cid] ){
    HeapBindParentChild( tree, 0, np->child[cid] );
    np->child[cid] = NULL;
    HeapBindParentChild( tree->child[0], 0, ret->child[0] );
    HeapBindParentChild( tree->child[0], 1, ret->child[1] );
    HeapDown( tree->child[0], cmp, util );
  }
  ret->parent = ret->child[0] = ret->child[1] = NULL;
  tree->size--;
  return ret;
}

本質的な処理は前回から変わりありません。HeapNodeSwap()と同様に、childだけ指定していた箇所をHeapBindParentChild()で置き換えました。

修正は以上です。テストは省略します。

親参照を可能にしたことで何が嬉しいかと言うと、HeapUp()とHeapDown()を気軽に呼び出せるようになったことです。再帰を無くしたのはおまけですが、これにより比較的大きな木を作る際にもスタックサイズをあまり気にしなくて済むようになりました。