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

1. 이진 힙(Binary Heap) 데이터구조란 무엇인가?

이진 힙은 아래와 같은 특성을 가지고 있는 이진 트리입니다.

1. 이진 힙의 데이터 구조는 완전 이진 트리 기반
   • 완전 이진 트리란 마지막 레벨을 제외하고 모든 레벨이 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 왼쪽에 있는 트리를 의미합니다.
2. 이진 힙 구성
   • 최소 힙(MinHeap) : 부모 노드가 자식 노드보다 값이 작음, 루트 노드의 경우 모든 노드들 중 가장 작은 값이 됨
   • 최대 힙(MaxHeap) : 부모 노드가 자식 노드보다 값이 금, 루트 노드의 경우 모든 노드들 중 가장 큰 값이 됨

즉, 정리하면 이진 힙이란 완전 이진 트리이면서 최소 힙 또는 최대 힙의 규칙으로 구성된 트리를 의미합니다.

 

최소 힙(Min Heap) 예제

위의 그림을 보면 최소 힙을 구성하는 것을 볼 수 있습니다. 그중에서 루트 노드인 10 노드는 트리 중에서 가장 작은 값을 가지는 것을 알 수 있습니다.

 

2. 이진 힙의 부모, 자식 접근

이진 힙은 완전 이진 트리 기반이므로 배열을 통해서 접근이 가능합니다.

• 루트 노드는 Arr[0]와 같이 접근
• Arr[i] 노드 기준 부모, 왼쪽 자식, 오른쪽 자식 노드 접근

Arr[(i-1)/2]	부모 노드 반환
Arr[(2*i)+1]	왼쪽 자식 노드 반환
Arr[(2*i)+2]	오른쪽 자식 노드 반환

배열 기반의 접근에 사용되는 순회 방법은 Level Order 방법이 존재합니다.

3. 힙의 용도

1. Heap Sort : Heap Sort는 O(nLogn) 시간에 배열을 정렬하기 위해 이진 힙(Binary Heap)을 사용
2. Priority Queue : 이진 힙(Binary Heap)은 insert(), delete(), extractmax(), decreaseKey() 연산들을 O(logN) 시간에 가능하기 때문에 이진 힙을 사용하여 효율적으로 PriorityQueue을 구현 가능합니다. Binomoial Heap과 Fibonacci Heap은 이진 힙의 변형중 하나입니다. 이러한 변형 힙들은 통합(union)과 같은 연산을 효율적으로 수행할 수 있습니다.
3. Graph Algorithms : Priority Queue는 특히 Dijkstra's Shortest Path와 Prim's Minimum Spanning Tree와 같은 그래프 알고리즘에 사용됩니다.

4. 최소 힙의 수행 과정

4.1 add

1. 힙의 빈 공간에 노드를 추가
2. 부모 노드와 비교함, 부모 노드보다 작다면 두 노드를 교환함 (trickleUp)

 

4.2 remove

1. 루트 노드를 제거
2. 힙의 마지막 요소를 루트 노드에 넣어줌
3. 루트에서 시작하여 두 자식 중 작은 노드와 바꿔주어 힙의 규칙을 만족하게 해줍니다. (trickleDown)

 

4.3 set

1. i번째 노드를 새로운 값으로 변경함
2. i번째 노드를 기준으로 부모 노드와 비교함, 부모 노드보다 작다면 교환함 (trickleUp)

 

4.4 trickleUp

trickleUp 과정은 i번째 노드를 기준으로 루트 노드까지 부모 노드와 비교하면서 부모 노드 값보다 더 작다면 서로 교환하는 과정입니다.

 

완전 이진 트리이기 때문에 노드의 위치는 다음과 같은 성질을 가집니다.

• parent : floor((child-1)/2)
• left : 2*parent+1
• right : 2*parent+2

	// 최소 힙이 되도록 조정
	// 위로 올라가면서 최소 힙 조정
	private void minTrickleUp(int i)
	{
		if(i==0)
		{
			return;
		}
		
		int parent = getParent(i);
		if(((Comparable<E>)harr[i]).compareTo(harr[parent])<0)
		{
			swap(parent, i);
			minTrickleUp(parent);
		}
	}
    
    // parent번째와 i번째를 교환
	// parent번째 원소와 i번째 원소 교환
	private void swap(int parent, int i)
	{
		E temp = harr[parent];
		harr[parent] = harr[i];
		harr[i] = temp;
	}

 

4.5 trickleDown

trickleDown 과정은 i번째 노드를 기준으로 리프 노드까지 자식 노드와 비교하면서 자식 노드 중 제일 작은 수와 교환합니다. trickleDown 과정을 통하여 힙 규칙을 유지시킵니다.

	// i번째에서 아래로 내려가면서 최소 힙 조정
	private void minTrickleDown(int i)
	{
		int left = getLeftChild(i);
		int right = getRightChild(i);
		int smallest = i;
		
		if(left < heapSize && ((Comparable<E>)harr[left]).compareTo(harr[smallest])<0)
		{
			smallest = left;
		}
		
		if(right < heapSize && ((Comparable<E>)harr[right]).compareTo(harr[smallest])<0)
		{
			smallest = right;
		}
		
		if(smallest != i)
		{
			swap(smallest,i);
			minTrickleDown(smallest);
		}		
	}

 

 

