ヒープ　解答ページ | Programming Place Plus　アルゴリズムとデータ構造編【データ構造】　第９章

// heap.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "heap.h"


// ヒープ
struct Heap_tag {
    int*      data;        // データ本体
    size_t    capacity;    // 最大容量
};

#define SWAP(type,a,b)          { type work = a; a = b; b = work; }

static void up_heap(Heap heap, size_t index);
static void down_root(Heap heap);
static void heap_print_node(const Heap heap, size_t index, int level);


/*
    ヒープを作る
*/
Heap heap_create(size_t capacity)
{
    struct Heap_tag* heap = malloc( sizeof(struct Heap_tag) );
    heap->data = malloc( sizeof(int) * (capacity + 1) );  // 添字を 1 から始めるため、+ 1 して確保
    heap->capacity = capacity;

    heap->data[0] = 0;  // 要素数

    return heap;
}

/*
    ヒープを削除する
*/
void heap_delete(Heap heap)
{
    if( heap != NULL ){
        free( heap->data );
        free( heap );
    }
}

/*
    ヒープに要素を追加する
*/
bool heap_insert(Heap heap, int value)
{
    size_t size = heap_getsize(heap);

    // 容量が一杯でないか確認
    if( heap->capacity <= size ){
        return false;
    }


    // まず、末尾に追加する
    size_t index = size + 1;
    heap->data[index] = value;
    heap->data[0]++;

    // 適切な位置まで浮かび上がらせる
    up_heap(heap, index);

    return true;
}

/*
    ヒープから根を取り除く
*/
bool heap_remove_root(Heap heap, int* value)
{
    size_t size = heap_getsize(heap);

    // ヒープが空でないか確認する
    if( size <= 0 ){
        return false;
    }


    *value = heap->data[1];

    // ヒープの最後にある要素を、先頭に移動する
    heap->data[1] = heap->data[size];
    heap->data[0]--;

    // 先頭に移動させた要素を、正しい位置に沈める
    down_root(heap);

    return true;
}

/*
    ヒープから要素を探す
*/
bool heap_search(const Heap heap, int value)
{
    size_t size = heap_getsize(heap);

    for( int i = 1; i < size + 1; ++i ){
        if( heap->data[i] == value ){
            return true;
        }
    }

    return false;
}

/*
    ヒープに格納されている要素数を返す
*/
size_t heap_getsize(const Heap heap)
{
    return heap->data[0];
}

/*
    ヒープの内容を出力する
*/
void heap_print(const Heap heap)
{
    if( heap == NULL || heap_getsize(heap) <= 0 ){
        return;
    }

    heap_print_node( heap, 1, 0 );
}

/*
    ヒープの指定要素を適切な位置まで浮かび上がらせる
*/
void up_heap(Heap heap, size_t index)
{
    while( index > 1 ){  // 根に到達したら終わり
        size_t parent = index / 2;

        if( heap->data[parent] > heap->data[index] ){
            // 親との大小関係が逆なら入れ替える
            SWAP( int, heap->data[parent], heap->data[index] );

            // さらに親をたどる
            index = parent;
        }
        else{
            // 大小関係が正常だったら終わり
            break;
        }
    }
}

/*
    根を適切な位置まで沈める
*/
void down_root(Heap heap)
{
    size_t size = heap_getsize(heap);
    int index = 1;  // 根から開始

    while( index * 2 <= size + 1 ){
        int child = index * 2;  // 左の子の位置

        // ２つの子があるなら、小さい方を使う
        // 右の子の添字は、左の子の添字 + 1 である
        if( child + 1 < size + 1 ){
            if( heap->data[child] > heap->data[child + 1] ){
                child = child + 1;
            }
        }

        // 子との大小関係が逆なら、入れ替える
        if( heap->data[child] < heap->data[index] ){
            SWAP( int, heap->data[child], heap->data[index] );
            index = child;
        }
        else {
            break;
        }
    }
}

/*
    ヒープの内容を出力する
*/
void heap_print_node(const Heap heap, size_t index, int level)
{
    size_t size = heap_getsize(heap);

    for( int i = 1; i < level; ++i ){
        printf( "    " );
    }
    if( level > 0 ){
        printf( "+---" );
    }
    printf( "%d\n", heap->data[index] );


    // 左の子
    index *= 2;
    if( index < size + 1 ){
        heap_print_node( heap, index, level + 1 );
    }

    // 右の子
    index += 1;
    if( index < size + 1 ){
        heap_print_node( heap, index, level + 1 );
    }
}

int heap_max_value(const Heap heap)
{
    int max = INT_MIN;

    for( int i = heap_getsize(heap) / 2 + 1; i < heap->first_empty; ++i ){
        if( max < heap->data[i] ){
            max = heap->data[i];
        }
    }
    return max;
}