Algorithms/Sorting/Heap Sort

Heap Sort

ヒープソート

Outline

ヒープソートは、データ構造としてHeap?を用いるソートである.
ヒープはそれが保持する要素の最大要素が必ず根に格納されているので、
その根の値を最終配列の最後尾に代入することを繰り返すと
データがソートされた配列を得る事ができる.

ヒープの処理は以下の三段階に分かれている.
ここで、nは入力配列のサイズである.

1. 入力された配列dataにヒープを構成する.
2. 根の値とdata[n - 1]を入れ替えて、nをデクリメント.
3. 配列dataに対して再びヒープを構成する.

三番目の処理は、データの入れ替えによってヒープ構造が破壊されている場合も
考えなくてはならないので必要である.

また、ヒープソートはPriority Queue?を用いて実装することもできる.

Program1(Heap?クラスを用いて実装)

サイズnの配列dataに対してヒープソートを行う関数.

void heap_sort(int data[], int n) {
  Heap h;

  h.build_heap(data, n);

  for(int i = n - 1 ; i >= 1 ; i--) {
    h.swap_elem(0, i);
    h.decrement_size();
    h.heapify(0);
  }

  h.copy_array(data);
}

Program2(Priority Queue?クラスを用いて実装)

サイズnの配列dataに対してヒープソートを行う関数.

void heap_sort(int data[], int n) {
  PriorityQueue pq;

  for(int i = 0 ; i < n ; i++) {
    pq.insert(data[i]);
  }

  for(int i = n - 1 ; i >= 0 ; i--) {
    data[i] = pq.extract_max();
  }
}

Consideration