出典　作ってわかるCプログラミング
日下部陽一 

読んでる本であともう１つ山があるのですが、もしよろしければ
ご指導ください。

ヒープについてなのですが、これのプログラムがでているのですが
わからなくて不安な部分があります。

ヒープというのはツリーというものがありましたがそれの仲間みたいですね。

どのような時につかわれるのですか？

そして、もっとイメージし難いのが、ヒープ構造は配列の上で作られるという
ことです。

配列というと、線状にならんでいるのを想像するのですが、とても木のように
は、みえないので想像がつきません。

本によると、a[1]には、ルート(root:木の根子)、a[2]、a[3]にlevel 1の要素を
・・・のように順に格納していく。

そうすれば、

a[i]の子はa[i*2]とa[i*2+1]である。
a[i]の親はa[i/2]である。

という関係が成り立つそうです。

と書いてありますが、上に書いた理由から想像がつきません。
配列上に木の形のように構成できるものなのでしょうか？

あとは元のプログラムの細かいところの質問と役目を教えてください。
わからない部分は←で示して質問してあります。

heap.c

int i_comp(int, int); /*比較*/
void i_swap(int, int); /*交換*/
void i_remove(int); /*削除*/
void i_add(int, char *); /*追加*/
static void heap(int, int);

static int n_item = 0;

/*
 * sort_heap() - ヒープをソーティング
 */
void sort_heap(int n)
{
    int i;
    n_item = n;←　n_itemというのは、何ですか？
    for (i = n_item / 2; i >= 1; i--)←　なぜ、i = n_item / 2と半分になってい
        heap(i, n_item);←　i　は何ですか？
}

static void heap(int i, int n)
{
    int child;

    if (i <= n / 2) {←　また、半分になっているますね・・・
        if (2 * i + 1 > n)←　ここは、なぜ2 * i + 1となっていて、この条件と
なっているのですか？
        child = 2 * i;←　これもなぜですか？
    　　else {
        if (i_comp(2 * i, 2 * i + 1) > 0)←　ここも同じです
            child = 2 * i;←　これもです
        else
            child = 2 * i + 1;←　これもです
        }
        if (i_comp(i, child) < 0) {←　ここの条件？
            i_swap(i, child);
        heap(child, n);
        }
    }
}

/*
 * add_item() - ヒープへのデータ追加
 */
void add_item(char *s)
{
    int i;

    i = ++n_item;←　なぜこのようになっているのですか？
    i_add(i, s); /* tree 末尾に追加 */ 
    /* 自分(i) > 親 (i / 2) の間 */
    while (i_comp(i, i / 2) > 0) {
        i_swap(i, i/2); /* 交換する */
        i = i / 2;
        if (i == 1) /* root まで行ったら */←　これがrootの条件ですか？
        break; /* おしまい */
    }
}

/*
 * remove_root() - ルートの削除
 */
void remove_root(void)
{
    i_swap(1, n_item);  /*rootの要素を削除し、*/
    i_remove(n_item);   /*一番下位の要素をrootへ移動*/
    sort_heap(--n_item);    /*treeの最整列*/
}

sub.c

#include <stdio.h>
#include <string.h>

#define MAXS 8
#define MAXITEMS 1024

static char array[MAXITEMS][MAXS];

/*
 * i_add() - 配列に要素を入れる
 */
void i_add(int n, char *s)
{
    strcpy(array[n], s);←　s　はなんですか？
}

/*
 * i_print(int n) - 指定された要素を表示
 */
void i_print(int n)
{
    printf("%3d: %s\n", n, array[n]);
}

/*
 * i_swap() - 二つの要素を入れ換える
 */
void i_swap(int a, int b)
{
    char temp_str[MAXS];

    strcpy(temp_str, array[a]);
    strcpy(array[a], array[b]);
    strcpy(array[b], temp_str);
}

/*
 * i_comp() - ２つの要素を比較する 
 */
int i_comp(int a, int b)
{
    return (strcmp(array[a], array[b]));
}

/*
 * i_remove - 指定された要素の削除
 */
void i_remove8int n)
{
    ; /* 今回は何もすることがない */
}

main.c←　メインってどのようなものですか？動き的には・・・
どのようなことをするものですか？

#include <stdio.h>

extern void i_add(int, char *);
extern void i_print(int);
extern void remove_root(void);

char *data[] = {
    "cab","dab","gab","jab",
    "lab","nab","tab","lac",
    "sac","bad","dad","fad",
    "gad","had","lad","mad",
    "pad","sad","tad","wad",
    "oaf","bag","fag","gag",
    "jag","lag","nag","rag",
    "sag","tag","wag","zag",
    "bah","wah","yah","raj",
    "oak","yak","gal","pai",
    "bam","cam","dam","gam",
    "ham","jam","lam","ram",
    "tam","yam","ban","can",
    "fan","man","pan","ran",
    "tan","van","wan","tao",
    "cap","gap","hap","lap",
    "map","nap","pap","rap",
    "sap","tap"
};

main()
{
    int i, n;

    n = sizeof(data) / sizeof(cahr *);←　ここの処理は何をしているのですか？
    for (i = 1; i <= n; i++)
        i_add(i, data[i - 1]);
    for (i = 1; i <= n; i++)
        i_print(i);
    sort_heap(n);
    for (i = 1; i <= n; i++)
        i_print(i);
    for (i = 1; i <= n; i++) {
        i_print(1);
        remove_root();
    }
}

#include <stdio.h>
#include <string.h>

#define SWAP(a, i, j)  { char *t = a[i]; a[i] = a[j]; a[j] = t; }
#define COMP(a, i, j)  strcmp(a[i], a[j])

void down_heap(char **a, int n, int i)
{
    while (i < n / 2) {
        int child = i * 2 + 1;
        if (child + 1 < n && COMP(a, child + 1, child) > 0)
            child++;
        if (COMP(a, i, child]) >= 0)
            break;
        SWAP(a, i, child)
        i = child;
    }
}

void heap_sort(char **a, int n)
{
    int i;
    for (i = n / 2 - 1; i >= 0; i--)
        down_heap(a, n, i);
    while (--n) {
        SWAP(a, n, 0)
        down_heap(a, n, 0);
    }
}

void print(char **a, int n)
{
    int i;
    for (i = 0; i < n; i++)
        printf(" %s", a[i]);
    printf("\n");
}

int main(void)
{
    char *a[] = {
        "alpha", "beta", "gamma", "delta", "epsilon", "eta", "zeta", "theta"
    };
    const int n = sizeof(a) / sizeof(a[0]);

    print(a, n);
    heap_sort(a, n);
    print(a, n);
    return 0;
}