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