2010年6月13日日曜日

ヒープソート

ヒープソート

■コード
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)
・データによる計算量の変化が小さい

0 件のコメント: