ヒープの使い方?修正投稿です

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
よっしー

ヒープの使い方?修正投稿です

#1

投稿記事 by よっしー » 2年前

「ベクターS(N)について、前からi番目まで入力したとき、k番目に小さい数を出力する」プログラムを作ったつもりなのですが、「S(N)=10,9,8,7,6,5,4,3,2,1」k=3のとき、出力「10,10,10,9,8,7,6,5,4,3」を期待しているのに「10,10,10,9,8,7,7,6,6,5」となってしまいます。if、elseで意図しない場所に行っていないかチェックするため、a,b,cを出力させており、意図した通りに動いているように見えます。不具合の原因がわからず、一週間近く時間を無駄にしていて途方に暮れています。どなたか教えていただけませんでしょうか。どうかよろしくお願いいたします。

コード:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Heap_Max
{
    vector<int> heap;
    Heap_Max() {}

    void push(int x)
    {
        heap.push_back(x);
        int i = (int)heap.size() - 1;
        while (i > 0)
        {
            int p = (i - 1) / 2;
            if (heap[p] >= x)
                break;
            heap[i] = heap[p];
            i = p;
        }
        heap[i] = x;
    }
    int top()
    {
        if (!heap.empty())
            return heap[0];
        else
            return -1;
    }
    void pop()
    {
        if (heap.empty())
            return;
        int x = heap.back();
        int i = 0;
        while (i * 2 + 1 < (int)heap.size())
        {
            int child1 = i * 2 + 1, child2 = i * 2 + 2;
            if (child2 < (int)heap.size() && heap[child2] > heap[child1])
            {
                child1 = child2;
            }
            if (heap[child1] <= x)
                break;
            heap[i] = heap[child1];
            i = child1;
        }
        heap[i] = x;
    }
};
struct Heap_Min
{
    vector<int> heap;
    Heap_Min() {}

    void push(int x)
    {
        heap.push_back(x);
        int i = (int)heap.size() - 1;
        while (i > 0)
        {
            int p = (i - 1) / 2;
            if (heap[p] <= x)
                break;
            heap[i] = heap[p];
            i = p;
        }
        heap[i] = x;
    }
    int top() //最小値を取得
    {
        if (!heap.empty())
            return heap[0];
        else
            return -1;
    }
    void pop() //最小値を削除
    {
        if (heap.empty())
            return;
        int x = heap.back();
        int i = 0;
        while (i * 2 + 1 < (int)heap.size())
        {
            int child1 = i * 2 + 1, child2 = i * 2 + 2;
            if (child2 < (int)heap.size() && heap[child2] < heap[child1])
            {
                child1 = child2;
            }
            if (heap[child1] <= x)
                break;
            heap[i] = heap[child1];
            i = child1;
        }
        heap[i] = x;
    }
};

int main()
{
    int N, k;
    cin >> N >> k;

    vector<int> S(N);
    for (int i = 0; i < N; ++i)
    {
        cin >> S[i];
    }

    Heap_Max low;
    Heap_Min high;
    for (int i = 0; i < N; ++i)
    {
        if (i < k)
        {
            cout << "a" << endl;
            low.push(S[i]);
        }
        else
        {
            int M = low.top(); //Mはlowの最大値であり、k番目に小さい数
            if (S[i] >= M)
            {
                high.push(S[i]);
                cout << "b" << endl;
            }
            else
            {
                low.push(S[i]);
                low.pop();
                cout << "c" << endl;
            }
        }
        cout << i << ":" << low.top() << endl;
    }
}
[/blur]

よっしー

Re: ヒープの使い方?修正投稿です

#2

投稿記事 by よっしー » 2年前

度々申し訳ありません。誤って、ぼかし加工が入ってしまったので、返信欄に質問文を再掲させていただきます。

