[자료구조] 힙

CS/자료구조

[자료구조] 힙

nowkoes 2023. 4. 20. 15:26

<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>

힙(Heap)

개요

　우리는 힙 자료구조에 대해 이전에 컨테이너 어댑터 포스팅에서 간략하게 알아본 적이 있다. 특정한 우선순위를 갖는 이 컨테이너에 대해 더욱 자세하게 알아보는 시간을 갖도록 하자.

　힙은 다음과 같은 시간 복잡도 특징을 갖고 있다.

최대/최소 원소에 접근: O(1)
원소 삽입, 삭제: O(logN)

　힙은 다음과 같은 특징이 있다.

부모 노드와 자식 노드의 우선순위는 항상 유지
우선순위가 높은 원소는 항상 루트 노드에 존재

완전 이진 트리(Perfect Binary Tree)

　힙은 원소 삽입 또는 삭제에 대해 O(logN)의 시간 복잡도를 만족해야 하기 때문에 일반적으로 완전 이진트리를 사용해야 한다. 여기서 완전 이진 트리(Complete Binary Tree, 포화 이진트리)는 레벨 순서대로 왼쪽에서 오른쪽 노드가 삽입되는 트리 구조다. 이 트리는 마지막 레벨의 노드를 제외하고는 모두 두 개의 자식 노드가 있고, 마지막 레벨에서는 왼쪽부터 차례대로 노드가 있다.

완전 이진 트리 예시 출처: https://visualgo.net/en/heap

　이에 반해 불완전 이진트리는 이를 만족하지 않는 트리를 의미한다.

불완전 이진 트리 예시 출처: https://visualgo.net/en/bst?slide=3

　완전 이진 트리는 트리의 데이터를 배열을 이용하여 저장할 수 있다는 특징이 있다. 즉, 루트 노드를 배열 맨 처음에 저장하고, 그다음 레벨의 모든 노드는 왼쪽부터 오른쪽 순서로 저장한다는 것이다. 이를 이용하면 부모 노드로부터 자식 노드로 이동하는 것을 배열의 인덱스 계산으로 추론할 수 있다.

　예를 들어 부모 노드가 i번째 배열 원소로 저장되어 있다면 자식 노드는 2i + 1(왼쪽) 또는 2i + 2(오른쪽)에 존재한다는 것이다. 마찬가지로 자식 노드가 i번째 인덱스라면 부모 노드는 (i-1)/2번째 인덱스다.

힙 연산

원소 삽입

　힙에서 새 원소를 삽입하면 단순히 배열의 맨 마지막 위치에 원소를 추가하면 된다. 만약 마지막 레벨이 꽉 차 있다면 새로운 레벨을 추가하여 노드를 추가하면 된다. 그리고 힙의 조건 중 모든 노드는 자식 노드보다 더 큰 값을 갖고 있어야 한다는 것이 있다. 따라서 원소를 삽입하고 나서 힙의 속성을 만족하게 정렬해 주는 과정이 필요하다.

　위의 10부터 1까지 원소를 갖는 완전 이진트리를 예시로, 11을 삽입한다고 가정해 보자.

　마지막 레벨에 추가를 하고, 힙의 조건에 맞게 자리를 바꿔가는 것을 확인할 수 있다.

원소 삭제

　힙에서는 가장 크거나 작은 원소만 삭제할 수 있다. 이를 위해 루트 노드와 트리의 맨 마지막 노드를 서로 교환한 후, 마지막 노드를 삭제해야 한다. 이렇게 되면 부모 노드와 자식 노드 간의 대소 관계가 맞지 않으므로 서브 트리에 대해 노드 교환 작업을 재귀적으로 반복하면 된다.

　11을 삽입한 힙 트리에 대해 11을 삭제한다고 해보자.

　루트 노드를 삭제하고, 마지막 노드와 바꾼 뒤 재귀적으로 트리를 조정하는 것을 확인할 수 있다.

힙 초기화

　이러한 구조를 가진 힙은 불변성을 만족하기 위해 초기화하는 작업이 중요하다는 것을 알 수 있다. 만약 힙에 하나씩 원소를 삽입한다면 시간 복잡도가 O(N logN)이 되지만, 전체 트리의 아래쪽 서브 트리부터 힙을 업데이트하는 방식을 채용한다면 O(N)의 시간 복잡도를 가져 효율적이게 사용할 수 있다. 이러한 알고리즘을 힙 생성 알고리즘(Heapification algorithm)이라고 한다.

　만약 11을 삭제한 힙 트리에 대해 원소 7을 12로 대체한다고 해보자.

　보는 것과 마찬가지로 불변성을 만족하도록 하는 이 알고리즘은 매우 빠른 속도로 진행될 것이라고 예측할 수 있다.

구현

　간략한 구현은 컨테이너 어댑터 포스팅에서 했었다. 이번엔 이 코드에 힙 알고리즘을 넣어 재귀적으로 호출하는 코드를 구현해 보겠다.

#include <iostream>
#include <vector>

