히프(heap)

히프 트리 구조

1. 히프의 개요

1) 정의

▪ 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조
▪ 최대 히프(Max Heap)
- 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
- {부모 노드의 키 값 ≥ 자식 노드의 키 값} 
- 루트 노드: 키 값이 가장 큰 노드
▪ 최소 히프(Min Heap)
- 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
- {부모 노드의 키 값 ≤ 자식 노드의 키 값} 
- 루트 노드: 키 값이 가장 작은 노드

 

2) 히프 트리 예

3) 히프의 추상 자료형(ADT Heap)

▪ 데이터 : n개의 원소로 구성된 완전 이진 트리
▪ 각 노드의 키 값은 그의 자식 노드의 키 값보다 크거나 같음

 - 부모 노드의 키 값 ≥ 자식 노드의 키 값

▪ 연산

heap∈Heap; item∈Element; 

// 공백 히프의 생성 연산
createHeap() ∷= create an empty heap; 

// 히프가 공백인지를 검사하는 연산
isEmpty(heap) ∷= if (heap is empty) then return true; 
	else return false; 

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

// 히프에서 키 값이 가장 큰 원소를 삭제하고 반환하는 연산
deleteHeap(heap) ∷= if (isEmpty(heap)) then return error; 
	else { 
		item ← 히프에서 가장 큰 원소; 
		remove {히프에서 가장 큰 원소}; 
		return item; 
	} 
End Heap( )

히프의 삽입 연산

1. 삽입 연산의 단계

1) 1단계
▪ 완전 이진 트리를 유지하면서 확장한 노드에 삽입할 원소를 임시 저장
- 노드가 n개인 완전 이진 트리에서 다음 노드의 확장 자리는 n+1번의 노드가 됨
- n+1번 자리에 노드를 확장하고, 그 자리에 삽입할 원소를 임시 저장함

2) 2단계
▪ 만들어진 완전 이진 트리 내에서 삽입 원소의 제자리를 찾음
- 현재 위치에서 부모 노드와 비교하여 크기 관계를 확인함
- 최대 히프의 경우
{현재 부모 노드의 키 값 ≥ 삽입 원소의 키 값}의 관계가 성립하지 않으면, 현재 부모 노드의 원소와 삽입 원소의 자리를 서로 바꿈

 

2. 최대 히프에서의 삽입 연산의 예

1) 17을 삽입하는 경우
▪ 노드를 확장하여 임시로 저장한 위치에서의 부모 노드와 크기를 비교하여 히프의
크기 관계가 성립하므로, 현재 위치를 삽입 원소의 자리로 확정

2) 23을 삽입하는 경우

3. 히프에서의 삽입 연산 알고리즘

1) 최대 히프에서의 삽입 알고리즘

insertHeap(heap, item)
	if (n = heapSize) then heapFull( );
	n ← n+1; // ①
	for (i ← n; ;) do {
		if (i = 1) then exit;
		if (item ≤ heap[└ i/2 ┘] then exit; // ②
		Heap[i] ← heap[└ i/2 ┘]; // ③
		i ← └ i/2 ┘ // ④
	}
	heap[i] ← item; // ⑤
end insertHeap( )

2) 삽입과정
① 현재 히프의 크기를 하나 증가시켜서 노드 위치를 확장하고, 확장한 노드 번호가 현재의 삽입 위치 i가 됨
② 삽입할 원소 Item과 부모 노드 heap[└i/2┘]를 비교하여 Item이 부모 노드 보다 작거나 같으면 현재의 삽입 위치 i를 삽입 원소의 위치로 확정함
③ 만약 삽입할 원소 Item이 부모 노드 보다 크면, 부모 노드와 자식 노드의 자리를 바꾸어 최대 히프의 관계를 만들어야 하므로 부모 노드 heap[└i/2┘]를 현재의 삽입 위치 heap[i]에 저장함
④ i/2를 삽입 위치 i로 하여, ②~④를 반복하면서 Item을 삽입할 위치를 찾음
⑤ 찾은 위치에 삽입할 노드 Item을 저장하면, 최대 히프의 재구성 작업이 완성되므로 삽입 연산을 종료함

 

