/* ppps_int_heap.c [サンプルライブラリ] int型のヒープ author: K.Y (Programming Place Plus) version 1.0.3 '2019/10/2 ・Webサイト側が C99規格へ対応したことに合わせて、コードを修正。 コメントスタイルと、変数宣言位置を変えた。 bool型を使う。 1.0.2 '2018/4/3 ・up_heap関数の実装の無駄を修正。 常に、根に到達するまで大小関係の比較を繰り返していた。 1.0.1 '2013/2/9 ・down_root関数を、より汎用的な down_heap関数に置き換えた。 これに伴って、ヒープの最大容量まで要素が追加されているとき、 ppps_int_heap_remove_root関数によって、 範囲外アクセスされることがあったのが修正された。 1.0.0 '2013/2/3 */ #include "ppps_int_heap.h" #include #include #include /* ヒープ */ struct PPPSIntHeap_tag { int* data; // データ本体 size_t capacity; // 最大容量 size_t first_empty; // 空になっている最初の位置 }; #define SWAP(type,a,b) { type work = a; a = b; b = work; } static void up_heap(PPPSIntHeap heap, size_t index); static void down_heap(PPPSIntHeap heap, size_t root, size_t end); static void heap_print_node(const PPPSIntHeap heap, size_t index, int level); /* ヒープを作る */ PPPSIntHeap ppps_int_heap_create(size_t capacity) { struct PPPSIntHeap_tag* heap = malloc( sizeof(struct PPPSIntHeap_tag) ); heap->data = malloc( sizeof(int) * (capacity + 1) ); // 添字を 1 から始めるため、+ 1 して確保 heap->capacity = capacity; heap->first_empty = 1; // 0番目は使わない return heap; } /* ヒープを削除する */ void ppps_int_heap_delete(PPPSIntHeap heap) { if( heap != NULL ){ free( heap->data ); free( heap ); } } /* ヒープに要素を追加する */ bool ppps_int_heap_insert(PPPSIntHeap heap, int value) { // 容量が一杯でないか確認 if( heap->capacity < heap->first_empty ){ return false; } // まず、末尾に追加する size_t index = heap->first_empty; heap->data[index] = value; heap->first_empty += 1; // 適切な位置まで浮かび上がらせる up_heap( heap, index ); return true; } /* ヒープから根を取り除く */ bool ppps_int_heap_remove_root(PPPSIntHeap heap, int* value) { /* ヒープが空でないか確認する */ if( ppps_int_heap_getsize(heap) <= 0 ){ return false; } *value = heap->data[1]; // ヒープの最後にある要素を、先頭に移動する heap->first_empty -= 1; heap->data[1] = heap->data[heap->first_empty]; // 先頭に移動させた要素を、正しい位置に沈める down_heap( heap, 1, heap->first_empty ); return true; } /* ヒープから要素を探す */ bool ppps_int_heap_search(const PPPSIntHeap heap, int value) { for( size_t i = 1; i < heap->first_empty; ++i ){ if( heap->data[i] == value ){ return true; } } return false; } /* ヒープに格納されている要素数を返す */ size_t ppps_int_heap_getsize(const PPPSIntHeap heap) { return heap->first_empty - 1; } /* ヒープの内容を出力する */ void ppps_int_heap_print(const PPPSIntHeap heap) { if( heap == NULL || ppps_int_heap_getsize(heap) <= 0 ){ return; } heap_print_node( heap, 1, 0 ); } /* ヒープの指定要素を適切な位置まで浮かび上がらせる */ void up_heap(PPPSIntHeap 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_heap(PPPSIntHeap heap, size_t root, size_t end) { while( root * 2 <= end ){ size_t child = root * 2; // 左の子の位置 // 2つの子があるなら、小さい方を使う // 右の子の添字は、左の子の添字 + 1 である if( child + 1 <= end ){ if( heap->data[child] > heap->data[child + 1] ){ child = child + 1; } } // 子との大小関係が逆なら、入れ替える if( heap->data[child] < heap->data[root] ){ SWAP( int, heap->data[child], heap->data[root] ); root = child; } else { break; } } } void heap_print_node(const PPPSIntHeap heap, size_t index, int level) { for( size_t i = 1; i < level; ++i ){ printf( " " ); } if( level > 0 ){ printf( "+---" ); } printf( "%d\n", heap->data[index] ); // 左の子 index *= 2; if( index < heap->first_empty ){ heap_print_node( heap, index, level + 1 ); } // 右の子 index += 1; if( index < heap->first_empty ){ heap_print_node( heap, index, level + 1 ); } }