#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]
ヒープの使い方?修正投稿です
ヒープの使い方?修正投稿です
「ベクター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を出力させており、意図した通りに動いているように見えます。不具合の原因がわからず、一週間近く時間を無駄にしていて途方に暮れています。どなたか教えていただけませんでしょうか。どうかよろしくお願いいたします。
Re: ヒープの使い方?修正投稿です
度々申し訳ありません。誤って、ぼかし加工が入ってしまったので、返信欄に質問文を再掲させていただきます。
「ベクター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を出力させており、意図した通りに動いているように見えます。不具合の原因がわからず、一週間近く時間を無駄にしていて途方に暮れています。どなたか教えていただけませんでしょうか。どうかよろしくお願いいたします。
「ベクター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を出力させており、意図した通りに動いているように見えます。不具合の原因がわからず、一週間近く時間を無駄にしていて途方に暮れています。どなたか教えていただけませんでしょうか。どうかよろしくお願いいたします。
Re: ヒープの使い方?修正投稿です
東上☆海美☆「
STL 使うのなら、ありもん使えばいいみみ。
」
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, 電子ブロック 持ち。
東上☆海美☆(とうじょう・うみみ)
http://atassyu.php.xdomain.jp/vtuber/index.html
レスがついていないものを優先して、レスするみみ。時々、見当外れなレスしみみ。
中の人:
手提鞄あたッしュ、[MrAtassyu] 手提鞄屋魚有店
http://ameblo.jp/mratassyu/
Pixiv: 666303
Windows, Mac, Linux, Haiku, Raspbery Pi, Jetson Nano, 電子ブロック 持ち。
Re: ヒープの使い方?修正投稿です
Heap_Max においても、 Heap_Min においても、pop 関数内において
という処理があります。
この2個のクラスでは比較が反対になるはずなのに、これは不自然ですね。
std::priority_queue が使えるでしょう。
この2個のクラスでは比較が反対になるはずなのに、これは不自然ですね。
同意します。
std::priority_queue が使えるでしょう。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: ヒープの使い方?修正投稿です
さらに、pop 関数内において、値を移動するだけで「余計な要素を削除する」処理が抜けているようですね。
p の代わりに、 *p とするべきではないでしょうか?
コンパイルエラーになりました。
p の代わりに、 *p とするべきではないでしょうか?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
解決しました!
東上☆海美☆さん、みけCATさん、ありがとうございます!
お二人の言葉で定義していたヒープの処理がいつのまにかおかしくなっていたのが分かりました!
具体的には、heap.pop_back();が消えていました。
ヒープの学習の確認のための問題だったのですが、何度も手を入れているうちに間違った手直しが残ってこのようなことになったのだと思います。
本当にありがとうございます!
お二人の言葉で定義していたヒープの処理がいつのまにかおかしくなっていたのが分かりました!
具体的には、heap.pop_back();が消えていました。
ヒープの学習の確認のための問題だったのですが、何度も手を入れているうちに間違った手直しが残ってこのようなことになったのだと思います。
本当にありがとうございます!