C言語関係掲示板

過去ログ

No７５３　ヒープの探索

[戻る]　[ホームページ]
No.9374
ヒープの探索
投稿者---T-モコ(2003/09/20 20:55:18)


A[N]を利用したヒープのプログラムを作りました。
A[i]の親は、A[(i-1)/2]であるヒープです。
（上に行くほど小さい整数を格納）
そしていまある整列されたヒープのなかからキーボードから入力した値ｘを検索する関数findを、
x ←検索する値
A[]←ヒープソートされた配列
n ←現在格納されているA[]の最後の添え字
として、 
int find(int x, int *A, int i, int n)
{
	int p,q;

	
	if(A[i] == x){
			
		return i;	
	}
	
	if(i>n){
		return -1;
	}
	
	
	if(A[i]<x){
		i = i*2 + 1;
		p = find(x, A, i, n);
		if(p > -1){
			return p;
		} 
		
		i++;
		
		q = find(x, A, i, n);
		
		if(q > -1){
			return q;
		}
	}
	return -1;
			
	
}

呼び出す際に、find(x,A,0,n)と与えることによりfind関数はｘを格納しているA[p]のpを返すというものです。
いちおうこれで返すようにはなったのですが、アルゴリズムはあっているでしょうか。それとなんかもっとキレイに書けないでしょうか。
自信が無いので質問してみました
No.9399
Re:ヒープの探索
投稿者---ともじ(2003/09/22 19:58:14)


こんばんは。返信が遅くなり申し訳ありません。

>A[N]を利用したヒープのプログラムを作りました。

>呼び出す際に、find(x,A,0,n)と与えることによりfind関数はｘを格納して
>いるA[p]のpを返すというものです。
>いちおうこれで返すようにはなったのですが、アルゴリズムはあっている
>でしょうか。それとなんかもっとキレイに書けないでしょうか。

このプログラムですと、
	if(A[i] == x){
		return i;	
	}
	if(i>n){
		return -1;
	}

で、Aの範囲を超えてアクセスする可能性があります。
	if(i>=n){
		return -1;
	}
	if(A[i] == x){
		return i;	
	}

とする必要があります。

ヒープ探索の定石のアルゴリズムは実は知らないのですが、この
プログラムだと、枝の右端に探索キーがあるときに、(p*2+1)-1 の
全ての要素を比較することになり、効率がよくないのではないでしょうか。
再帰を使わずに次のようなものではどうでしょうか。
int find(int x, int *A, int n)
{
    int i, j;
    
    for (i = 0; i < n; i = i * 2 + 1) {
        if (A[i] == x) return i;
        if (A[i] > x) break;
    }
    for (j = (i - 1) / 2; j < i; j++) {
        if (A[j] == x) return j;
    }
    return -1;
}


No.9401
Re:ヒープの探索
投稿者---かずま(2003/09/22 21:01:14)


> 再帰を使わずに次のようなものではどうでしょうか。

これだと、int A[ ] = { 1, 2, 5, 3, 4, 6 } という配列から、
5 を見つけることができないのではありませんか？
No.9404
Re:ヒープの探索
投稿者---ともじ(2003/09/22 23:13:56)


>これだと、int A[ ] = { 1, 2, 5, 3, 4, 6 } という配列から、
>5 を見つけることができないのではありませんか？

No.9374で
A[]←ヒープソートされた配列
とあるので、昇順にデータは並んでいるものとみなしました。
もっとも、昇順に並んでいるデータの探索にヒープを使う必要はないのですが。
No.9405
Re:ヒープの探索
投稿者---たか(2003/09/22 23:20:45)


>もっとも、昇順に並んでいるデータの探索にヒープを使う必要はないのですが。

bsearch()が使えますね。
それとももしかしたらヒープ配列と書くつもりだったのかもしれません。
No.9414
Re:ヒープの探索
投稿者---かずま(2003/09/23 14:08:52)


> A[]←ヒープソートされた配列
> とあるので、昇順にデータは並んでいるものとみなしました。

なるほど。配列全体がすでにソートされているのだったら問題ありません。

私は、

> A[i]の親は、A[(i-1)/2]であるヒープです。
> （上に行くほど小さい整数を格納）
> そしていまある整列されたヒープのなかから

という記述をみて、ヒープだけを考えていました。
失礼しました。
No.9422
Re:ヒープの探索
投稿者---T-モコ(2003/09/23 22:45:34)


A[]←ヒープソートされた配列

ごめんなさい。「ヒープソートされた配列」ではなく、たかさんがおっしゃっている通り「ヒープ配列」に訂正させてくださいｍ(＿　＿)ｍ
たとえば
A[]={1,3,2,4,5,8,6}
も「ヒープ配列」とよべるかよくわからないのですが、

子の親は子より小さい　

という規則を守っている配列です。
No.9423
Re:ヒープの探索
投稿者---たか(2003/09/23 23:21:15)


>ごめんなさい。「ヒープソートされた配列」ではなく、たかさんがおっしゃっている通り「ヒープ配列」に訂正させてくださいｍ(＿　＿)ｍ

という事はC++のSTLのheapと同じ意味ですね。配列内にヒープ木を構築
する事はよくあります。

今日は時間が遅いので、明日暇があったらレスします。
No.9424
Re:ヒープの探索
投稿者---T-モコ(2003/09/24 00:24:47)


あとひとつ訂正です＾＾；

n ←現在格納されているA[]の最後の添え字

ではなく

ｎは現時点での要素数

です

A[]={1,3,2,4,5,8,6}

なら最初の言い方だと６ですが、本当はnは７ですｍ(_ _)ｍ
レスで改良していただいたプログラムは今から研究してみます！
No.9430
Re:ヒープの探索
投稿者---たか(2003/09/24 14:48:01)


ヒープ配列を二分木と見なすと、幅優先探索と深さ優先探索の二種類が
あります。見せていただいたプログラムは深さ優先探索です。

それぞれの探索の利点・欠点は

幅優先探索:
・ヒープの並び方に探索時間は影響を受けない。
・探索の際にはいつも同じ程度のコストがかかる。
・スタックを使用せず代わりにキューを使用するのでスタックオーバー
フローの心配がない。

深さ優先探索
・もし一度目でキーのある方の枝を選んだ場合、探索時間は半分で
済むが、キーのない方の枝を選んだ場合は２倍程度の時間がかかる。
平均コストは幅優先探索と同じ。
・再帰を用いた場合スタックを多量に消費する。

深さ優先探索は再帰プログラムとして、幅優先探索はキューを用いて
実現できます。

ちなみにヒープ木を構成していると言っても、普通のランダムな二分木
に比べて、探索時間が極端に短くなるようなアドバンテージはありませ
ん。ヒープ木がその最大の威力を発揮するのはヒープソートの時です。
No.9431
Re:ヒープの探索
投稿者---たか(2003/09/24 14:58:56)


あ、申し忘れましたが、一般的には深さ優先探索の方が幅優先探索よりも
スマートなプログラミングができます。

幅優先探索はごちゃごちゃします。
No.9435
Re:ヒープの探索
投稿者---たか(2003/09/24 18:36:20)


今急に思いついた(仕事の一休み)のですが、どうせヒープ配列って一見
ランダム配列に見えるから、線形探索した方が楽でいいかもしれません。
多分効率は変わらないでしょう。というか線形探索はプログラムが単純
な分だけ一番速くなるかも・・・・・・