[자료구조] 힙(Heap)

1. 개념

• 완전 이진 트리에 있는 노드 중에서 킷값이 가장 큰 노드나 킷값이 가장 작은 노드를 찾기 위해서 만든 자료구조
• 힙은 완전 이진 트리이므로 배열로 표현 가능

힙(Heap)이란 완전 이진 트리로써 각 노드의 값은 자신의 자식 노드의 값보다 크거나 같다. 따라서 힙은 언제나 루트의 값이 최댓값이 된다.

힙에서 최댓값을 삭제하게 되면 힙의 마지막(배열 마지막 인덱스) 원소를 삭제된 위치인 루트에 넣고 힙을 하나 줄인 뒤 힙이 되도록 자식들과 크기를 비교하며 필요한 값을 서로 교환한다. 

힙 정렬은 힙을 활용하여 정렬하는 방식이다.

 

1) 최대 힙(Max Heap)

• 킷값이 가장 큰 노드를 찾기 위한 완전 이진 트리
• {부모 노드의 킷값 ≥ 자식 노드의 킷값}
• 루트 노드 : 킷값이 가장 큰 노드

 

2) 최소 힙(Min Heap)

• 킷값이 가장 작은 노드를 찾기 위한 완전 이진 트리
• {부모 노드의 킷값 ≤ 자식 노드의 킷값}
• 루트 노드 : 킷값이 가장 작은 노드

 

3) 최대 힙(Heap)의 예

• Root가 가장 크다.
• 자식 노드의 Root 또한 가장 크다.

 

			33
		↙		↘
	31				24
↙		↘		↙		↘
21		29		16		22

 

4) 최소 힙(Heap)의 예

• Root가 가장 작다.
• 자식 노드의 Root 또한 가장 작다.

 

			16
		↙		↘
	19				20
↙		↘		↙		↘
25		29		22		24

 

5) 힙이 아닌 예

 

• 완전 이진 트리를 만족하지 않은 예

			9
		↙		↘
	5				4
↙		↘				↘
4		2				1

 

• 최대 힙, 최소 힙을 구성하는 규칙에 어긋난 예

			9
		↙		↘
	11				6
↙		↘		↙
8		11		15

 

 

2. 알고리즘

• 데이터 : n개의 원소로 구성된 완전 이진 트리로써 각 노드의 킷값은 그의 자식 노드의 킷값보다 크거나 같다. 
   - 부모 노드의 킷값 ≥ 자식 노드의 킷값인 최대 힙(Max Heap)을 말한다.

1) 연산

heap ∈ Heap; item ∈ Element;
createHeap() = create an empty heap;	// 공백 힙의 생성 연산

// 힙이 공백인지를 검사하는 연산
isEmpty(heap) = if(heap is empty) return true;	
				else return false;

// 힙의 적당한 위치에 원소(item)를 삽입하는 연산
insertHeap(heap, item) = insert item into heap;

// 힙에서 킷값이 가장 큰 원소를 삭제하고 반환하는 연산
deleteHeap(heap) = if(isEmpty(heap)) return error;
					else{
						item <- 힙에서 가장 큰 원소;
						remove{힙에서 가장 큰 원소};
						return item;
					}
End Heap()

 

3. 삽입 연산

1) 1단계 

• 완전 이진 트리를 유지하면서 노드를 확장하여 삽입할 원소를 임시 저장
• 노드가 n개인 완전 이진 트리에서 다음 노드의 확장 자리는 n + 1번의 노드
• n + 1번 자리에 노드를 확장하고 그 자리에 삽입할 원소를 임시 저장

 

2) 2단계

• 만들어진 완전 이진 트리 내에서 삽입 원소의 제자리를 찾는다.
• 현재 위치에서 부모 노드와 비교하여 크기 관계를 확인
• {현재 부모 노드의 킷값 ≥ 삽입 원소의 킷값}의 관계가 성립하지 않으면, 현재 부모 노드의 원소와 삽입 원소의 자리를 서로 바꾼다.

 

3) 알고리즘

 

