[정렬 알고리즘] 힙 정렬

 

2021.08.23 - [자료구조 & 알고리즘] - [알고리즘] 정렬

 

📎 힙 정렬

힙 정렬은 힙(heap)을 사용해 정렬하는 선택 정렬 응용 알고리즘이다.

 

 

힙 Heap 

힙이란 차곡차곡 쌓아올린 더미라는 뜻으로 완전이진트리 구조를 가진다.

 

 

나무위키 - 힙트리

 

 

완전 이진 트리 형태는 부모 노드 밑에 자식노드가 2개 이하로 제한된 구조로 가장 기본적이고 간단한 트리 형태를 말한다.

 

 

힙의 특성

• 최대힙 Max Heap : 부모 노드 값은 항상 자식 노드 값보다 크다 (=Root 노드 값이 가장 크다)
• 최소힙 Min Heap : 자식 노드 값은 항상 부모 노드 값보다 크다 (=Root 노드 값이 가장 작다)

 

기본적으로 힙정렬은 최대힙의 특성을 가지고 정렬을 구현한다.

 

 

힙의 배열 저장은 위의 사진 2)를 참고해서 보면 쉽다.

 

 

부모는 Arr[ (i-1) / 2 ]
왼쪽 자식은 Arr[ 2i +1 ]
오른쪽 자식은 Arr[ 2i +2 ]

 

위의 사진을 참고해서 본다면

부모 10의 위치는 Arr[3]이고 그 밑의 자식들은

Arr[6] = 9 / Arr[7] = 3 이 되는 걸 볼 수 있다.

 

 

힙 정렬은 이 배열 저장, 노드의 높이 등을 가지고 정렬을 한다.

 

 

힙정렬의 과정

1. 입력받은 배열을 최대힙 구조로 구성 Build Max-heap 
2. 루트 제거하고 마지막 요소를 루트로 옮김 Extract-Max
3. <1~2> 반복

 

 

 

자바 코드로 구현하면 이렇다.

 

 

import java.util.Scanner;
 
public class HeapSort {
    /*
     * 힙 정렬 : 힙 정렬은 힙(heap)을 사용해 정렬하는 선택 정렬 응용 알고리즘
     * 최대 힙 특성 Max-heap : 루트 노드 값이  가장 큼
     * 일반적인 힙 정렬의 시간 복잡도는 O(n log n)
     * 
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("정렬할 요소의 수: ");
    
        int n = sc.nextInt();
        
        int[] arr = new int[n];
        
        //요소 입력받음
        for(int i=0; i<n; i++) {
            arr[i]=sc.nextInt();
        }
        
        heapSort(arr, n);
                
        System.out.println("정렬 완료");
        
        //정렬 후 출력
        for(int i=0; i<n; i++) {
            System.out.print(arr[i]+" ");
        }
    }
    
    static void heapSort(int[] arr, int n) {
        //힙구조로 구성 (Build Max-heap) 
        heapify(arr, n);
        
        //루트 제거하고 마지막 요소를 루트로 옮김 (Extract-Max)
        for(int i=n-1; i>=0; i--) {
            swap(arr, 0, i);
            
            heapify(arr, i);
        }
        
    }
    
    //Build Max-heap 
    static void heapify(int[] arr, int last) {    //last변수는 가장 마지막 인덱스를 뜻함
        for(int i=1; i<last; i++) {
            int child = i;
            
            while(child>0) {    
                int parent = (child - 1)/2;
                
                if(arr[child] > arr[parent]) {     //부모와 비교해서 자식이 클경우엔
                    swap(arr, child, parent);    //swap
                }
                child = parent;        
            }
        }
    }
    
    //배열의 요소 두개의 위치를 바꿈 
    static void swap(int[] arr, int idx1, int idx2) {
        int tmp = arr[idx1];
        arr[idx1]=arr[idx2];    //idx1 : idx1 -> idx2
        arr[idx2]=tmp;            //idx2 : idx2 -> idx1
    }
}
 

 

힙 정렬의 성능 분석

힙 정렬의 과정 중 Build Max-heap 을 수행하는 시간은 O(nlgn)이다.

Extra-Max 는 n-1번 반복한다.

 

총 힙 정렬의 전체 수행시간은 O(nlgn)이 된다. 최악이든 최선이든 항상 O(nlgn)이 된다.

 

 

+

T아카데미 | 스마트 ICT 전문가 양성 (skplanet.com)

컴퓨터 알고리즘 초급 | T아카데미 온라인강의