ヒープソートの実装に失敗します

Question

前提

ヒープソートを実装したいです。

実現したいこと

発生している問題・エラーメッセージ

535 725 649 643 963 393 279 188 166 163

該当のソースコード

#include<bits/stdc++.h>
using namespace std;
#include<time.h>

void pushdown(vector<int>&A, int first, int last){
    int i = first;
    while(i <= (last-1) / 2){
        int j;
        if(A[(2*i+1)] < A[(2*i+2)]){ //小さいほうの子の番号
            j = (2*i+1);
        }
        else j = (2*i+2);
        if(A[j] < A[i]){ //子が親より小さかった場合
            swap(A[i], A[j]);
            i = j;
        }
        else return;
    }
}

void HeapSort(vector<int>&A){
    int n = A.size();
    vector<int> B;
    for(int irev = 0; irev <= n/2; irev++) {
        int i = n/2 - irev;
        pushdown(A, i, n-1);
    }
    for(int irev = 1; irev <= n-1; irev++){
        int i = n - irev;
        swap(A[0], A[i]);
        pushdown(A, 0, i-1);
    } 
}

int main(){
    vector<int> a = {963,643,163,535,725,188,649,279,393,166};
    HeapSort(a);
    for (int i = 0; i< 10; i++){
        cout << a[i] << " ";
    }
}

試したこと

サンプルコードを参照しながら怪しい部分を書き換えました。

補足情報（FW/ツールのバージョンなど）

Comments

[Zuishin]

アップヒープが無く、私の知っているヒープソートとは違うように見えますが、元にしたサンプルコードはどこにありますか？

Answer 1

問題点が3つあります。

1つ目は、pushdownが、子供が1つしかない場合に対応していないことです。
例えば、firstが0、lastが1の場合、最初のループでiが0となり、A[(2*i+2)]がlastより後ろへのアクセスとなってしまいます。

2つ目は、pushdownのfirst,lastがともに0の場合も子要素にアクセスしていることです。
while(i <= (last-1) / 2)の条件を考えると、(last-1)が-1、(last-1)/2が0となるため、初回のループが実行されてしまいます。

3つ目は、ヒープで最大値を求めなければならないのに、最小値を求めていることです。
ヒープで最小値を求めているため、各々のswapで最小値を一番後ろに移動していくことになります。その結果、昇順ではなく降順にソートされてしまいます。

前回もそうでしたが、vectorの添え字の範囲外アクセスに気づかないケースが多いように思います。コンパイルにg++を使っているなら、ソースの先頭に#define _GLIBCXX_DEBUGと入れることで、範囲外アクセスをチェックしてエラーにしてくれるようになるので、利用を検討してください。

---

プログラムが意図通りに動かない場合にやるべきことは、「サンプルコードを参照しながら怪しい部分を書き換えました。」ではなく「デバッグ」です。意図通りの動作にならない原因を調査しないまま修正すると、かえって正解から離れていく恐れがあります。変数の値が意図通りになっているか確認しつつ、1行ずつ実行していけば、どこで想定外の事象が発生しているか原因がはっきりします。デバッグ環境の整え方は検索すれば見つかると思います。