heapSort

heapSort.java

/**
* heap 정렬을 합니다. 
* @param arr
*/
void heapSort(int[] arr) {
  for (int i = (arr.length - 1) / 2 ; i >= 0; i--) 
    heapify(arr, i, arr.length); // 모든 내부 node를 index가 큰 node 부터 root node(arr[0])까지 히프화합니다. 
  // arr[0](root node)에는 최댓값이 들어가고 모든 서브트리가 heap 이됩니다. 
  for (int j = arr.length - 1; j > 0; j--) {
    swap(arr, 0, j); // 0번 원소와 j번 원소를 교환합니다.
    heapify(arr, 0, j); // [0,j) 구간을 히프화 합니다.
  }
}

/**
* 전달받은 node 번호와 자식 노드를 비교하여 히프화합니다. 
* @param arr
* @param nodeIndex 히프화할 node 의 번호입니다. 
* @param heapSize 완전 이진 트리의 크기입니다.  
*/
void heapify(int[] arr, int nodeIndex, int heapSize) { 
  int ai = arr[nodeIndex]; 
  while (nodeIndex < heapSize/2) { // arr[i] 는 leaf 가 아닌경우만 loop 를 순환합니다. 
    int j = 2 * nodeIndex + 1; // j는 ai의 좌측 자식 노드의 index 입니다. 
    if(j + 1 < heapSize && arr[j + 1] > arr[j]) ++j; // 우측 자식 노드의 값이 더 큰 경우 j를 후증가합니다. 
    if(arr[j] <= ai) break; // 부모가 자식노드보다 크면 loop 를 종료합니다. 
    arr[nodeIndex] = arr[j];
    nodeIndex = j;
  }
  arr[nodeIndex] = ai;
}