힙 정렬 (Heap Sort)

힙 정렬

자료구조인 힙을 이용하여 정렬을 수행하는 방법입니다. 그렇다면 힙이 무엇일까요?

 

힙 (Heap)

힙은 완전 이진 트리이며 최소 힙과 최대 힙이 있습니다. 여기서 완전 이진 트리나 힙에 대해서 더 설명하지는 않겠습니다. 힙에 대해서 잘 모르시는 분께서는 공부를하고 다시 보시는 것을 추천드립니다. : )

 

힙 정렬을 다시 말하자면, 최소 힙이나 최대 힙을 이용하여 정렬하는 방법입니다. 내림차순 정렬을 위해서는 최대 힙을 사용하고, 오름차순 정렬을 위해서는 최소 힙을 사용합니다.

 

힙 정렬의 과정은 다음과 같습니다. (설명을 위해 내림차순 정렬을 예시로 보여드리겠습니다.)

1. 정렬할 데이터들을 최대 힙으로 만듭니다.
2. 최대 힙의 루트에 있는 가장 큰 값을 마지막 요소와 교환하여, 힙의 사이즈를 줄입니다.
3. 최대 힙을 다시 구성합니다.
4. 힙의 사이즈가 1보다 크면 위의 과정을 반복합니다.

 

1) 최댓값인 루트의 9를 삭제 후, 마지막 노드를 가져옵니다.

 

2) 루트로 삽입된 노드와 자식 노드와 비교하여 큰 값과 교환합니다.

 

3) 최대 힙이 아니라면 다시 자식 노드와 비교하여 교환해줍니다. 위의 과정을 반복합니다.

 

시간 복잡도

완전 이진 트리인 힙의 높이는 $O(logn)$입니다. 데이터 하나를 힙에 삽입, 삭제하는 과정에서 힙을 재구성하는 시간은 $O(logn)$가 소요됩니다. 이에 요소개수 n개를 곱하면 전체 $O(nlogn)$의 시간 복잡도를 가집니다.

 

자바스크립트 코드

let arrLen;

function swap(arr, i, j){
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

function heapify(arr, i){
  let max = i;
  let left = 2 * i + 1;
  let right = 2 * i + 2;
  
  if(left < arrLen && arr[left] > arr[max]){
    max = left;
  }
  
  if(right < arrLen && arr[right] > arr[max]){
    max = right;
  }
  
  if(max != i){
    swap(arr, i, max);
    heapify(arr, max);
  }
}

function heapSort(arr){
  arrLen = arr.length;

  for(let i = Math.floor(arrLen / 2); i >= 0; i--){
    heapify(arr, i);
  }
  
  for(let i = arrLen - 1; i > 0; i--){
    swap(arr, 0, i);
    arrLen--;
    
    heapify(arr, 0);
  }
  
  return arr;
}

console.log(heapSort([13, 1, 3, 7, 9, 11, 5]));

 

장점

• 시간 복잡도가 $O(nlogn)$으로 빠른 편에 속합니다.
• 가장 큰 값을 구하거나 가장 작은 값을 구할 때 좋습니다.

단점

• 실제 프로그램에 구현할 경우 평균 계산 속도가 퀵 정렬보다 느리고 불안정합니다.

 

정리

힙 정렬은 이름에도 힙이 드러가는 만큼 자료구조 힙을 사용하여 정렬을 수행합니다. 이는 힙에 대한 지식이 없으면 이해하기 힘드니 공부하고 오시는 것을 추천드립니다. 만약 힙에 대해 알고있다면, 어려운 내용은 아닐 것입니다. : >