ヒープソート

ヒープソート

■コード

int heapSize;
 int parent(int i){ return (i-1)/2; }
 int left(int i){ return i*2+1; }
 int right(int i){ return i*2+2; }
 void swap(int[] a, int i, int j){
  int t=a[i]; a[i]=a[j]; a[j]=t;
 }
 
 /**
  * iを根とする2分木がヒープとなるように，a[i]をヒープの中に“滑り落とす”
  * 但し，left(i)，right(i)を根とする2分木がそれぞれヒープであるとする
  */
 void heapify(int[] a, int i){
  int left=left(i);
  int right=right(i);
  int largest=i;
  if(left<heapSize && a[left]>a[largest])
   largest=left;
  if(right<heapSize && a[right]>a[largest])
   largest=right;
  if(largest!=i){
   swap(a, i, largest);
   heapify(a, largest);
  }
 }
 
 /** ヒープを構築 */
 void buildHeap(int[] a){
  for(int i=(a.length-1)/2; i>=0; i--)
   heapify(a, i);
 }
 
 /** Heap sort(ヒープソート) */
 public void heapSort(int[] a){
  heapSize=a.length;
  buildHeap(a);
  for(int i=a.length-1;i>=1;i--){
   swap(a, 0, i);
   heapSize--;
   heapify(a, 0);
  }
 }

■特徴
・ヒープ構造を用いる
・最悪計算量O(nlogn)
・データによる計算量の変化が小さい