비선형 데이터구조, 힙(Heap) #2 이진 힙 정렬(Binary Heap Sort)

이전글

https://yonghwankim-dev.tistory.com/123

비선형 데이터구조, 힙(Heap) #1 이진 힙(Binary Heap)

 

개요

이전글에서는 이진 힙의 구조를 알아보았습니다. 이번글에서는 이진 힙을 정렬하는 함수를 구현하겠습니다.

 

1. Binary Heap은 무엇인가?

Binary Heap은 완전 이진 트리입니다. 완전 이진 트리는 마지막 레벨을 제외한 모든 레벨에 노드가 채워져 있고 마지막 레벨의 노드들은 전부 왼쪽에 위치해 있습니다. Binary Heap은 부모 노드의 값이 두개의 노드 값보다 크거나 작도록 특별한 순서로 노드가 저장되는 완전한 이진 트리입니다. 우리는 이것을 최대 힙(max heap) 또는 최소 힙(min heap)이라고 불립니다. 힙은 이진 트리 이거나 배열 기반으로 나타낼 수 있습니다.

 

Binary Heap은 왜 배열 기반으로 표현하는가?

Binary Heap은 완전 이진 트리이기 때문에 배열 기반의 표현이 공간 효율성이 좋고 쉽게 부모 노드와 자식 노드를 표현할 수 있습니다. 만약 부모 노드의 인덱스가 I라고 저장되면, 왼쪽 자식 노드는 (2*I+1)번째이고 오른쪽 자식 노드는 (2*I+2)번째 입니다. (인덱스는 0번째부터 시작)

 

어떻게 트리를 조정(heapify)할까?

이진 트리를 Heap 데이터 구조로 다시 그리기 위한 프로세스를 heapify라고 알려져 있습니다. 이진 트리는 최대 2개의 자식노드를 가지는 구조입니다. 만약 노드의 자식 노드들이 조정된다면 오직 'heapify' 프로세스는 해당 자식 노드를 기준으로 조정됩니다. 힙은 언제나 이진 트리 규칙을 만족해야 합니다.

 

완전 이진 트리로부터 시작하여 우리는 그 힙의 자식 노드를 가지고 있는 모든 부모 노드들을 대상으로 'heapify'를 호출함으로써 최대힙(Max-Heap)이 될 수 있습니다. 즉, 'heapify'를 재귀적으로 사용합니다.

 

"heapify" 알고리즘

heapify(array)
   Root = array[0]
   Largest = largest( array[0] , array [2 * 0 + 1]. array[2 * 0 + 2])
   if(Root != Largest)
       Swap(Root, Largest)

0번째 루트 노드를 기준으로 루트 노드와 왼쪽 자식 노드, 오른쪽 자식 노드 중 가장 큰 노드를 탐색합니다. 그리고 왼쪽 노드, 오른쪽 노드 중 루트 노드보다 큰 노드가 존재하면 루트 노드와 큰 자식 노드를 값을 교환합니다.

 

"heapify"의 예시

        30(0)                 
       /   \         
    70(1)   50(2)

Child (70(1)) is greater than the parent (30(0))

Swap Child (70(1)) with the parent (30(0))
        70(0)                 
       /   \         
    30(1)   50(2)

오름차순 힙 정렬 알고리즘 수행 과정

1. 입력된 데이터에 대하여 최대 힙으로 구현합니다.
2. 최대힙으로 구현되면 최대 힙의 루트 노드에는 가장 큰 값이 저장될 것입니다. 이후 힙의 크기를 1감소시킴으로써 힙의 마지막 원소와 루트 노드를 교환합니다.
3. heap의 크기가 0이 될때까지 2번의 과정을 반복 수행합니다.

heap을 어떻게 수행되는가?

자식 노드들이 힙조정되는 경우에만 heapify 절차를 노드에 적용할 수 있습니다. 그래서 힙조정은 바텀업(bottom-up) 순서로 수행되어야 합니다. 아래의 예시는 힙 조정의 예시입니다.

Input data: 4, 10, 3, 5, 1
         4(0)
        /   \
     10(1)   3(2)
    /   \
 5(3)    1(4)

소괄호 안의 숫자는 배열의 인덱스를 의미함

1번째에서 힙조정 수행한 결과 : 변화없음
         4(0)
        /   \
    10(1)    3(2)
    /   \
5(3)    1(4)

0번째에서 힙조정 수행한 결과 : 
        10(0)
        /  \
     5(1)  3(2)
    /   \
 4(3)    1(4)
heapify 절차는 위에서 아래로 재귀적으로 수행됩니다.

 

2. 힙 정렬 알고리즘 구현

sort 메서드와 maxTrickleDown 메서드는 최소힙 클래스(MinHeap)의 메서드로써 sort 메서드에서 파라미터로 배열을 입력받지 않도록 구현하였습니다. maxTrickleDown 메서드는 heapify 역할을 수행합니다. 즉, i번재 노드를 기준으로 위에서 아래로 최대 힙이 되도록 힙조정을 수행합니다. 자세한 코드는 References source code에서 확인할 수 있습니다.

	// 힙 정렬
	public void sort()
	{
		// 최대힙이 되도록 조정
		for(int i=heapSize/2-1;i>=0;i--)
		{
			maxTrickleDown(heapSize, i);
		}
		
		// 힙의 마지막 원소부터 시작하여 힙 정렬 수행
		for(int i=heapSize-1;i>0;i--) {
				
			// 힙의 마지막 원소와 루트 값을 교환
			// 0번째는 최대값이 위치함, i번째는 최소값이 위치함
			swap(0,i);
			
			// 루트에서 최대힙이 되도록 조정
			maxTrickleDown(i,0);
		}
	}
    
    // 0~lastPosition 범위내에서 i번째 원소의 최대 힙 조정
	private void maxTrickleDown(int lastPosition, int i)
	{
		int left = getLeftChild(i);
		int right = getRightChild(i);
		int largest = i;
		
		if(left < lastPosition && ((Comparable<E>)harr[left]).compareTo(harr[largest])>0)
		{
			largest = left;
		}
		
		if(right < lastPosition && ((Comparable<E>)harr[right]).compareTo(harr[largest])>0)
		{
			largest = right;
		}
		
		if(largest != i)
		{
			swap(largest,i);
			maxTrickleDown(lastPosition, largest);
		}		
	}

	@Test
	void minHeapSortTest() {
		MinHeap<Integer> heap = new MinHeap<Integer>(5);
		
		heap.add(5);
		heap.add(4);
		heap.add(3);
		heap.add(2);
		heap.add(1);
		
		heap.printHeap(); // Expected Output : 1 2 4 5 3
		
		heap.sort();	// 최소힙의 오름차순 정렬
		
		heap.printHeap(); // Expected Output : 1 2 3 4 5
			
	}

1 2 4 5 3
1 2 3 4 5

위의 최소 힙 오름차순 정렬 수행과정을 그림을 표현하면 아래와 같습니다.

 

References

source code : https://github.com/yonghwankim-dev/DataStruct/blob/main/Heap/Implement/MinHeap.java
https://www.geeksforgeeks.org/heap-sort/