C言語 構造体を用いたヒープのdeleteminと要素の入れ替え

Question

以下の画像のヒープにdeletemin1回行い、要素の置き換えをしてシフトアップ、シフトダウンでヒープを昇順に再構築するプログラムを考えているのですが、以下のコードのようにヒープを作る所まではできたのですが、そこから先が分かりません。どのようにしてdeleteminをしてヒープを再構築したら良いのでしょうか？

#include <stdio.h>
int main(void){
  struct tag{
    int name;
    int key;
    struct tag *left;
    struct tag *right;
  };

  struct tag tag0,tag1,tag2,tag3,tag4,tag5,*root;

  root = &tag0;

  root->name = 0;
  root->key = 5;
  root->left = &tag1;
  root->right = &tag2;

  root->left->key = 7;
  root->left->name = 1;
  root->left->left = &tag3;
  root->left->right = &tag4;

  root->right->key = 11;
  root->right->name = 2;
  root->right->left = &tag5;
  root->right->right = NULL;

  root->left->left->key = 18;
  root->left->left->name = 3;
  root->left->left->left = NULL;
  root->left->left->right = NULL;

  root->left->right->key = 22;
  root->left->right->name = 4;
  root->left->right->left = NULL;
  root->left->right->right = NULL;

  root->right->left->key = 21;
  root->right->left->name = 5;
  root->right->left->left = NULL;
  root->right->left->right = NULL;

  printf("%d %d %d %d %d %d\n",tag0.key,tag1.key,tag2.key,tag3.key,tag4.key,tag>
return 0;
}

Answer 1

deleteminとはよーするに rootが指す要素を削除するんですよね。
削除されてできた空席は、そのふたりの子のうち小さい方に埋めて(削除された親の位置にズレて)もらいます。(子がひとりならその子に)
そーすると今まで子のいた席が空席となります。その空席は、その二人の子のうち小さい方に埋めてもらいます。
以下同文...子がいなくなったらおしまい。

Comments

[keeen]

理解できました。ありがとうございます。