5. 최소 힙의 구현

위에서 소개된 add, remove, set, trickleUp, trickleDown 등의 과정을 코드로 구현합니다.

public class MinHeap<E> {
	private E[] harr;
	private int capacity;	// 힙의 최대 크기
	private int heapSize;	// 힙의 현재 크기
	
	public MinHeap()
	{
		this(10);
	}
	
	public MinHeap(int capacity)
	{
		harr = (E[]) new Object[capacity];
		this.capacity = capacity;
		heapSize = 0;
	}

	// 힙에 원소를 추가
	public void add(E obj)
	{
		// 힙이 꽉차있는지 검사
		if(heapSize==capacity)
		{
			System.out.println("Overflow : Could not add\n");
			return;
		}
		
		// heap의 마지막 자리에 값을 추가
		heapSize++;
		int i = heapSize - 1;
		harr[i] = obj;

		// 위로 올라가면서 힙 조정
		minTrickleUp(i);
	}

	// 루트 노드의 값을 추출합니다. 추출된 루트 노드는 제거됩니다.
	public E remove()
	{
		if(heapSize<=0)
		{
			return null;
		}
		
		if(heapSize==1)
		{
			heapSize--;
			return harr[0];
		}
		
		// 힙으로부터 루트 노드의 값을 제거하고 최소값으로 대체
		E root = harr[0];
		harr[0] = harr[--heapSize];
		minTrickleDown(0);	// 루트 노드 힙조정
		
		return root;
	}
	
	// i번째 노드의 값을 new_val 값으로 변경합니다.
	public void set(int i, E newObj)
	{
		// i번째 노드의 값 변경
		harr[i] = newObj;
		
		// 위로 올라가면서 힙 조정
		minTrickleUp(i);
	}

	// 최소값 반환, 루트 노드의 값을 제거하지 않고 값만 반환합니다.
	public E getMin()
	{
		return harr[0];
	}

	// 힙 출력
	public void printHeap()
	{
		for(int i=0;i<heapSize;i++)
		{
			System.out.print(harr[i] + " ");
		}
		System.out.println();
	}
	
	// 최소 힙이 되도록 조정
	// 위로 올라가면서 최소 힙 조정
	private void minTrickleUp(int i)
	{
		if(i==0)
		{
			return;
		}
		
		int parent = getParent(i);
		if(((Comparable<E>)harr[i]).compareTo(harr[parent])<0)
		{
			swap(parent, i);
			minTrickleUp(parent);
		}
	}
	
	// i번째에서 아래로 내려가면서 최소 힙 조정
	private void minTrickleDown(int i)
	{
		int left = getLeftChild(i);
		int right = getRightChild(i);
		int smallest = i;
		
		if(left < heapSize && ((Comparable<E>)harr[left]).compareTo(harr[smallest])<0)
		{
			smallest = left;
		}
		
		if(right < heapSize && ((Comparable<E>)harr[right]).compareTo(harr[smallest])<0)
		{
			smallest = right;
		}
		
		if(smallest != i)
		{
			swap(smallest,i);
			minTrickleDown(smallest);
		}		
	}
		
	// parent번째와 i번째를 교환
	// parent번째 원소와 i번째 원소 교환
	private void swap(int parent, int i)
	{
		E temp = harr[parent];
		harr[parent] = harr[i];
		harr[i] = temp;
	}	
	
	// i번째 부모의 인덱스 반환
	// 주어진 i번째 노드의 부모 노드 반환
	private int getParent(int i)
	{
		return (i-1)/2;
	}
	
	// i번째의 왼쪽 자식 인덱스 반환
	// 주어진 i번째 노드의 왼쪽 자식 반환
	private int getLeftChild(int i)
	{
		return (2*i+1);
	}
	
	// i번째의 오른쪽 자식 인덱스 반환
	// 주어진 i번째 노드의 오른쪽 자식 반환
	private int getRightChild(int i)
	{
		return (2*i+2);
	}
	
}

class MinHeapTest {

	@Test
	void minHeapAddTest() {
		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
	}
	
	@Test
	void minHeapRemoveTest() {
		MinHeap<Integer> heap = new MinHeap<Integer>(5);
		
		heap.add(5);
		heap.add(4);
		heap.add(3);
		heap.add(2);
		heap.add(1);
		
		// Expected Output : 1 2 3 4 5
		System.out.print(heap.remove() + " ");	 
		System.out.print(heap.remove() + " ");
		System.out.print(heap.remove() + " ");
		System.out.print(heap.remove() + " ");
		System.out.print(heap.remove() + " ");
		System.out.println();
	}
	
	@Test
	void minHeapSetTest() {
		MinHeap<Integer> heap = new MinHeap<Integer>(5);
		
		heap.add(50);
		heap.add(40);
		heap.add(30);
		heap.add(20);
		heap.add(10);
	
		heap.printHeap(); // Expected Output : 10 20 40 50 30
		heap.set(3, 5);
		heap.printHeap(); // Expected Output : 5 10 40 20 30
		
	}
}

 

References

source code : https://github.com/yonghwankim-dev/DataStruct
https://www.geeksforgeeks.org/binary-heap/
[부스트코스] 자바로 구현하는 자료구조