Skip to content

Instantly share code, notes, and snippets.

@keehyun2
Created January 28, 2018 04:09
Show Gist options
  • Save keehyun2/350c29b439832e8cda6374afb47f72ff to your computer and use it in GitHub Desktop.
Save keehyun2/350c29b439832e8cda6374afb47f72ff to your computer and use it in GitHub Desktop.
heapify
/**
* 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment