🚀 힙 정렬 구현하기

자바에서는 힙 정렬 알고리즘을 활용한 PriorityQueue 자료구조를 제공합니다
해당 자료구조를 사용하면 쉽게 정렬할 수 있지만,
힙 정렬의 원리를 더 깊이 이해하기 위해 직접 구현해보겠습니다

🛠️ 최대 힙 구조로 변환하기

원본 배열 [7, 3, 5, 2, 8, 1, 4, 6]을 오름차순 정렬하겠습니다
힙 정렬에서는 오름차순 정렬 시 최대 힙 구조를 사용합니다

다음은 최대 힙을 구성하는 자바 코드입니다

class HeapSort{  
  
    public static void heapSort(int[] arr){  
        if(arr.length < 2){  
            return;  
        }  
        int parent = ((arr.length-1)-1) / 2;  
  
        for (int i = parent; i >= 0; i--) {  
            heapify(arr, i, arr.length-1);  
        }  
  
    }  
  
  
    private static void heapify(int[] arr, int parent, int last){  
        int left = 2 * parent + 1;  
        int right = 2 * parent + 2;  
        int large = parent;  
  
        if(left <= last && arr[left] > arr[large]){  
            large = left;  
        }  
  
        if(right <= last && arr[right] > arr[large]){  
            large = right;  
        }  
  
        if(parent != large){  
            swap(arr, large, parent);  
            heapify(arr, large, last);  
        }  
  
    }  
  
  
    private static void swap(int[] arr, int a, int b){  
        int tmp = arr[a];  
        arr[a] = arr[b];  
        arr[b] = tmp;  
    }  
  
}

재귀적으로 호출되는 heapify() 메소드를 통해 최대 힙 구조로 배열이 재정렬됩니다

이 코드의 결과는 다음과 같습니다.

8 7 5 6 3 1 4 2 

🛠️ 최대 힙에서 오름차순으로 정렬하기

이제 최대 힙으로 구성된 배열을 최종적으로 오름차순 배열로 만드는 과정만 남았습니다
최대 힙에서 루트 노드를 하나씩 제거해며 배열의 끝부터 배치하는 방식으로 정렬을 수행합니다

아래 코드에서 루트와 배열의 마지막 요소를 서로 바꾸고, 힙의 크기를 하나씩 줄여가며 힙을 재구성합니다

public static void heapSort(int[] arr){  
  
    if(arr.length < 2){  
        return;  
    }  
    int parent = (arr.length-2) / 2;  
  
    for (int i = parent; i >= 0; i--) {  
        heapify(arr, i, arr.length-1);  
    }  
  
    for (int i = arr.length-1; i > 0; i--) {  
        swap(arr, 0, i);  
        heapify(arr, 0, i-1);  
    }  
  
}

여기서 추가된 반복문은 최대값을 배열의 끝에 하나씩 이동시키고,
나머지 요소를 계속해서 힙으로 재구성하여 전체 배열이 오름차순으로 정렬되도록 만듭니다

결과는 아래와 같습니다

1 2 3 4 5 6 7 8 

결과적으로 원본 배열이 오름차순으로 정렬된 것을 확인할 수 있습니다!

참고

• 힙 정렬 알고리즘 구현 참고