Heap (data structure)

ウィキペディア

ヒープ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/01 14:21 UTC 版)

ヒープ（英: heap）とは、「子要素は親要素より常に大きいか等しい（または常に小さいか等しい）」という制約を持つ木構造の事。単に「ヒープ」という場合、二分木を使った二分ヒープを指すことが多いため、そちらを参照すること。

二分ヒープのインデックス付け

概要

ヒープは最小値（または最大値）を求めるのに適した木構造の一種であり、「子要素は親要素より常に大きいか等しい（または常に小さいか等しい）」という制約を持つ。子要素が複数ある場合、子要素間の大小関係に制約はない。

フィボナッチヒープの場合、挿入や最小値検索やマージが一定償却時間で行え、削除は$O(\log n)$カテゴリ