힙 (자료 구조) - 위키백과, 우리 모두의 백과사전
[JS] 히프(Heap), 최대 히프와 최소 히프, 우선순위 큐
자료구조 - 우선순위 큐(Priority Queue)와 힙(heap)

개념

최댓값, 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리를 기본으로 한 자료구조

• A가 B의 부모 노드면, A와 B의 키 값 사이에는 대소 관계가 성립
• 자료의 삽입, 삭제 후 항상 힙이 유지되어야 함
• 부모 노드의 우선순위 ≥ 자식 노드의 우선순위

느슨한 정렬 (약한 힙, Weak Heap)

부모와 자식 노드의 우선순위만 신경쓰고 형제간의 우선순위는 고려되지 않음
(가장 아래의 노드가 항상 최솟값이나 최댓값이 아님)

우선순위 큐 (Priority Queue)

• 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것

시간복잡도

• 최소, 최대값을 $O(1)$의 시간복잡도로 얻을 수 있음
• 자료의 삽입, 삭제 시 시간복잡도는 $O(logn)$
  • 우선순위 큐의 삭제 연산 시 모든 노드를 방문해 우선순위가 높은 것을 기억해 놓고 삭제해야 하기 때문에 시간복잡도가 $O(n)$이지만, 힙으로 구현 시 $O(logn)$

이진 트리의 높이가 하나 증가할 때마다 저장 가능한 자료의 개수가 2배 증가하고, 비교 연산 횟수는 1회 증가
최악의 경우 모든 레벨의 탐색해야 하므로 시간 복잡도가 $O(logn)$
노드를 하나 탐색할 때마다 고려해야 할 자료의 크기가 절반으로 줄어듦

숫자가 클수록 우선순위가 높은 문제: 최대 힙 사용
숫자가 작을수록 우선순위가 높은 문제: 최소 힙 사용

최대 힙 (Max Heap)

최대 트리 + 완전 이진 트리

최대 트리

• 루트 노드의 값: 최댓값
• 부모 노드의 키 값 ≥ 자식 노드의 키 값

• 최대 우선순위 큐

최소 힙 (Min Heap)

최소 트리 + 완전 이진 트리

최대 트리

• 루트 노드의 값: 최솟값
• 부모 노드의 키 값 ≤ 자식 노드의 키 값

• 최소 우선순위 큐

구현

부모나 자식의 인덱스를 가지고 서로의 인덱스를 계산할 수 있으므로, 인덱스로 접근이 가능한 배열 리스트로 구현 (루트 노드의 인덱스가 1이고 순서대로 증가)

• 부모 노드의 인덱스가 $n$이면 자식 노드의 인덱스는 $2n$ 또는 $2n + 1$
• 자식 노드의 인덱스가 $n$이면 부모 노드의 인덱스는 $n/2$ (이때, $n > 1$)

자료의 추가, 제거 후에는 힙을 유지할 수 있도록 재구조화(heapify)하는 과정이 필요

구조체와 함수 원형

typedef struct HeapNodeType
{
	int	key;
}	HeapNode;

typedef struct HeapType
{
	int			maxCount;
	int			currentCount;
	HeapNode	*pElement;
}	Heap;

Heap*		createHeap(int maxCount);
void		deleteHeap(Heap **pHeap);
int			insertMaxHeap(Heap *pHeap, HeapNode element);
int			insertMinHeap(Heap *pHeap, HeapNode element);
int			deleteMaxHeapNode(Heap *pHeap);
int			deleteMinHeapNode(Heap *pHeap);
HeapNode	*getMaxHeapNode(Heap *pHeap);
HeapNode	*getMinHeapNode(Heap *pHeap);
int			isHeapFull(Heap *pHeap);
int			isHeapEmpty(Heap *pHeap);
void		displayHeap(Heap *pHeap);

힙 생성

Heap	*createHeap(int maxcount)
{
	Heap	*pHeap;

	pHeap = (Heap *)malloc(sizeof(Heap));
	if (pHeap == NULL)
		return (NULL);
	pHeap->maxCount = maxcount;
	pHeap->currentCount = 0;
	pHeap->pElement = (HeapNode *)malloc(sizeof(HeapNode) * (maxcount + 1));
	if (pHeap->pElement == NULL)
	{
		free(pHeap);
		return (NULL);
	}
	return (pHeap);
}

자료 추가

자료를 추가할 인덱스 찾기
1. 초기 인덱스는 현재 자료 개수 + 1 (말단)
2. 인덱스가 1(루트)이 아니고, 부모 노드와 비교해서 자식 노드가 크면 부모 노드를 현재 인덱스로 복사 (최소 힙은 자식 노드가 작다면 복사)
3. 탐색할 인덱스를 2로 나누기
4. 2, 3 반복

int	insertMaxHeap(Heap *pHeap, HeapNode element)
{
	int	i;
	int	parent_i;

	if (pHeap == NULL || isHeapFull(pHeap))
		return (FALSE);
	pHeap->currentCount++;
	i = pHeap->currentCount;
	parent_i = i / 2;
	while (i > 1 && element.key >= pHeap->pElement[parent_i].key)
	{
		pHeap->pElement[i].key = pHeap->pElement[parent_i].key;
		i /= 2;
		parent_i = i / 2;
	}
	pHeap->pElement[i] = element;
	return (TRUE);
}

