1. 개념

• 힙 자료구조의 장점을 활용한 정렬
  • 최대 힙(heap)
    • 완전 이진 트리 : 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리
    • 각 노드의 값은 자신의 자식 노드의 값보다 크거나 같음
  • 임의의 값 삽입과 최댓값 삭제가 용이

2. 과정

1. 일반 배열을 최대 힙으로 구성한다.
2. 루트의 값을 마지막 요소와 교환한 후, 힙의 사이즈를 하나 줄인다.
   (정렬과정에서 최대값을 고려하지 않게 하기 위함)
3. 힙의 사이즈가 1보다 클 경우 위의 과정을 반복한다.

3. 구현

/* n: 배열의 길이 */

public class HeapSort {
	
	static void swap(int[] arr, int idx1, int idx2) {
		int temp = arr[idx1];
		arr[idx1] = arr[idx2];
		arr[idx2] = temp;
	}
	
	/**
	 * 배열을 힙으로 변환
	 * */
	static void downHeap(int[] arr, int n, int selectedIdx) {
		int parentNode = selectedIdx;
		int leftChildNode = parentNode*2 + 1;
		int rightChildNode = parentNode*2 + 2;
		
		// 1-1. 왼쪽 자식노드
		if(leftChildNode < n && arr[parentNode] < arr[leftChildNode]) {
			parentNode = leftChildNode;
		}
		
		// 1-2. 오른쪽 자식노드
		if(rightChildNode < n && arr[parentNode] < arr[rightChildNode]) {
			parentNode = rightChildNode;
		}
		
		// 1-3. 부모노드 < 자식노드
		if(selectedIdx != parentNode) {
			swap(arr, parentNode, selectedIdx);	// 자식노드와 부모노드의 값 교환
			downHeap(arr, n, parentNode);
		}
	}
	
	/**
	 * 힙 정렬
	 * */
	static void heapSort(int[] arr, int n) {
		// 1. 배열을 최대 힙으로 구성
		for(int i = n/2 - 1; i >= 0; i--) {
			downHeap(arr, n, i);
		}
		
		// 2. 루트값 추출 및 최대힙 재구성
		for(int i = n-1; i > 0; i--) {
			swap(arr, 0, i);	// 루트 값과 아직 정렬되지 않은 부분의 마지막 요소 교환
			downHeap(arr, i, 0);	// 추출한 루트값을 제외하고 힙 재구성
		}
	}

1. 일반 배열을 최대 힙으로 구성하기 위한 로직으로, 자식노드로부터 부모노드를 비교한다. 반복문에서 인덱스의 범위를 n/2-1부터 0까지로 지정한 이유는, 부모노드의 인덱스를 기준으로 왼쪽 자식노드(i*2 + 1)와 오른쪽 자식노드(i*2 + 2)가 존재하고(n/2를 하는 이유), 루트 노드의 인덱스는 0부터 시작하기 때문이다(n/2에 -1을 하는 이유).

1-1. 왼쪽 자식노드의 인덱스가 배열의 범위를 초과하지 않고(leftChildNode < n), 부모노드의 값이 왼쪽 자식노드의 값보다 작으면(arr[parentNode] < arr[leftChildNode]), 부모노드의 인덱스에 왼쪽 자식노드의 인덱스를 저장하여 위치를 조정해준다(parentNode = leftChildNode). 이는 최대 힙에서 부모노드의 값은 자식노드의 값보다 작을 수 없기 때문이다.
1-2. 오른쪽 자식노드의 인덱스가 배열의 범위를 초과하지 않고(rightChildNode < n), 부모노드의 값이 오른쪽 자식노드의 값보다 작으면(arr[parentNode] < arr[rightChildNode]), 부모노드의 인덱스에 오른쪽 자식노드의 인덱스를 저장하여 위치를 저장해준다(parentNode = rightChildNode). 이는 자식노드의 값은 부모노드의 값은 자식노드의 값보다 작을 수 없기 때문이다.
1-3. 만약 부모노드의 인덱스에 변화가 있는 경우, 부모노드와 자식노드 간에 위치 조정이 필요하므로 자식노드와 부모노드의 값을 교환한다(swap()). 그리고 조정이 완료된 부모노드부터 다시 downHeap()을 수행한다.

2. 최대 힙이 구성된 상태이므로, 루트 값과 아직 정렬되지 않은 부분의 마지막 요소의 값을 교환하여 루트 값을 추출한 후(swap()), 추출한 루트값을 제외하고 힙을 재구성한다(downHeap()). 반복문에서 인덱스를 n-1로 초기화 한 이유는, 힙 정렬은 최하위 레벨부터 위로 진행하는 down-top 방식이기 때문이다. 또한, 힙 정렬의 마지막 단계에서 배열의 첫 번째 요소(루트 노드)만 남았을 경우, 그 요소가 이미 최대값이기 때문에 더 이상의 조정이 필요 없기 때문에 루트 노드를 제외하고 반복문을 수행하게 된다(i>0).

4. 성능 분석

public class HeapSort {
    
