[알고리즘] 힙 정렬(heap sort)

힙은 '최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조'다.

 

힙정렬에 대해 설명하기 위해서는 트리에 대해서 설명이 필요하다.

 

트리란??

트리는 두 지점의 연결 관계로 구성되어 있는데, 계층관계가 존재한다는 것이 특징다. 우리는 하나의 연결 관계에서 위쪽에 있는 점을 부모라고 부르며, 아래쪽에 있는 점을 자식이라고 부를 것 입니다.

이 외에도 추가적인 용어들이 많은데, 아래쪽 사진을 참고하면서 용어를 이해해봅시다.

• 노드: 각 지점을 의미합니다.
• 루트 노드: 트리에서 맨 꼭데기를 의미합니다. 위쪽 조직도를 보면, 루트 노드는 회사 대표가 되겠죠?
• 부모, 자식: 트리에서 연결된 두 노드의 관계를 의미하는데, 더 위쪽에 있는 노드를 부모 노드, 아래쪽에 있는 노드를 자식 노드라고 부릅니다.
• 차수: 특정 노드를 기준으로, 자식의 수가 얼마나 되는지 의미합니다.
• 깊이: 루트 노드와 얼마나 떨어져 있는지를 가리키는 말입니다.
• 높이: 트리에서 깊이가 가장 깊은 노드의 깊이를 의미합니다.
• 리프 노드: 자식을 갖고 있지 않은 노드를 의미합니다.

트리

 

힙 정렬의 순서

• 정렬해야 할 n개의 데이터를 최대 힙또는 최소힙으로 구성
• 힙의 root노드에서 값을 순서대로 추출한다.
• root노드의 값을 heap을 구성하는 마지막 노드와 교환한뒤 힙의 크기를 1만큼 줄이는 방식

 

힙정렬은 말로하기는 너무 길고 좋은 영상이 있어 첨부한다.

 

---

내 코드

import java.util.*;

public class Main {

    static int n;
    static int[] arr;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }

        //(n-1) / 2 부터 0까지 heapify -> 자기 자신과 자식노드들중 최댓값을 자신의 위치로 이동
        for(int i = (n-1) / 2; i >= 0; i--){
            heapify(n, i);
        }

        //heapify작업이 종료된다면 제일 루트노드에는 최대값이 주어진다.
        //1. 루트노드의 값을 배열의 끝과 바꾼다.
        //2. 루트노드를 heapify한다. 
        //3. 1번으로 반복
        //4. 여기서 중요한점은 heapify의 첫번째 파라미터이다. heapify의 범위를 지정해줘야
        //   쓸데없이 돌지 않는다. 
        for(int i = n-1; i >= 0; i--){
            swap(0, i);
            heapify(i, 0);
        }

        for(int number : arr){
            System.out.print(number + " ");
        }
    }

    static void heapify(int n, int i){
        int largest = i;
        int left = (i * 2) + 1;
        int right = (i * 2) + 2;

        if(left < n && arr[left] > arr[largest]){
            largest = left;
        }

        if(right < n && arr[right] > arr[largest]){
            largest = right;
        }

        if(largest != i){
            swap(i, largest);
            heapify(n, largest);
        }
    }

    static void swap(int num1, int num2){
        int temp = arr[num1];
        arr[num1] = arr[num2];
        arr[num2] = temp;
    }
}

 

시간복잡도

힙생성(heapify) 알고리즘의 시간 복잡도는 O(logN)이다.

 

 

슬슬 정렬이 이해되어 가는것 같다. 하지만 계속 복습해야지.. 아마 이번글은 TBU..