ヒープ

最近の主な更新 2006-05-21 - 第二版 2001-xx-xx - 初版 はじめに int 型の配列が与えられたとする．この配列から，値の大きい順で要素を取り 出したい．しかもできるだけ効率的に．どうすればよいだろうか． このような問題を解くためのデータ構造が，ヒープである． ヒープの解説に入る前に，まず，上の問題に対する単純な解法を考えてみる． おそらく，次のような方法が思いつくはずである．配列の要素を前から順に見 ていく．このとき，現在の最大値を格納する要素の添字を覚えておく．配列の 最後の要素まで到達したら，覚えておいた添字の場所にある要素を取り出す． これを，配列が空になるまで繰り返す． この方法では，配列の大きさを n としたとき，(n-1) + (n-2) + ... + 1 = n(n-1)/2 回の比較を必要とする．従って，計算量としてはO(n^2)のアルゴリ ズム