isertHeap(heap, item)
	if(n == heapSize) HeapFull();
	else n <- n + 1	;			// 1
	for( i <- n; ;) do {
		if(i = 1) exit;
		if(item <= heap[i/2]) exit;	// 2
		heap[i] <- heap[i/2];		// 3
        i <- i/2				// 4
	}
	heap[i] <- item;			// 5
end insertHeap()

 

1. 현재 힙의 크기를 하나 증가시켜 노드 위치를 확장하고 확장한 노드 번호가 현재의 삽입 위치 i가 된다.
2. 삽입할 원소 item과 부모 노드 heap[i/2]를 비교하여 item이 부모 노드보다 작거나 같으면 현재의 삽입 위치 i를 삽입 원소의 위치로 확정한다.
3. 만약 삽입할 원소 item이 부모 노드보다 크면 부모 노드와 자식 노드의 자리를 바꾸어 최대 힙의 관계를 만들어야 하므로 부모 노드 heap[i/2]를 현재의 삽입 위치 heap[i]에 저장한다.
4. i/2/를 삽입 위치 i로 하여 2 ~ 4를 반복하면서 item을 삽입할 위치를 찾는다.
5. 찾은 위치에 삽입할 노드 item을 저장하면 최대 힙의 재구성 작업이 완성되므로 삽입 연산을 종료한다.

 

4. 삭제 연산

• 힙에서는 루트 노드의 원소만을 삭제할 수 있다.

 

1) 1단계

• 루트 노드의 원소를 삭제하여 반환

 

2) 2단계

• 원소의 개수가 n - 1개로 줄었으므로 노드의 수가 n - 1인 완전 이진 트리로 조정한다.
• 노드가 n개인 완전 이진 트리에서 노드 수 n - 1개의 완전 이진 트리가 되기 위해서 마지막 노드 즉, n번 노드를 삭제한다.
• 삭제된 n번 노드에 있던 원소는 비어있는 루트 노드에 임시 저장한다.

 

3) 3단계

• 완전 이진 트리 내에서 임시 저장된 원소의 제자리를 찾는다.
• 현재 위치에서 자식 노드와 비교하여 크기 관계를 확인한다.
• {임시저장 원소의 킷값 ≥ 현재 자식 노드의 킷값}의 관계가 성립하지 않으면 현재 자식 노드의 원소와 임시저장 원소의 자리를 서로 바꾼다.

 

4) 알고리즘

 

deleteHeap(heap)
	if(n == 0) return error;
	item <- heap[1];	// 1 루트 노드의 원소를 item에 저장
	temp <- heap[n];	// 2 마지막 노드의 원소를 temp에 보관
	n <- n - 1;		// 3 힙의 노드 개수 1 감소
	i <- 1;			// 4 i : temp 원소가 저장될 노드 번호 저장 변수
	j -< 2;			// j : i의 자식 노드 번호
	while(j <= n) do {
		if(j < n)
			if(heap[j] < heap[i + 1]) j <- j + 1;	// 킷값이 큰 자식 노드 찾기
		if(temp >= heap[j]) exit;	// 5 자식 노드가 작으면 자리 확정
		heap[i] <- heap[j];		// 6 자식 노드가 크면 자리 교환
		i <- j;
		j <- j * 2;
	}
	heap[i] <- temp;	// 7
	return item;		// 8
end deleteHeap()

 

1. 루트 노드 heap[1]을 item에 저장
2. 마지막 노드의 원소 heap[n]을 temp에 임시 저장
3. 마지막 노드 삭제
4. 마지막 노드의 원소였던 temp의 임시 저장위치 i는 루트 노드 자리인 1번이 됨
5. 현재 저장위치에서 자식 노드 heap[j]와 heap[j + 1]이 있을 때 둘 중에서 킷값이 큰 자식 노드의 킷값과 temp를 비교하여 temp가 크거나 같으면 현재 위치가 temp의 자리로 확정
6. 만약 temp가 자식 노드보다 작으면 자식 노드와 자리를 바꾸고 다시 5 ~ 6을 반복 하면서 temp 자리를 찾음
7. 찾은 위치에 temp를 저장하여 최대 힙의 재구성 잡업을 완성
8. 루트 노드를 저장한 item을 반환하는 것으로 삭제 연산 종료