알고리즘...20

힙 정렬

루트에 항상 가장 큰 값(혹은 가장 작은 값)이 오도록 정렬되는 힙을 사용하는 정렬 방식이다.

 

힙 만들기

입력되는 배열을 완전 이진트리로 가정하여 힙을 생성한다.

 

힙 생성 알고리즘

BuildHeap(A[], n)
{
    for i ← └n / 2┘ downto 1
    {
        Heapify(A, i, n);
    }
}

Heapfipy(A[], k, n)
{
    left ← 2k; right ← 2k + 1;
    // 작은 자식 고르기
    if (right ≤ n) then
    {
        if (A[left] < A[right]) then
        {
            smaller ← left;
        }
        else
        {
            smaller ← right;
        }
    }
    // 왼쪽 자식만 있는 경우
    else if (left ≤ n) then
    {
        smaller ← left;
    }
    // 자식이 없는 경우, 종료
    else
    {
        return;
    }
    if (A[smaller] < A[k]) then
    {
        A[k] ↔ A[smaller];
        Heapify(A, smaller, n);
    }
}

 

힙 정렬 알고리즘

힙을 만들어 데이터를 모두 삽입한 뒤 루트에서 하나씩 인출하여 순서대로 배열에 넣어준다.

 

힙 정렬 알고리즘

HeapSort(A, n)
{
    BuildHeap(A, n);
    for i ← n downto 2
    {
        A[1] ↔ A[i];
        힙 A가 힙 상태를 만족하도록 다시 정렬한다.
    }
}

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