히프의 삭제 연산

1. 삭제 연산의 단계

1) 1단계
히프에서는 루트 노드의 원소 만을 삭제 할 수 있음(삽입과는 역순)
▪ 루트 노드의 원소를 삭제하는 동시에 반환함
2) 2단계
▪ 원소의 개수가 n-1개로 줄었으므로, 노드의 수가 n-1인 완전 이진 트리로 조정함
- 노드가 n개인 완전 이진 트리에서 노드 수 n-1개의 완전 이진 트리가 되기 위해서 마지막 노드, 즉 n번 노드를 삭제함
- 삭제된 n번 노드에 있던 원소는 비어있는 루트 노드에 임시 저장함

3) 3단계
▪ 완전 이진 트리 내에서 루트에 임시 저장된 원소의 제자리를 찾음
- 현재 위치에서 자식 노드와 비교하여 크기 관계를 확인함
- {임시 저장 원소의 키 값 ≥ 현재 자식 노드의 키 값}의 관계가 성립하지 않으면, 현재 자식 노드의 원소와 임시 저장 원소의 자리를 서로 바꿈

 

2. 히프에서의 삭제 연산의 예

3. 히프에서의 삭제 연산 알고리즘

1) 최대 히프에서의 삭제 알고리즘

deleteHeap(heap)
	if (n = 0) then return error;
	item ← heap[1]; // ①
	temp ← heap[n]; // ②
	n ← n-1; // ③
	i ← 1; // ④
	j ← 2;
	while (j ≤ n) do {
		if (j < n) then 
		if (heap[j] < heap[j+1]) then j ← j+1; // ⑤
		if (temp ≥ heap[j]) then exit; 
		heap[i] ← heap[j]; 
		i ← j: // ⑥
		j ← j*2;
	}
	heap[i] ← temp; // ⑦
	return item; // ⑧
end deleteHeap( )

2) 삭제 과정
① 루트 노드 heap[1]을 변수 Item에 저장함
② 마지막 노드의 원소 heap[n]을 변수 temp에 임시 저장함
③ 마지막 노드를 삭제하고, 히프 배열의 원소 개수를 하나 감소함
④ 마지막 노드의 원소였던 temp의 임시 저장 위치 i는 루트 노드의 자리인 1번이 됨
⑤ 현재 저장 위치에서 왼쪽 자식 노드 heap[j]와 오른쪽 자식 노드 heap[j+1]이 있을 때, 둘 중에서 키 값이 큰 자식 노드의 키 값과 temp를 비교하여, temp가 크거나 같으면 현재 위치가 temp의 자리로 확정됨
⑥ 만약 temp가 자식 노드 보다 작으면 자식 노드와 자리를 바꾸고, 다시 ⑤~⑥을 반복하면서 temp의 자리를 찾음
⑦ 찾은 위치에 temp를 저장하여 최대 히프의 재구성 작업을 완성함
⑧ 루트 노드를 저장한 item을 반환하는 것으로 삭제 연산을 종료함

 

핵심 정리

히프 트리 구조

▪ 히프(Heap)는 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전
이진 트리(Complete Binary Tree)를 기본으로 한 자료구조(Tree-based 
Structure)로서 다음과 같은 힙 속성(Property)을 만족함
- A가 B의 부모 노드(Parent node)이면, A의 키(Key) 값과 B의 키 값 사이에는
대소관계가 성립함
- 키 값의 대소관계는 오로지 부모 노드와 자식 노드 간에만 성립하며, 특히 형제
사이에는 대소관계가 정해지지 않음

 

히프의 삽입 연산

▪ 완전 이진 트리를 유지하면서 확장한 노드에 삽입할 원소를 임시 저장함
▪ 만들어진 완전 이진 트리 내에서 삽입 원소의 제자리를 찾음

 

히프의 삭제 연산

▪ 루트 노드의 원소를 삭제하여 반환함
▪ 원소의 개수가 n-1개로 줄었으므로, 노드의 수가 n-1인 완전 이진 트리로 조정함
▪ 완전 이진 트리 내에서 루트에 임시 저장된 원소의 제자리를 찾음