Heap(Max Heap, Min Heap)

Heap

영단어 Heap은 '무엇인가를 차곡차곡 쌓아 올린 더미'라는 뜻을 가지고 있다. 아래 그림에서도 볼 수 있듯이, 맨 아래부터 데이터를 차곡차곡 쌓아둔 모양이다.

Heap은 완전 이진트리로 모든 노드가 연속적으로 존재하기 때문에 연결 리스트보다는 배열로 구현하는 것이 효율적이다.
또한 heap은 모든 노드에 저장된 값이 자식 노드에 저장된 값보다 크거나 같은 자료구조이다. 즉, 루트 노드에 저장된 값이 가장 커야 한다.

이처럼 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진트리를 최대 힙(Max Heap)이라고 한다.
이와 반대로, 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리인 최소 힙(Min Heap)도 존재한다.
최소 힙은 특히 shortest job first를 구현할때 매우 유용하다.

 

힙의 특성을 바탕으로 만들어진 자료구조가 우선순위 큐이며, 우선순위 큐는 기본적으로 최대 힙의 형태로 구현되어있다. 

만약 우선순위 큐를 최소 힙 형태로 바꾸고 싶다면 아래와 같이 코드를 작성하면 된다.(C++ 기준)

priority_queue<int, vector<int>, greater<int> > pq;

 

 

 

최대 힙 & 최소 힙

Max Heap에서는 Root node 에 있는 값이 제일 크므로, 최댓값을 찾는데 소요되는 연산의 시간 복잡도는 O(1)이다.
반대로 Min Heap 에서는 최솟값을 찾는데 소요되는 연산의 시간 복잡도가 O(1)이다.
그리고 완전 이진 트리이기 때문에 배열을 사용하여 효율적으로 관리할 수 있다. (= random access 가능)

 

 

 

최대 힙의 삽입

최대 힙은 노드가 삽입된 후에도 완전 이진트리의 조건을 만족해야 한다.
따라서 노드의 삽입 위치는 완전 이진 트리의 조건을 만족시키기 용이한 트리의 가장 마지막 위치가 좋다. 마지막 위치에 노드를 삽입한 후에는 최대 힙의 조건을 만족하도록 상위 노드와 값을 비교하여 재구성하는 과정(heapify)이 필요하다.

최악의 경우는 삽입한 요소가 루트 노드까지 올라가는 경우이므로 $log_{2} N $의 시간복잡도가 발생한다.

1. 최대 힙의 마지막 노드 다음에 새로운 노드 추가
2. 최대 힙 조건을 만족하기 위해 새 노드와 부모 노드의 크기 비교
   if(새 노드 > 부모 노드) swap(새 노드, 부모 노드)
3. 한 단계 상위 레벨로 이동 후 새 노드가 올바른 위치 찾을때까지 과정2 반복

 

 

 

최대 힙 노드 삽입하기

#include <iostream>
using namespace std;

#define MAX 1000 

void heapify(int arr[], int n, int i)
{
	int parent = i/2;
    
	if (arr[parent] > 0) {
		if (arr[i] > arr[parent]) {
			swap(arr[i], arr[parent]);
			heapify(arr, n, parent);
		}
	}
}

void insertNode(int arr[], int& n, int Key)
{
	n = n + 1;
	arr[n] = Key;
	heapify(arr, n, n);
}

void printArray(int arr[], int n)
{
	for (int i = 1; i <= n; ++i)
		cout << arr[i] << " ";

	cout << "\n";
}

int main()
{
	int arr[MAX] = { 0, 10, 5, 3, 2, 4 };
	int n = 5;
	int key = 15;

	insertNode(arr, n, key);
	printArray(arr, n);

	return 0;
}

// 출력: 15 5 10 2 4 3

 

 

 

최대 힙의 삭제

최대 힙에서 노드 삭제는 일반적으로 최댓값인 루트 노드의 삭제를 의미한다. 루트가 삭제된 후에는 다시 최대 힙으로 재구성(heapify)되어야 하기 때문에 시간 복잡도는 트리의 높이에 비례하는 $log_{2} N $이다.

1. 루트 노드의 값을 임시 변수에 복사한뒤 마지막 노드를 루트 노드 위치로 이동
2. 새로운 로트 노드의 좌우 자식 노드 중 값이 큰 노드를 비교할 자식 노드로 지정
3. 부모 노드와 자식 노드를 비교하여 부모 노드의 값이 크면 heapify 종료
4. 자식 노드가 부모 노드보다 더 크면 둘을 swap하고 아래 레벨로 이동한뒤 2~4 반복

 

 

 

최대 힙 노드 삭제하기

#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i)
{
	int largest = i; 
	int l = 2 * i;
	int r = 2 * i + 1; 

	if (l <= n && arr[l] > arr[largest]) largest = l;
	if (r <= n && arr[r] > arr[largest]) largest = r;

	if (largest != i) { 
		swap(arr[i], arr[largest]);
		heapify(arr, n, largest);
	}
}

void deleteRoot(int arr[], int& n)
{
	int lastElement = arr[n];
    
	arr[1] = lastElement;
	n = n - 1;
	heapify(arr, n, 1);
}

void printArray(int arr[], int n)
{
	for (int i = 1; i < n; ++i)
		cout << arr[i] << " ";
	cout << "\n";
}

int main()
{
	int arr[] = { 0, 10, 5, 3, 2, 4 };
	int n = sizeof(arr) / sizeof(arr[0]);

	deleteRoot(arr, n);
	printArray(arr, n);

	return 0;
}

// 출력 : 5 4 3 2

 

 

 

최소 힙의 삽입/삭제

최소 힙의 삽입과 삭제도 루트로 갈수록 작아진다는 특성만 다를 뿐 최대 힙과 비슷하다. 

 

 

 

Heap을 배열로 표현하기

Heap은 완전 이진 트리이기 때문에 배열로 표현하기 용이하다. 따라서 모든 노드를 아래와 같이 인덱스로 접근할 수 있다.

 

arr[1] = 루트 노드
arr[i/2] = 부모 노드
arr[2*i] = 왼쪽 자식 노드
arr[2*i + 1] = 오른쪽 자식 노드

 

 

 

 

References

Heap Data Structure

geeksforgeeks.org/binary-heap

Interview_Question_for_Beginner/tree/master/DataStructure#binary-heap

https://asfirstalways.tistory.com/325

📗 자료구조 개념 및 구현