よくわかるヒープソート

以前のこの記事には誤ったコードが記載されておりました。自信満々に嘘コードを書いたことをお詫び申し上げます。

ぐぐって上位に出てくるコードがどれも冗長すぎる…………………

空間計算量はO(1)（追加領域を必要としない）、最悪・平均時間計算量がO(n log n)。

大体std::sortの中身になっているイントロソートは、クイックソートが深くなり過ぎたらヒープソートに切り替えるというもの。

オーダーはよいがクイックソートよりは定数項がでかい+ヒープなので空間的局所性が低くキャッシュで不利になる可能性がある？

void HeapSort(vector<int>& data) {
  // ヒープに入れていく
  // [0, i_end]
  for (int i_end = 0; i_end < data.size(); ++i_end) {
    int idx = i_end;
    while (idx > 0) {
      idx = (idx - 1) / 2;
      if (2 * idx + 1 <= i_end && data[idx] < data[2 * idx + 1]) {
        swap(data[idx], data[2 * idx + 1]);
        continue;
      }
      if (2 * idx + 2 <= i_end && data[idx] < data[2 * idx + 2]) {
        swap(data[idx], data[2 * idx + 2]);
        continue;
      }
      break;
    }
  }

  // ヒープから取り出していく
  for (int i_end = data.size() - 1; i_end >= 0; --i_end) {
    // [0, i_end]
    swap(data[0], data[i_end]);
    // now [0, i_end)
    int idx = 0;
    while (true) {
      int nidx = idx;
      if (2 * idx + 1 < i_end && data[nidx] < data[2 * idx + 1]) {
        nidx = 2 * idx + 1;
      }
      if (2 * idx + 2 < i_end && data[nidx] < data[2 * idx + 2]) {
        nidx = 2 * idx + 2;
      }
      if (idx == nidx) break;
      swap(data[idx], data[nidx]);
      idx = nidx;
    }
  }
}