[JS] 힙 정렬

 힙 정렬(Heap Sort)은 힙 생성 알고리즘를 이용하여 정렬하는 방법이다. 힙 생성 알고리즘은 특정한 노드의 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘이다. 또한 위치를 바꾼 후에도 자식이 존재하는 경우, 비교 연산을 수행하여 더 큰 자식과 자신의 위치를 바꾸어야한다. 따라서 최대 힙의 경우, 루트 노드의 원소는 가장 큰 수가 된다.

 

 

 힙 생성 알고리즘에 대해서는 이전에 포스팅한 적이 있다. 그래서 이번 포스팅에서는 따로 설명하지는 않겠다. 그런데 힙 생성 알고리즘의 시간 복잡도는 몇 일까? 정답은 

$$ O(nlog_{2}N) $$

이다. 왜냐하면 한 번 자식노드가 증가할 때마다 노드의 개수가 2배씩 증가하기 때문이다. 예를 들어 데이터가 1024개라면 대략 10번 정도만 내려가면 된다. 이제 간단한 예제를 들어서 힙 정렬의 과정을 설명해보도록 하겠다.

 

 

 다음과 같은 입력 배열 [6, 2, 3, 7, 1]을 예로 들어보겠다.

 

 

 이 입력배열을 트리 구조로 바꾸면 다음과 같다.

 

[그림 1] 트리 구조

 

 이제 트리구조화 시킨 입력배열을 힙 생성 알고리즘을 이용하여 최대 힙을 만들어 주도록 하자. 

 

[그림 2] 힙 생성 알고리즘 1회 적용

 

 만들어준 최대힙의 루트노드 값과 맨끝 노드 값을 비교한다. 만약 루트 노드 값이 맨 끝 노드 값 보다 크면 서로 값을 스와핑한다. 

 

[그림 2] 값 비교 후 스와핑

 

 그러면 자연스레 입력 배열의 맨 끝 인덱스에는 가장 큰 값인 7이 위치하게 된다. 여기서 중요한 점은 7은 이미 마지막 노드로 자리를 확정받은 상태라는 것이다. 따라서 다음 힙 생성알고리즘을 적용시킬 때 굳이 7을 비교할 필요가 없다. 그런 이유로 마지막 인덱스 값은 5가 아니라 1을 뺀 4가 된다. 이제 [1, 6, 3, 2, 7]이 아닌 [1, 6, 3, 2]에 힙 생성 알고리즘을 적용하여 최대힙을 구성해주자.

 

[그림 3] 최대 힙 구성(두 번째)

 

 루트노드 6을 마지막 노드 2와 값을 비교한다. 6이 2보다 크므로 서로 스와핑한다.

 

[그림 4] 값 스와핑

 

 그러면 6, 7은 자리 값이 확정되었으므로 다음 연산을 수행할 입력 배열의 길이는 3이 된다. 그러면 다음 힙 생성 알고리즘을 적용할 때는 는 두 번째 노드인 1부터 비교연산을 해야하는 것일까? 아니다. 비교연산을 하는 노드의 인덱스를 정하는 방식은 배열의 길이/2 연산이다. 따라서 그 다음 연산을 수행할 입력 배열의 길이는 3이고, 배열의 길이(3)에서 2를 나누면 몫이 1이되므로, 인덱스가 1인 노드, 즉 루트 노드와 자식노드들을 비교연산해주면 된다.

 

[그림 5] 세 번째 연산

 

 그리고 마지막 인덱스 노드와 루트 노드의 값을 비교하여 스와핑하면 된다. 

 

[그림 6] 세 번째 스와핑 

 

 다음 연산할 배열의 총 길이는 2가 되므로 자식 노드와 비교를 수행할 노드의 인덱스는 2/2 = 1 이므로 루트 노드가 된다. 그러면 [그림 6]과 같은 트리가 만들어 질 것이다. 2는 1보다 크므로 스와핑 연산을 수행한다. 그러면 다음 연산할 배열의 총 길이는 1이 된다. 1/0은 0이 된다.  이 때는 트리의 루트 노드 값과 마지막 노드 값을 비교한다. 1과 1은 같으므로 스와핑 작업을 할 필요가 없다. 따라서 다음과 같은 결과가 나오게 된다.

 

[그림 7] 최종 결과

 

 이를 프로그래밍 코드로 구현하면 다음과 같다.

let arr = [7, 6, 8, 9, 10, 1];

main();

function main(){
  arr = heapSort(arr);
  console.log(arr);
}

/* functions */

function heapSort(arr){
  for(let i=arr.length-1; i>=0; i--){
    arr = heapify(arr,i);

    if(arr[0] > arr[i]){
      let temp = arr[i];
      arr[i] = arr[0];
      arr[0] = temp;
    }
  }
  return arr;
}

function heapify(arr, lastIdx){
    let idx = parseInt(lastIdx/2)-1;

    while(idx >= 0){
    const left = arr[idx*2+1]; 
    const right = arr[idx*2+2];

    if(left >= right && arr[idx] < left){
      temp = arr[idx];
      arr[idx*2+1] = temp;
      arr[idx] = left;    
    }
    else if(right > left && arr[idx] < right){
      temp = arr[idx];
      arr[idx*2+2] = temp;
      arr[idx] = right;
    }
    idx--;
  }

  return arr;
}

 

참고자료

1. 동빈나님의 블로그 - 10. 힙 정렬(Heap Sort)