기본 정렬 알고리즘 - 힙정렬(Heap Sort)

힙 정렬(Heap Sort)의 특징

• 힙 정렬의 핵심 아이디어는 힙 트리 구조를 사용하여 정렬한다.

• 시간 복잡도 O(N * logN)

• 사전 지식

  • 이진트리(Binary Tree): 모든 노드의 자식 노드가 2개 이하인 트리

  • 완전 이진트리: 데이터가 루트노드부터 시작해서 자식 노드까지 왼쪽부터 오른쪽으로 차례차례 들어가 있는 형태의 트리

  • 힙(Heap): 최소값이나 최댓값을 빠르게 찾아내기 위해서 완전 이진트리를 기반으로 하는 구조를 말한다.

 

코드

아래 코드는 상향식 구현 방식을 사용하였습니다. 하양식으로 구현하여도 무방합니다.

function solution(heap)
{
    let length = heap.length;
    let temp = 0;

    /**
     * 먼저 전체 트리구조를 최대 힙 구조로 바꾼다.
     * 즉, 모든 노드를 하나씩 돌면서 힙 구조로 변경
     */
    for (let i = 1; i < length; i++)
    {
        let c = i;
        do {
            // 부모 찾기
            let root = parseInt((c - 1) / 2);

            if (heap[root] < heap[c])
            {
                temp = heap[c];
                heap[c] = heap[root];
                heap[root] = temp;
            }
            // 자식에서 부모로 올라가면서 반복적으로 수행되도록 처리
            c = root;   
        } while (c !== 0); // root에 도달할때까지 반복
    }
    console.log('최대 힙 생성: ' + heap);

    // 크기를 줄여가면서 반복적으로 힙을 구성
    for (let i = length - 1; i >= 0; i--)
    {
        // 가장 큰 값을 배열 맨 뒤로 보내기
        temp = heap[0];
        heap[0] = heap[i];
        heap[i] = temp;

        // 맨 마지막 요소를 제외하고 반복하면서 힙 정렬
        let root = 0;
        let c = 1;
        do {
            // c는 root의 자식이 된다.
            c = 2 * root + 1;

            // 자식 중에 더 큰 값을 찾기
            if (heap[c] < heap[c + 1] && c < i - 1) // 범위 잡기
            {
                c++;
            }
            // 루트보다 자식이 더 크다면 교환
            if (heap[root] < heap[c] && c < i)
            {
                temp = heap[root];
                heap[root] = heap[c];
                heap[c] = temp;
            }
            root = c;

        } while (c < i);
    }

    return heap;
}

console.log(solution([7, 6, 5, 8, 3, 5, 9, 1]));

 

 

참조

https://www.youtube.com/watch?v=iyl9bfp_8ag&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=11