Heap Sort ( 힙 정렬 )

힙(Heap)

힙이란?

• 최댓값이나 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조
• heap 은 우선순위 큐를 위해서 만들어진 트리자료구조이다. 
• 힙에는 최소힙과 최대힙이 있음

heap의 특징

• heap은 완전이진트리의 형태이다. 완전이진트리 설명보러가기
• heap은 트리내에서 중복된 값을 허용한다.
• heap은 느슨한 정렬(반 정렬) 상태를 가진다. 

최소힙

작은 값을 항상 트리의 위에 있게 해서 트리의 루트에는 가장 작은 값이 오도록 함

 

최대힙

가장 큰 값이 맨 위에 오도록 함. 모든 노드는 자기 부모 노드가 자기보다 큰 값을 가지고 있음

 

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

 

정렬할 데이터들을 최대 힙으로 만듭니다.

최대 힙의 루트에 있는 가장 큰 값을 마지막 요소와 교환하여, 힙의 사이즈를 줄입니다.

최대 힙을 다시 구성합니다.

힙의 사이즈가 1보다 크면 위의 과정을 반복합니다.

 

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

 

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

 

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

자바스크립트 코드

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)O(nlogn)으로 빠른 편에 속합니다.
• 가장 큰 값을 구하거나 가장 작은 값을 구할 때 좋습니다.

단점

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

 

시간 복잡도

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