int	insertMinHeap(Heap *pHeap, HeapNode element)
{
	int	i;
	int	parent_i;

	if (pHeap == NULL || isHeapFull(pHeap))
		return (FALSE);
	pHeap->currentCount++;
	i = pHeap->currentCount;
	parent_i = i / 2;
	while (i > 1 && element.key <= pHeap->pElement[parent_i].key)
	{
		pHeap->pElement[i].key = pHeap->pElement[parent_i].key;
		i /= 2;
		parent_i = i / 2;
	}
	pHeap->pElement[i] = element;
	return (TRUE);
}

자료 삭제

우선순위가 가장 높은 루트 노드를 삭제
1. 마지막 노드를 루트 노드로 복사
2. 루트 노드와 자식 노드의 값을 비교해서 더 큰 값을 가진 자식과 교환 (최소 힙은 더 작은 자식과 교환)
3. 2 반복

int	deleteMaxHeapNode(Heap *pHeap)
{
	int	index;
	int	left;
	int	right;
	int	big;
	int	tmp;

	if (pHeap == NULL || isHeapEmpty(pHeap))
		return (FALSE);
	index = 1;
	pHeap->pElement[index].key = pHeap->pElement[pHeap->currentCount].key;
	pHeap->currentCount--;
	while (index < pHeap->currentCount)
	{
		left = index * 2;
		right = index * 2 + 1;
		big = left;
		if (right <= pHeap->currentCount && pHeap->pElement[left].key < pHeap->pElement[right].key)
			big = right;
		if (pHeap->pElement[index].key < pHeap->pElement[big].key)
		{
			tmp = pHeap->pElement[index].key;
			pHeap->pElement[index].key = pHeap->pElement[big].key;
			pHeap->pElement[big].key = tmp;
		}
		index = big;
	}
	return (TRUE);
}

int	deleteMinHeapNode(Heap *pHeap)
{
	int	index;
	int	left;
	int	right;
	int	small;
	int	tmp;

	if (pHeap == NULL || isHeapEmpty(pHeap))
		return (FALSE);
	index = 1;
	pHeap->pElement[index].key = pHeap->pElement[pHeap->currentCount].key;
	pHeap->currentCount--;
	while (index < pHeap->currentCount)
	{
		left = index * 2;
		right = index * 2 + 1;
		small = left;
		if (right <= pHeap->currentCount && pHeap->pElement[left].key > pHeap->pElement[right].key)
			small = right;
		if (pHeap->pElement[index].key > pHeap->pElement[small].key)
		{
			tmp = pHeap->pElement[index].key;
			pHeap->pElement[index].key = pHeap->pElement[small].key;
			pHeap->pElement[small].key = tmp;
		}
		index = small;
	}
	return (TRUE);
}

힙 정렬

힙이 빌 때까지 루트 노드를 꺼내오기
1. 정렬할 데이터로 힙 구성
2. 루트 노드에 최댓값(최소 힙의 경우 최솟값)이 들어간 상태이므로 루트 노드를 임시 공간에 복사
3. 루트 노드 자리에 마지막 노드 복사
4. 힙 재구성
5. 임시 공간에 저장된 루트 노드 반환
6. 2~5 반복

👉 오름차순 정렬 (최소 힙의 경우 내림차순)

힙 생성 알고리즘의 시간복잡도는 $O(logn)$
전체 데이터의 개수 $n$개에 대해 힙을 다시 생성하므로 힙 정렬의 시간복잡도는 $O(nlogn)$

HeapNode	*getMaxHeapNode(Heap *pHeap)
{
	int			index;
	int			left;
	int			right;
	int			big;
	int			tmp;
	HeapNode	*rootNode;

	if (pHeap == NULL || isHeapEmpty(pHeap))
		return (NULL);
	index = 1;
	rootNode = (HeapNode *)malloc(sizeof(HeapNode));
	*rootNode = pHeap->pElement[index];
	pHeap->pElement[index] = pHeap->pElement[pHeap->currentCount];
	pHeap->currentCount--;
	while (index < pHeap->currentCount)
	{
		left = index * 2;
		right = index * 2 + 1;
		big = left;
		if (right <= pHeap->currentCount && pHeap->pElement[left].key < pHeap->pElement[right].key)
			big = right;
		if (pHeap->pElement[index].key < pHeap->pElement[big].key)
		{
			tmp = pHeap->pElement[index].key;
			pHeap->pElement[index].key = pHeap->pElement[big].key;
			pHeap->pElement[big].key = tmp;
		}
		index = big;
	}
	return (rootNode);
}

HeapNode	*getMinHeapNode(Heap *pHeap)
{
	int			index;
	int			left;
	int			right;
	int			small;
	int			tmp;
	HeapNode	*rootNode;

	if (pHeap == NULL || isHeapEmpty(pHeap))
		return (NULL);
	index = 1;
	rootNode = (HeapNode *)malloc(sizeof(HeapNode));
	*rootNode = pHeap->pElement[index];
	pHeap->pElement[index] = pHeap->pElement[pHeap->currentCount];
	pHeap->currentCount--;
	while (index < pHeap->currentCount)
	{
		left = index * 2;
		right = index * 2 + 1;
		small = left;
		if (right <= pHeap->currentCount && pHeap->pElement[left].key > pHeap->pElement[right].key)
			small = right;
		if (pHeap->pElement[index].key > pHeap->pElement[small].key)
		{
			tmp = pHeap->pElement[index].key;
			pHeap->pElement[index].key = pHeap->pElement[small].key;
			pHeap->pElement[small].key = tmp;
		}
		index = small;
	}
	return (rootNode);
}

🔗 배열 리스트로 구현한 힙 전체 코드