<히프> 기본 개념과 삽입 삭제 알고리즘 정리

# 히프의 개념

---

 히프(heap)는 "더미"라는 뜻이다. 히프는 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다. 히프는 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 (작은) 이진 트리를 말한다. 즉 A가 B의 부모 노드라고 하고 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크다고 하면, 다음과 같은 조건이 항상 성립하는 트리이다.

$Key(A) >= Key(B)$

 히프는 완전 이진 트리(complete binary tree) 이며 중복된 값을 허용함에 유의한다. 이진 탐색 트리에서는 중복된 값을 허용하지 않았다. 히프 안에서 데이터들은 느슨한 정렬 상태를 유지한다. 즉, 큰 값이 상위 레벨이고 작은 값이 하위 레벨에 있다는 정도의 정렬상태다. 애초에 히프는 삭제연산을 수행할 때마다 가장 큰 (작은) 값을 찾아내게끔 구현되어 있기 때문이다. 가장 큰 (작은) 값을 알아내면 되는 것이기 때문에 전체 데이터를 정렬할 필요는 없는 것이다.

 히프에는 두 가지 종류의 히프 트리가 존재한다. 하나는 부모 노드의 키 값이 자식 노드보다 큰 최대 히프(max heap)이고, 또 하나는 부모 노드의 키 값이 항상 자식 노드보다 작은 최소 히프(min heap)이다. 두 가지의 히프는 단지 부등호만 달라지고 나머지는 완전히 동일하다.

최대 히프(max heap)의 조건:   $Key(부모노드) >= Key(자식 노드)$

최소 히프(min heap)의 조건:   $Key(부모 노드) <= Key(자식 노드)$

# 히프의 구현

---

 히프는 완전 이진 트리이기 때문에 각각의 노드에 차례대로 번호를 붙일 수 있다. 이 번호를 배열의 인덱스로 생각하면 배열에 히프의 노드들을 저장할 수 있다. 따라서 히프를 저장하는 표준 자료 구조는 배열이다. 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다. 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않음을 유의한다. 예를 들면 루트 노드의 오른쪽 노드의 인덱스는 항상 3번이다.

 배열을 이용하여 히프를 저장하면 완전 이진 트리에서처럼 자식 노드와 부모 노드를 쉽게 알 수 있다. 부모노드를 3이라고 가정했을 때, 왼쪽 자식노드는 3 * 2 이고, 오른쪽 자식노드는 (3 * 2) + 1 이다.

• 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
  
  
• 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
  
  
• 부모의 인덱스 = (자식의 인덱스) / 2

 히프를 구현하여 보면, 히프는 1차원 배열로 표현될 수 있기 때문에 아래와 같이 히프의 요소를 구조체로 표현하고 이 구조체의 1차원 배열을 만들어 히프를 표현한다. 여기서 heap_size는 현재 히프 안에 저장된 요소의 개수이다.

/*************************************************
 ** 구조체로 표현한 히프
*************************************************/

typedef struct
{
	int key;
} element;

typedef struct
{
	element heap[MAX_ELEMENT];
	int heap_size;
} HeapType;

/*************************************************
 ** End Line
*************************************************/

# 히프의 삽입 연산

---

 히프에서의 삽입 연산은 회사에서 신입사원이 들어오면 일단 제일 밑(말단) 위치에 앉힌 다음, 능력을 봐서 위로 승진시켜가는 것과 비슷하다.

 히프에 새로운 요소가 들어오면, 일단 새로운 노드를 히프의 마지막 노드에 삽입한다. 삽입은 했지만 현재 히프의 규칙성이 지켜지고 있는지를 확인해야 하고 그렇지 않다면 적절한 위치로 이동시켜줘야 한다. 따라서 삽입 후에 새로운 노드를, 부모 노드들과 비교한 후 필요할 경우 자리를 교환해서 히프의 성질을 만족시켜 주어야 한다.

 새로운 노드 8이 들어왔다고 가정해보자. 최대 히프의 성질 (부모노드는 항상 자식노드보다 크거나 같아야 한다)을 만족하지 않기 때문에 교환 작업을 진행한다. 자신의 부모노드인 4와 자리를 바꾼다. 하지만 여전히 조건이 만족되지 않는다. 다음으로는 7과 자리를 바꾼다. 이로서 최대히프가 완성되었다.

 아래의 실제 구현에서는 교환과정을 일일이 진행해줄 필요가 없기에 (연산의 최소화를 위하여) 부모 노드만을 끌어내린 후에 삽입될 위치의 정보를 도출하고 그 위치에 새로운 노드를 집어 넣는다. // 굳이 매 루프별 교환을 시행해주지 않아도 똑같은 결과를 낼 수 있기 때문에 프로그램의 효율을 위해 이와같은 처리를 해준다.

