Heap의 실전적 구현

Data heap[100000];  
int count;  
  
void push(Data data) {  
	heap[++count] = data;  
	for (int c = count; c > 1; c /= 2) {  
		if (compare(heap[c], heap[c / 2]) {  
			swap(heap[c], heap[c / 2]);  
		} else {  
			break;  
		}  
	}  
}  
  
void pop(void) {  
	if (count == 0) return;  
	swap(heap[1], heap[count—-]);	// 루트와 제일 마지막 요소를 swap  
  
	// 재정렬  
	for (int c = 2; c <= count; c *= 2) {  
		if (c < count && compare(heap[c + 1], heap[c])) c++;  
		if (compare(heap[c], heap[c / 2])) {  
			swap(heap[c], heap[c / 2]);  
		} else {  
			break;  
		}  
	}  
}  
  
void erase(int index) {  
	// 지우고자 하는 노드를 루트로 이동시키기  
	for (int c = index; c > 1; c /= 2) {  
		swap(heap[c], heap[c / 2]);  
	}  
  
	// 루트를 삭제하기  
	pop();  
}  

compare 함수의 구현에 따라 최대 Heap, 최소 Heap이 결정된다. pop()은 경우에 따라 루트였던 노드를 리턴하도록 구현할 수도 있다.

Data 타입을 정의할 때 operator> 연산자 오버로딩을 잘 활용하자. 비교의 조건이 여러개이고 보조 조건이 있는 경우에도 주요 로직 변경없이 쉽게 처리가 가능하다.

값으로 먼저 비교하고 동점시 id로 비교한다면 아래와 같이 구현할 수 있다.

bool operator>(Data cmp) {  
	if (value != cmp.value) return value > cmp.value;  
	return id > cmp.id;  
}  

Lazy update 방식

Heap에 한정된 이야기는 아니다. 다만 Heap의 경우에는 이미 들어가 있는 데이터를 수정하기가 쉽지않아 많이 쓰이는 편이다. 데이터의 수정이 필요한 경우 기존 데이터는 그대로 두고 새로운 데이터를 추가로 넣어버리고 나중에 pop()을 할때에서야 신선한 데이터인지를 판단하는 것이다. 이를 위해 정렬을 위한 Heap과 별도로 최신 값을 저장할 배열이 필요하게 된다.

예를 들어 여러 Heap에 중복된 데이터가 들어가는 경우 다른 Heap에서 수정이나 삭제가 되더라도 다른 Heap에 반영하지않고 pop()때까지 판단을 유보하는 방식이다.

Real time update(RTU) 방식

말그대로 수정이 필요할 때, Heap 요소를 바로 업데이트하는 방식이다. 성능상에서 조금 안좋겠지만 더 직관적이다. Heap에 업데이트를 하기 위해 Heap을 구현하기 위한 배열에서의 인덱스를 별도의 배열에 저장하는 것이 포인트이다.