    // O(1)
    static void swap(int[] arr, int idx1, int idx2) {
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }
    
    // O(log n)
    static void downHeap(int[] arr, int n, int selectedIdx) {
        int parentNode = selectedIdx;
        int leftChildNode = parentNode*2 + 1;
        int rightChildNode = parentNode*2 + 2;
        
        // O(1)
        if(leftChildNode < n && arr[parentNode] < arr[leftChildNode]) {
            parentNode = leftChildNode;
        }
        
        // O(1)
        if(rightChildNode < n && arr[parentNode] < arr[rightChildNode]) {
            parentNode = rightChildNode;
        }
        
        // O(log n)
        if(selectedIdx != parentNode) {
            swap(arr, parentNode, selectedIdx);
            downHeap(arr, n, parentNode);
        }
    }
    
    static void heapSort(int[] arr, int n) {
        // O(n)
        for(int i = n/2 - 1; i >= 0; i--) {
            downHeap(arr, n, i);
        }
        
        // O(n log n)
        for(int i = n-1; i > 0; i--) {
            swap(arr, 0, i);    // O(1)
            downHeap(arr, i, 0);    // O(log n)
        }
    }
}

4-1. 배열 → 최대 힙 : O(n)

• 각 노드에 대한 비교 횟수는 트리의 깊이(높이)에 따라 결정된다. 트리의 깊이가 깊어질수록 비교 횟수가 증가할 수 있다.
• 레벨별 노드 수는 위에서 아래로 갈수록 지수적으로 증가한다.
• 각 노드에 필요한 실제 작업(비교) 횟수는 상위 레벨로 올라갈수록 감소한다.
• 상위 레벨에서 더 많은 비교를 해야할 수도 있으나, 노드의 수 자체가 적기때문에 전체 작업량이 선형적으로 증가하게 된다.
  ∴ 트리의 모든 레벨에 대해 필요한 총 작업량은 노드의 총 개수에 비례한다.

4-2. 루트 값 추출 및 힙 재배치 : O(nlogn)

• swap() : O(1)
• downHeap() : 최악의 경우 힙의 높이(logn) 만큼 걸림 → O(logn)
• 전체 과정의 시간 복잡도

  O(logn) + O(log(n−1)) + O(log(n−2)) + ... + O(log2)
  ∴ O(nlogn)

4-3. 힙 정렬 수행 시간

• 최악/최선/평균 → O(nlogn)

  T(n) = O(n) + O(nlogn)
  ∴ T(n) = O(nlogn)

5. 특징

• 선택 정렬을 응용한 알고리즘이다.
  • 불안정적 정렬 알고리즘
  • 제자리 정렬 알고리즘
• 퀵 정렬과 합병 정렬의 성능이 좋기 때문에 사용빈도가 높지 않다.
• 다음과 같은 상황에서 유용하게 사용할 수 있다.
  • 최대값/최소값을 구할 때

    이 글에서는 최대 힙만 이용했지만, 최소 힙으로도 구성이 가능하다. 최소 힙(최소값)/최대 힙(최대값)의 루트값이므로 한 번의 힙 구성을 통해 해당 값을 구하는 것이 가능하다.

  • 최대 k만큼 떨어진 요소들을 정렬할 때

    삽입정렬보다 개선된 결과를 획득할 수 있다.

---

📖 참고

• 힙 소트(Heap Sort)
• 이관용. "알고리즘 11강. 정렬 알고리즘 (2)" 방송통신대학교, 2022년.