資料紹介

n個の整数を要素とする1次元配列Aの中から、要素の値の小さな順にk個までの要素を抽出したい。これを実現するための効率の良いアルゴリズムを考案せよ。ただし、nは比較的大きな数であり、またkはnに比べて非常に小さいものとする。
(ヒント)k<<nなので、与えられたn個のデータを全て昇順に整列させてから必要なk個のデータを抽出するのでは効率が悪い。したがって、全てのデータを整列させずに必要なk個のデータを得る方法を考えると良い。
考案したアルゴリズム
(1)n個の整数を要素とする1次元配列Aを半順順序木としたヒープBに組み直す。
(2)ヒープBをヒープソートの手順にて降順にソートを行うが、小さい数値からk個のみ確定した時点でヒープソートを中止する。この場合、ヒープBにおいて、B[n]〜B[n - k + 1]の要素が、小さな順のk個の要素となる。
考案したアルゴリズムの例
例を示すため、配列の要素数nは、9とし、抽出する要素の小さな値の個数kは、3とする。
(1)下記のような配列Aを半順序木へ組みなおし、ヒープBとする。
添字 1 2 3 4 5 6 7 8 9
要素 3 11 15 12 5 7 14 10 9

?添字1の要素3をヒープBに追加する

資料の原本内容 ( この資料を購入すると、テキストデータがみえます。 )

抽出アルゴリズム　レポート
n個の整数を要素とする1次元配列Aの中から、要素の値の小さな順にk個までの要素を抽出したい。これを実現するための効率の良いアルゴリズムを考案せよ。ただし、nは比較的大きな数であり、またkはnに比べて非常に小さいものとする。
(ヒント)k<<nなので、与えられたn個のデータを全て昇順に整列させてから必要なk個のデータを抽出するのでは効率が悪い。したがって、全てのデータを整列させずに必要なk個のデータを得る方法を考えると良い。
考案したアルゴリズム
n個の整数を要素とする1次元配列Aを半順順序木としたヒープBに組み直す。
ヒープBをヒープソートの手順にて降順にソートを行うが、小さい数値からk個のみ確定した時点でヒープソートを中止する。この場合、ヒープBにおいて、B[n]～B[n - k + 1]の要素が、小さな順のk個の要素となる。
考案したアルゴリズムの例
例を示すため、配列の要素数nは、9とし、抽出する要素の小さな値の個数kは、3とする。
下記のような配列Aを半順序木へ組みなおし、ヒープBとする。
添字123456789要素31115125...

コメント0件