ヒープソート

ヒープソート

■コード

view plainprint?

1. int heapSize;  
2.  int parent(int i){ return (i-1)/2; }  
3.  int left(int i){ return i*2+1; }  
4.  int right(int i){ return i*2+2; }  
5.  void swap(int[] a, int i, int j){  
6.   int t=a[i]; a[i]=a[j]; a[j]=t;  
7.  }  
8.    
9.  /** 
10.   * iを根とする2分木がヒープとなるように，a[i]をヒープの中に“滑り落とす” 
11.   * 但し，left(i)，right(i)を根とする2分木がそれぞれヒープであるとする 
12.   */  
13.  void heapify(int[] a, int i){  
14.   int left=left(i);  
15.   int right=right(i);  
16.   int largest=i;  
17.   if(left<heapSize && a[left]>a[largest])  
18.    largest=left;  
19.   if(right<heapSize && a[right]>a[largest])  
20.    largest=right;  
21.   if(largest!=i){  
22.    swap(a, i, largest);  
23.    heapify(a, largest);  
24.   }  
25.  }  
26.    
27.  /** ヒープを構築 */  
28.  void buildHeap(int[] a){  
29.   for(int i=(a.length-1)/2; i>=0; i--)  
30.    heapify(a, i);  
31.  }  
32.    
33.  /** Heap sort(ヒープソート) */  
34.  public void heapSort(int[] a){  
35.   heapSize=a.length;  
36.   buildHeap(a);  
37.   for(int i=a.length-1;i>=1;i--){  
38.    swap(a, 0, i);  
39.    heapSize--;  
40.    heapify(a, 0);  
41.   }  
42.  }  

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