/*************************************************
 ** 최대 히프의 삽입 함수
*************************************************/

void insert_max_heap(HeapType *h, element item)
{
	int i = ++(h->heap_size); // 삽입을 할 것이므로 원소의 개수를 증가

	/* 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정 */
	// i가 루트가 아니고 입력으로 받은 item의 key값이 i의 부모의 키 값보다 크면
	while ((i != 1) && (item.key > h->heap[i / 2].key))
	{
		// 거슬러올라가야 하므로 현재노드를 부모노드로 설정하고
		h->heap[i] = h->heap[i / 2];

		// 인덱스를 부모노드의 인덱스로 설정한다.
		i /= 2;
	}
	// 탈출했다는 건 더이상 거슬러 올라갈 곳이 없다는 것이므로
	// 현재 인덱스의 위치에 item을 삽입한다.
	h->heap[i] = item;
}
/*************************************************
 ** End Line
*************************************************/

# 히프의 삭제 연산

---

삭제 연산은 회사에서 사장의 자리가 비게 되면 먼저 제일 밑(말단) 사원을 사장 자리로 올린 다음에 능력에 따라 강등시키는 것과 비슷하다. 사장자리에 앉을 능력이 안되면 강등시키는 건 히프의 법칙을 충족시키는 과정이다.

 최대 히프에서의 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다. 최대 히프에서 최댓값은 루트 노드이므로 루트 노드가 삭제된다. 삭제 후에 루트 노드가 빈 상태로 둘 수는 없으므로 히프를 재구성해야 한다. 그래서 먼저 말단에 있는 노드를 루트 노드에 위치시킨 후, 규칙에 따라 아래 자식노드들과 교환하는 과정을 거친다.

 위의 트리는 최대 히프이다. 루트 노드인 9가 삭제되면서 그 자리는 공석이 되는데 그 공석을 제일 밑의 노드 (인덱스 10)가 대체하게 된다. 3이 루트 노드의 자리에 갔다고 해서, 실제 루트 노드가 되는지는 두고봐야 한다. 최대히프의 규칙성을 깨뜨리는지를 살펴본다. 아래 두 개의 자식 노드 중 더 큰 노드인 7과 비교를 한다. // 더 큰 노드랑 비교하는 이유는 최대 히프의 규칙 때문이다. 계속해서 수행해야 할 교환연산에 있어 큰 자식이랑 비교를 하는 것이 논리성을 깨뜨리지 최소히프였다면 더 작은 자식과 비교를 해야 규칙성이 올바르게 작동한다.

 비교를 하면서 교환이 필요하다면 교환을 수행한다. 이 교환은 자식노드가 현재노드보다 크지 않을 때가지 계속된다. 즉 최대 히프의 규칙을 만족할 때까지 진행된다.

비교를 하면서 올바른 위치를 찾아 교환 연산을 거듭하다 보면 위와 같은 트리가 결과물로 나오게 된다. 아래는 삭제 알고리즘을 코드로 구현한 것이다. 본 포스팅에서는 최대히프에 관해 설명했지만, 아래의 알고리즘은 최소 히프에서의 삭제 연산이다. 최대 히프는 논리만 거꾸로 바꿔주면 되는 것이므로 둘 다 공부할 수 있게끔 최소 히프를 첨부했다.

/*************************************************
 ** 최소 히프 삭제 연산
*************************************************/

