[알고리즘] JAVA 힙 정렬 (Heap Sort) 알고리즘

  

 

힙 정렬은 병합 정렬과 퀵 정렬만큼 빠른 정렬 알고리즘

- 힙 트리 구조(Heap Tree Structure)를 이용하는 정렬 방법

 

힙 정렬을 알기 전에 이진 트리에(Binary Tree)에 대해 알고 있어야 한다.

이진 트리

- 컴퓨터 안에서 데이터를 표현할 때 데이터를 각 노드에 담은 뒤에 노드를 두 개씩 이어 붙이는 구조

- 모든 노드의 자식 노드가 2개 이하인 트리 구조

 

 

완전 이진 트리(Complete Binary Tree)

- 데이터가 루트 노드부터 시작해서 자식 노드가 왼쪽 자식 노드, 오른쪽 자식 노드로 차근차근 들어가는 구조의 이진 트리이다. 즉, 완전 이진 트리는 이진 트리의 노드가 중간에 비어있지 않고 빽빽히 가득 찬 구조의 이진 트리이다.

 

힙

힙(Heap)은 최솟값이나 최대값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리이다. 힙에는 최대 힙과 최소 힙이 존재하는데 최대 힙은 '부모 노드'가 '자식 노드'보다 큰 힘이라고 할 수 있다. 일단 힙 정렬을 하기 위해서는 정해진 데이터를 힙 구조를 가지도록 만들어야 한다.

힙 정렬을 수행하기 위해서는 힙 생성 알고리즘(Heapify Algorithm) 을 사용한다. 힙 생성 알고리즘은 특정한 '하나의 노드'에 대해서 수행하는 것이다. 특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘이다.

 

힙 생성 알고리즘의 시간 복잡도 → O(log N)

 

문제

- 7, 6, 5, 8, 3, 5, 9, 1, 6을 오름차순으로 정렬하시오.

 

소스 코드

package com.company;

public class Main<i> {

    private static int number = 9;
    private static int[] heap = {7, 6, 5, 8, 3, 5, 9, 1, 6};

    public static void main(String[] args) {
        // 먼저 전체 구조를 최대 힙구조로 바꾼다.
        for(int i=1; i<number; i++) {
            int c = i;
            do {
                int root = (c-1)/2;
                if(heap[root] < heap[c]) {
                    int temp = heap[c];
                    heap[c] = heap[root];
                    heap[root] = temp;
                }
                c = root;
            }while (c != 0);
        }
        // 크기를 줄여가며 반복적으로 힙을 구성
        for(int i = number - 1; i >= 0; i--) {
            int temp = heap[0];
            heap[0] = heap[i];
            heap[i] = temp;
            int root = 0;
            int c = 1;
            do {
                c = 2 * root + 1;
                // 자식 중에 더 큰 값 찾기
                try {
                    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;
                    }
                } catch (Exception e) {
                    e.printStackTrace();
                }
                root = c;
            } while(c<i);
        }
        for(int i=0; i<number; i++) {
            System.out.print(heap[i] + " ");
        }
    }


}

 

출력 결과