image.png

  1. 부모노드 1개 자식노드 2개(총 3개) 비교한다.
  2. 최소힙을 만들어 가는 과정에서는 부모노드가 자식노드보다 작아야하기 때문에 가장 작은 자식 노드를 부모노드와 자리를 바꾼다.
  3. 바꾸어진 부모노드는 아래 노드와도 비교를 해야하기 때문에 재귀적으로 heapify를 수행한다.

최소힙으로 힙구성(Heapify)

 만약에 아래와 같은 배열이 있다고 하면,
 int[] arr = {7,6,5,8,3,5,9,1,6};
          7
      6       5
    8   3   5   9
  1   6   
-->가장 최상단의 노드가 7로 이미 자식노드 보다 크다. 이것을 최초힙구성해보자. 
이때 최소힙 구조로 Heapify(힙구성) 해본다.

-->그런데, 주목해야할 특징이 하나 있다. 가장 상단에 있는 7번 노드가 0번 인덱스인데,
힙에서 왼쪽 자식 노드의 인덱스는 부모 노드 인덱스에 2를 곱한다음 +1을 한 것과 같다.
오른쪽 자식 노드의 인덱스는 부모 노드 인덱스에 2를 곱한다음+2를 한 것과 같다.

----------------------------------------------------------------------------

static void heapify(int[] arr, int parent){
  int left = parent *2 +1;  //매개변수로 받은 부모 노드 인덱스로부터 *2+1은 왼쪽 자식노드 인덱스
  int right = parent*2 +2;  //*2+2는 오른쪽 자식노드의 인덱스
  
 if(left>=arr.length)return; // 1번
 if(right>=arr.length){ //2번
   if(arr[parent] > arr[left]){
      int temp = arr[parent];
      arr[parent] = arr[left];
		  arr[left] = temp;
		  heapify(arr,left)
} else{ //3번
  int minIndex =0;
  if(arr[parent]>arr[left] || arr[parent]>arr[right]){
        if(arr[left] > arr[right]){
          minIndex = right
          } else { minIndex =left;
          }
         int temp = arr[parent];
         arr[parent]=arr[minIndex];
         arr[minIndex]=temp;
         heapify(arr,minIndex);
         }
-1번
: parent*2+1한 값이 최소한, 노드를 담은 배열의 길이와 같다면(배열의 길이는 마지막 인덱스+1이니까) 존재하는 인덱스를 초과했다는 것이고,
그 말으더 이상 노드가 없다는 뜻이다.값이 있다면 노드는 왼쪽부터 채워지니까.

-2번
:paretn*2+2한 값이 배열의 길이와 같다면 사실상 오른쪽 자식노드는 없다는 것임. 
다만 왼쪽 노드는 있을 수도 있고 없을 수도 있음. 그런데 없다는 것은 위의 조건문으로 빠져나가니 
해당 2번 조건은 left가 있을때의 조건이 됨.
이 때! 최소힙 구조에서는 부모노드가 자식노드보다 작거나 같아야하므로 만약 부모노드가 자식노드인
left보다 크다면 자리를 바꾸어야한다. 그리고 자식노드로 이동한 원래의 부모노드를 기준으로 다시 
아래에 위치한 자식노드들과 또 비교해나감으로써(여기서 재귀호출이 필요한 것!) 전체적인 최소힙 구성이 되는 것이다.

-3번
:else의 조건에는 left가 arr.length보다 작거나 right가 arr.length보다 작다는 것으로 즉 존재하는 인덱스라는 뜻임.
따라서, 부모노드가 자식노드 보다 크다면 왼쪽 자식노드와 오른쪽 자식노드 둘 중 작은 값이 부모노드와
바뀌면 된다. 이때 왼쪽이든 오른쪽이든 제일 작은 값을 가질 인덱스를 0으로 초기화해두고,
그 인덱스에 해당하는 값을 부모노드와 바꾼다음 자식노드로 이동된 기존의 부모노드를 
또 다시 아래 자식노드들과 비교해나감으로써 전체적인 최소힙구조를 갖추어야하므로 재귀호출이 필요하다.

-------------------------------------------------------------
이제 구현된 heapify메서드를 통해 
int[]arr = {7,6,5,8,3,5,9,1,6}을 힙구성해보자면

for(int i=(arr.lengh/2)-1 ; i>=0 ; i--){
     heapify(arr,i)
}

-->여기서 힙구성은 왜 i=(arr.length/2 -1)에서 부터 진행될까?
heapify는 부모노드와 자식노드를 비교하는 것이다. 
즉 자식노드가 없는 노드는 메서드를 적용할 필요가 없다.
그런데 완전이진트리의 특성상 마지막 부모노드는 arr.lengh/2 -1이다.
즉 마지막 부모노드의 인덱스부터 1씩 빼가면서 제일 마지막에는 root노드까지 heapify를 해나가는 것!

2.최대힙으로 힙구성(Heapify)

앞서 진행한 최소힙으로 heapify한 작업이 부모노드와 자식노드를 비교해서
자식노드가 부모노드보다 더 작은 값을 가지고 있다면 부모와 자식의 값을 교체해나가는 과정이다.
최대힙은 똑같은 로직에서 자식노드가 부모노드보다 더 큰 값을 가지고 있다면 부모와 자식의 값을
교체해나면 되니까 위의 코드에서 비교할 때의 부등호만 바꾸면 되는 것이다

-------------------------------------------------------------------------------

static void heapify(int[] arr, int parent){
  int left = parent *2 +1;  //매개변수로 받은 부모 노드 인덱스로부터 *2+1은 왼쪽 자식노드 인덱스
  int right = parent*2 +2;  //*2+2는 오른쪽 자식노드의 인덱스
  
 if(left>=arr.length)return; // 1번
 if(right>=arr.length){ //2번
   if(arr[parent] < arr[left]){
      int temp = arr[parent];
      arr[parent] = arr[left];
		  arr[left] = temp;
		  heapify(arr,left)
} else{ //3번
  int maxIndex =0;
  if(arr[parent]<arr[left] || arr[parent]<arr[right]){
        if(arr[left] > arr[right]){
          maxIndex = left
          } else { minIndex =right;
          }
         int temp = arr[parent];
         arr[parent]=arr[maxIndex];
         arr[maxIndex]=temp;
         heapify(arr,maxIndex);
         }

힙 정렬