힙 정렬 (Heap Sort)

힙 정렬 (Heap Sort)

완전 이진 트리를 기본으로 하는 힙 자료구조를 기반으로한 정렬 방식

• 힙 정렬은 병합 정렬과 퀵 정렬만큼 빠른 정렬 알고리즘이다.
• 힙은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리다.
• 힙에는 최대 힙과 최소 힙이 존재하는데 최대 힙은 부모 노드가 자식 노드보다 큰 힙이라고 할 수 있다.
• 힙정렬을 하기 위해서는 정해진 데이터를 힙 구조를 가지도록 만들어야 한다.
• 힙 정렬을 수행하기 위해서는 힙 생성 알고리즘 (Heapify Algorithm)을 사용한다.
• 힙 생성 알고리즘은 특정한 하나의 노드에 대해서 수행하는 것이다.
• 힙 생성 알고리즘은 특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘이다.
• 힙 정렬은 병합 정렬과 다르게 별도로 추가적인 배열이 필요하지 않다는 점에서 메모리 측면에서 효율적이다.
• 완전 이진 트리인 힙의 높이는 O(log N)이다. 데이터 하나를 힙에 삽입, 삭제하는 과정에서 힙을 재구성하는 시간은 O(log N이 소요된다. 이에 요소개수 n개를 곱하면 전체 O(Nlog N)의 시간 복잡도를 가진다.
• 가장 큰값을 구하거나 가장 작은 값을 구할 때 좋다.
• 실제 프로그램에 구현할 경우 평균 계산 속도가 퀵 정렬보다 느리고 불안정하다.   

 

입력 배열

6

2

3

7

1

 

 

트리 구조

 

 

 

 

 

 

 

 

 

최대 힙 만들어주기 위해 힙 생성 알고리즘 1회 적용 
만들어준 최대힙의 루트 노드 값과 맨 끝 노드 값을 비교한다.
루트 노드가 잎사귀 노드보다 크면 값을 스와핑한다.

맨 끝 노드 값은 가장 큰 값인 7이 위치한다.
7은 마지막 노드로 확정 받아서 다음에 7을 비교할 필요없다.
[1,6,3,2]에 힙 생성 알고리즘을 적용하여 최대힙을 구성한다. 

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

마지막 인덱스 노드와 루트 노드의 값을 비교하여 스와핑한다.

트리 루트 노드 값과 마지막 노드 값을 비교한다.

코드로 구현

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;
}

 

참고자료

https://m.blog.naver.com/ndb796/221228342808

10. 힙 정렬(Heap Sort)

https://taesung1993.tistory.com/26