element delete_max_heap(HeapType *h)
{
	int parent, child;
	element item, temp;

	// 최소히프의 특성상 루트노드에 있는 값이 가장 작은값이므로
	// 반환할 루트노드의 값을 item에 저장해둔다.
	item = h->heap[1];

	// 맨 마지막에 있는 노드의 값을 temp에 저장하고
	// 루트노드의 정보를 위에서 빼냈으므로 힙사이즈를 1 줄인다.
	temp = h->heap[(h->heap_size)--];

	/* 맨 마지막 노드값 (temp)를 이용한 비교과정 */
	// temp를 일단 루트에 두었다고 가정하고 아래 과정을 시작한다.
	// 최소히프 삭제는 루트노드부터 말단으로 가며 차례대로 비교하여
	// 적절한 위치를 찾아 삽입하는 작업이다.

	parent = 1; // 맨 첫 실행의 부모노드를 루트로 둔다.
	child = 2; // 그리고 그 왼쪽 자식을 자식노드로 둔다.

	// child가 힙 사이즈보다 크면 힙을 벗어난 비교이므로 실행이 안된다.
	// 따라서 child가 힙 사이즈보다 작거나 같을 때 비교가 일어난다.
	while (child <= h->heap_size)
	{
		// 두 개의 자녀 중 더 작은 자녀를 비교기준으로 삼기 위해 아래의 if문 실행
		if (
			// 오른쪽 자녀가 있다고 생각하면, child는 힙사이즈보다 작아야 한다.
			// 왼쪽 자녀가 힙사이즈와 같은데 오른쪽 자녀가 있다면 + 1을 해줘야 하는데
			// 그렇게 되면 힙사이즈를 넘어서기 때문에 child는 힙사이즈보다 작아야 한다.
			(child < h->heap_size) && 
			// 오른쪽 자녀 (child + 1)이 더 작기 때문에 새로운 기준점을 만들어주기 위해
			// child++ 을 해준다.
			(h->heap[child].key) < h->heap[child + 1].key
			)
			child++;

		// 비교 대상인 child를 설정했으니 루트노드에 위치 중인 temp와 비교한다.
		// temp가 더 작다면 위치이동을 할 필요가 없으므로 이 반복문을 빠져나간다.
		// 제자리에 있다는 뜻이다. 최소히프는 작은 값이 부모로 있어야 한다.
		if (temp.key >= h->heap[child].key)
			break;

		// 여기까지 왔다는 건 temp의 자리교환이 필요하다는 뜻이다.
		// temp가 있을 곳을 찾기 위해 비교대상을 한 단계 아래로 이동한다.
		h->heap[parent] = h->heap[child]; // 자녀의 값이 새로운 비교 기준점이 된다.
		parent = child; // 자녀가 부모로 된다. (다음 비교를 위해)
		child *= 2; // 2를 곱하여 다음 자녀로 된다.
	}
	// 위 반복문을 빠져나오면, parent가 temp가 위치할 곳이 되어 있을 것이다.
	h->heap[parent] = temp;
	return item;
}
/*************************************************
 ** End Line
*************************************************/

# 히프의 시간 복잡도 분석

---

히프의 삽입과 삭제 연산의 시간 복잡도를 분석해보자. 삽입 연산에서 새로운 요소는 가장 밑에 위치하게 되고, 부모 노드와 비교를 하면서 트리를 타고 올라간다. 최악의 경우 루트 노드까지 올라와야 하므로 트리의 높이에 해당하는 비교 연산 및 이동 연산이 필요하다.

 히프가 완전 이진 트리임을 생각하면 히프의 높이는 $log_2n$가 되고 따라서 삽입 연산의 시간 복잡도는 $O(log_2n)$이 된다. 삭제도 마찬가지로 루트 노드부터 자식 노드들과 비교를 하며 내려가는 구조이기 때문에 최악의 경우 역시 트리의 높이에 해당하는 시간이 걸린다. 따라서 삭제도 삽입과 마찬가지로 $log_2n$의 시간이 걸린다.