template <class T>
class Heap
{
	std::vector<T> _heap;

　먼저 vector를 이용해 구현할 것이므로 다음과 같이 벡터를 초기화해 준다.

	...
	void HeapifyUp(int current)
	{
		int parent = (current - 1) / 2;

		if (current && _heap[parent] < _heap[current])
		{
			std::swap(_heap[current], _heap[parent]);
			HeapifyUp(parent);
		}
	}

public:
	void push(T value)
	{
		_heap.push_back(value);
		int index = _heap.size() - 1;
		HeapifyUp(index);
	}

　배열의 맨 마지막에 값을 추가하는 push() 함수를 구현한다. 이때 값을 넣고 나서 초기화하는 HeapifyUp() 함수를 호출하여 재귀적으로 반복한다.

　값은 맨 마지막 노드에 추가된다. 이때 이 값의 부모의 인덱스는 (인덱스 - 1) / 2가 된다. 이 인덱스와 부모의 값을 계속 비교하며 힙의 조건에 맞게 재귀적으로 호출하며 타고 올라가게 구현하였다.

	...
	void HeapifyDown(int current)
	{
		int left = 2 * current + 1;
		int right = 2 * current + 2;
		int largest = current;

		if (left < _heap.size() && _heap[left] > _heap[current])
			largest = left;

		if (right < _heap.size() && _heap[right] > _heap[largest])
			largest = right;

		if (largest != current)
		{
			std::swap(_heap[current], _heap[largest]);
			HeapifyDown(largest);
		}
	}
    
public:
	...
	void pop()
	{
		_heap[0] = _heap.back();
		_heap.pop_back();
		HeapifyDown(0);
	}

　배열의 가장 큰 값을 삭제하는 pop() 함수다. 이때 원소를 제거하고 초기화하는 HeapifyDown() 함수를 호출하여 재귀적으로 반복하게 구현하였다.

　루트 노드와 마지막 레벨의 노드를 교환하여 삭제한 뒤, 가장 큰 값이 루트 노드가 되어야 하므로 왼쪽 값과 오른쪽 값을 계속 비교하며 바꿔준다. 가장 큰 값의 인덱스와 현재 인덱스가 같아지면 함수는 동작을 종료한다.

public:
	...
	T top()
	{
		return _heap.at(0);
	}

	bool empty()
	{
		return _heap.empty();
	}
};

　가장 큰 값을 출력하는 top() 함수와, 비어있는지 확인하는 empty() 함수를 작성하였다.

총합본

#include <iostream>
#include <vector>

template <class T>
class Heap
{
	std::vector<T> _heap;

	void HeapifyDown(int current)
	{
		int left = 2 * current + 1;
		int right = 2 * current + 2;
		int largest = current;

		if (left < _heap.size() && _heap[left] > _heap[current])
			largest = left;

		if (right < _heap.size() && _heap[right] > _heap[largest])
			largest = right;

		if (largest != current)
		{
			std::swap(_heap[current], _heap[largest]);
			HeapifyDown(largest);
		}
	}

	void HeapifyUp(int current)
	{
		int parent = (current - 1) / 2;

		if (current && _heap[parent] < _heap[current])
		{
			std::swap(_heap[current], _heap[parent]);
			HeapifyUp(parent);
		}
	}

public:
	void push(T value)
	{
		_heap.push_back(value);
		int index = _heap.size() - 1;
		HeapifyUp(index);
	}

	void pop()
	{
		_heap[0] = _heap.back();
		_heap.pop_back();
		HeapifyDown(0);
	}

	T top()
	{
		return _heap.at(0);
	}

	bool empty()
	{
		return _heap.empty();
	}
};

int main()
{
	Heap<int> h;
	h.push(100);
	h.push(500);
	h.push(600);
	h.push(200);
	h.push(400);

	while (!h.empty())
	{
		int value = h.top();
		h.pop();

		std::cout << value << ' ';
	}
	std::cout << std::endl;
}

요약

힙(Heap)
1. 정의: 최대/최소 값을 루트 노드로 갖는 구조.
2. 특징
　a. 최댓값, 최솟값 추출 O(logN) / 접근 O(1)
　b. 완전 이진 트리 형태
　c. 부모 노드는 자식 노드보다 항상 큰/작은 값
3. 자식과 부모의 관계
　a. 부모: i -> 자식: 2i + 1, 2i + 2
　b. 자식: i -> 부모: (i - 1) / 2
4. 종류
　a. 최대 힙(Max Heap)
　b. 최소 힙(Min Heap)

저작자표시 비영리 변경금지

'CS > 자료구조' 카테고리의 다른 글

[자료구조] 해시 테이블 (1) (0)	2023.04.26
[자료구조] 그래프 (0)	2023.04.24
[자료구조] 이진 탐색 트리 (2) - 구현 (0)	2023.04.20
[자료구조] 이진 탐색 트리 (1) (0)	2023.04.19
[자료구조] 트리 순회(Tree traversal) (0)	2023.04.17

현재글[자료구조] 힙

개발일지