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

힙 정렬 (Heap Sort)

---

▶힙 정렬은 힙 자료구조를 기반으로 원소들을 정렬하는 방식을 의미합니다. 힙에 대한 기본 지식은http://lktprogrammer.tistory.com/69 에서 확인 할 수 있습니다.

 

■ 정렬 과정

---

▶ 이번 게시글에서는 최대힙을 기준으로 설명을 하겠습니다. 힙의 기본은 완전 이진 트리의 형태이면서 부모 노드가 자식 노드보다 큰 값을 가지는 힙 성질을 만족하는 트리를 의미합니다. 따라서 최상위 노드인 루트 노드는 전체 원소 중에서 항상 최대값을 가지게 됩니다.

 

1. 배열에 저장 된 원소들을 최대힙으로 구성

2. 루트 노드에 존재하는 값을 가지고 오고, 가장 말단에 있는 노드를 루트 노드에 위치 시킵니다. 새로 자리 잡은 루트 노드에 대하여 다시 힙 성질에 맞게끔 배열을 조정합니다. (DownHeap 과정)

3. 배열에 남아 있는 원소가 없을때까지 2번 과정을 반복합니다.

 

▶ 다음과 같은 배열 {1,2,3,4,5}에 대하여 반대로 내림차순으로 정렬하는 과정을 살펴 보겠습니다. 먼저 특정 인덱스 i에 대한 왼쪽 자식 노드의 인덱스는 i*2+1에 해당되며 오른쪽 자식 노드는 i*2+2에 해당 됩니다. (인덱스가 0에서부터 시작하는 경우)

▶먼저 현재 트리의 경우는 힙이 아닙니다. 먼저 최대힙 성질을 만족하도록 트리를 조정해야 합니다. 가장 말단 노드부터 시작하여 특정 노드가 루트노드가 되는 서브 트리가 힙성질을 만족하게 되면 최종적으로 전체 트리가 힙 성질을 만족 할 수 있습니다. 실제로는 가장 말단에 있는 5부터 시작하여야 하지만 5의 경우에는 리프 노드로 자식 노드가 존재하지 않습니다. 즉 자식 노드를 가지고 있는 레벨의 노드부터 시작을 하면 됩니다. 자식 노드를 가지는 레벨의 시작 인덱스는 전체 노드의 개수/2가 되고 위 그림에서는 5/2=2인 2번 인덱스인 3부터 시작을 합니다.

 

 

▶3을 루트노드로하여 힙 성질을 만족하도록 바꿉니다. 그런데 3은 자식 노드가 없으므로 힙 성질을 만족한다고 생각하고 넘어갑니다.

▶다음은 2를 루트 노드로 하는 서브 트리를 힙으로 만드는 과정입니다. 자식 노드인 4와 5중에서 큰 값인 5와 2를 비교를 합니다. 5과 더 크므로 2와 5를 자리를 바꿉니다. 그리고 위치가 바뀐 노드를 루트 노드로 하는 서브 트리를 힙으로 조정 할려고 하니 자식 노드가 존재하지 않습니다.

 

▶마지막으로 1에 대하여 힙 성질을 만족하도록 조정합니다. 두 자식 노드 중 큰 값 5과 1보다 크므로 두 위치를 교환합니다.

▶마지막으로 위치가 바뀐 노드를 루트 노드로 하는 서브트리를 최대힙을 만족하도록 조정합니다. 최상위 노드인 1은 두 자식 노드중 큰 값 4보다 작으므로 둘의 위치를 교환합니다. 바뀐 노드 1를 루트 노드로 하는 서브 트리를 힙 성질이 만족하다록 조정할려고 하니 자식 노드가 존재하지 않으므로 여기까지 합니다.

 

여기까지 완료가 되었다면 힙이 완성 됩니다. 이제 실제로 DownHeap 과정을 반복하면서 정렬된 데이터 값을 가지고 오는 부분을 살펴 보겠습니다.

▶루트 노드의 값 5를 가지고 오고 가장 말단에 있는 노드 2를 루트 노드에 위치 시킵니다. 그런 다음 다시 루트노드에 대하여 최대 힙 성질을 만족하도록 배열을 조정합니다. 4과 2보다 크므로 둘의 위치를 교환합니다. 그런 다음바뀐 위치의 노드2에 대하여 최대 힙 성질을 만족하도록 조정합니다. 2가 1보다 크므로 그대로 두게 됩니다.

 

이런식으로 힙에서 루트 노드를 가지고 오고 말단 노드를 루트 노드에 위치 시키고 최대힙을 구성하는 것을 반복함으로써 힙 정렬을 시도하게 됩니다.

 

■ 힙 정렬 구현

---

public class Heap {
    private int Heap_Size;
    private int data[];
    
    public Heap(int[] data,int Heap_Size)    //정렬하고자 하는 배열과 크기를 저장합니다.
    {
        this.Heap_Size = Heap_Size;
        this.data = data;
    }
    public void Heap_Sort()                    
    {
        for(int i=Heap_Size/2;i>=0;i--)        //최초 배열을 최대힙으로 구성합니다.전체 원소의 
        {
            Max_Heapfiy(i);
        }
        for(int i=0;i<data.length;i++)        //DownHeap을 반복하며 정렬된 결과를 출력합니다.
        {
            System.out.println(DownHeap());
        }
    }
    public void Max_Heapfiy(int i)
    {
        int left_node= i*2+1;            //왼쪽 자식 노드의 인덱스
        int right_node = i*2+2;            //오른쪽 자식 노드의 인덱스
        int Max;                        //부모 노드와 자식 노드중 큰 값을 가지는 노드의 인덱스
        if(left_node < Heap_Size)        //왼쪽 자식 노드가 존재하는 경우
        {
            if(data[left_node]>data[i])    //왼쪽 자식 노드가 부모 노드보다 큰 경우
            {
                Max = left_node;
            }
            else                        //왼쪽 자식 노드가 부모 노드보다 작은 경우
            {
                Max = i;
            }
        }
        else                            //왼쪽 자식 노드가 없으면 return
        {
            return;
        }
        if(right_node < Heap_Size)        //오른쪽 자식 노드가 있는 경우
        {
            if(data[right_node]>data[Max])    //오른쪽 자식 노드가 왼쪽 자식 노드와 부모 노드보다 큰 경우
            {
                Max = right_node;
            }
        }
        if(Max != i)                    //기존 부모노드보다 큰 값이 자식 노드에 있는 경우
        {
            Swap(Max,i);
            Max_Heapfiy(Max);
        }
    }
    public int DownHeap()                
    {
        int max = data[0];                //루트 노드를 저장
        data[0] = data[--Heap_Size];    //말단 노드를 루트 노드에 위치 시키고 힙의 크기를 --
        Max_Heapfiy(0);                    //루트 노드에 대한 최대힙화
        return max;                        
    }
    public void Swap(int Max,int i)
    {
        int tmp = data[Max];
        data[Max] = data[i];
        data[i] = tmp;
    }
}

 

출처 : https://lktprogrammer.tistory.com/70?category=672214