heapify

heapify.java

/**
* node의 childe 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;
}