「ベクターS(N)について、前からi番目まで入力したとき、k番目に小さい数を出力する」プログラムを作ったつもりなのですが、「S(N)=10,9,8,7,6,5,4,3,2,1」k=3のとき、出力「10,10,10,9,8,7,6,5,4,3」を期待しているのに「10,10,10,9,8,7,7,6,6,5」となってしまいます。if、elseで意図しない場所に行っていないかチェックするため、a,b,cを出力させており、意図した通りに動いているように見えます。不具合の原因がわからず、一週間近く時間を無駄にしていて途方に暮れています。どなたか教えていただけませんでしょうか。どうかよろしくお願いいたします。

アバター
あたっしゅ
記事: 663
登録日時: 13年前
住所: 東京23区
連絡を取る:

Re: ヒープの使い方?修正投稿です

#3

投稿記事 by あたっしゅ » 2年前

東上☆海美☆「
STL 使うのなら、ありもん使えばいいみみ。

コード:

//
// https://dixq.net/forum/viewtopic.php?f=3&t=21305&sid=0a062e1298175f45d2bb954b9f70c487
// ヒープの使い方?修正投稿です - ミクプラ(ja)
//
//  for VS2021 Preview on Windows Insider Preview
//
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

using namespace std;


int
main() try
{
#if 0
    int N, k;
    cin >> N >> k;

    vector<int> S(N);
    for (int i = 0; i < N; ++i)
    {
        cin >> S[i];
    }
#else
    const int   N = 10;
    int         S[N] = { 10,9,8,7,6,5,4,3,2,1 };
    const int   k = 3;
#endif

    list<int> lst;

    for (int i = 0; i < N; i++) {
        lst.push_back(S[i]);
    }

    lst.sort();

    list<int>::iterator p = lst.begin();
    for (int i = 0; i < k; i++) {
        cout << i << ":" << p << endl;
        p++;
    }

    return EXIT_SUCCESS;
}
catch (...)
{
	std::cout << "例外発生" << std::endl;

	return EXIT_FAILURE;
}


// end.
VTuber:
東上☆海美☆(とうじょう・うみみ)
http://atassyu.php.xdomain.jp/vtuber/index.html
レスがついていないものを優先して、レスするみみ。時々、見当外れなレスしみみ。

中の人:
手提鞄あたッしュ、[MrAtassyu] 手提鞄屋魚有店
http://ameblo.jp/mratassyu/
Pixiv: 666303
Windows, Mac, Linux, Haiku, Raspbery Pi, Jetson Nano, 電子ブロック 持ち。

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: ヒープの使い方?修正投稿です

#4

投稿記事 by みけCAT » 2年前

Heap_Max においても、 Heap_Min においても、pop 関数内において

コード:

            if (heap[child1] <= x)
                break;
という処理があります。
この2個のクラスでは比較が反対になるはずなのに、これは不自然ですね。
あたっしゅ さんが書きました:
2年前
STL 使うのなら、ありもん使えばいいみみ。
同意します。
std::priority_queue が使えるでしょう。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: ヒープの使い方?修正投稿です

#5

投稿記事 by みけCAT » 2年前

さらに、pop 関数内において、値を移動するだけで「余計な要素を削除する」処理が抜けているようですね。
あたっしゅ さんが書きました:
2年前

コード:

        cout << i << ":" << p << endl;
コンパイルエラーになりました。
p の代わりに、 *p とするべきではないでしょうか?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

投稿者

解決しました!

#6

投稿記事 by 投稿者 » 2年前

東上☆海美☆さん、みけCATさん、ありがとうございます!

お二人の言葉で定義していたヒープの処理がいつのまにかおかしくなっていたのが分かりました!
具体的には、heap.pop_back();が消えていました。
ヒープの学習の確認のための問題だったのですが、何度も手を入れているうちに間違った手直しが残ってこのようなことになったのだと思います。
本当にありがとうございます!

コード:

    void pop()
    {
        if (heap.empty())
            return;
        int x = heap.back();
        heap.pop_back();
        int i = 0;
        while (i * 2 + 1 < (int)heap.size())

返信

“C言語何でも質問掲示板” へ戻る