5주차 자료구조 스터디 - 힙 (heap) & 우선순위 큐 (priority queue)

3주차에 힙정렬을 구현하면서 힙에 대해서 간략하게 정리했었다. 3주차 힙정렬 👉 blahblahlab.tistory.com/33

1) 힙이란 ?

최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)

•  부모노드와 자식노드 사이에 일정한 대소관계가 존재한다. 

•  부모노드가 자식노드보다 더 크면 최대힙(max heap) 

•  부모노드가 자식노드보다 더 작으면 최소힙(min heap)

•  형제끼리는 대소관계가 존재하지 않는다.

•  부모와 자식간의 인덱스는 왼쪽자식 = 2 * 부모노드 , 오른쪽 자식 = 2 * 부모노드 +1 을 성립한다.

그림으로 보는 게 훨씬 직관적이다. 

부모노드가 자식노드보다 큰 최대힙의 경우이다. 형제끼리는 대소관계가 없다.

https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

2) 힙 구현 

힙은 원소의 삽입과 삭제 이렇게  2가지의 기능을 수행해야한다. 
별도의 erase같은 기능 없이 배열의 크기로만 해결한다.  

편의상 힙의 인덱스가 1부터 시작한다두고, 최소힙으로 설정하자.

 

• 삽입

삽입의 시간복잡도가 $log N$ 이다. 

1. 배열의 크기를 뜻하는 n을 하나 늘려준 후, heap[n] 에 새로운 값을 저장해준다. 

2. 새로운 값의 인덱스 n부터 시작해서 올라가면서 부모노드와 비교해준다. 

3. 부모노드와 비교 시 부모노드가 더 크다면 자식노드 중 더 작은 값과 바꿔준 후 , 

    부모노드를 절반으로 나눠 올라가 비교한다.  

4.  부모노드와 비교시 부모노드가 더 작다면 즉, 변화가 일어나지 않는다면 멈춘다. 

    이미 힙상태인 배열에 새로운 배열의 위치를 정해주는 거기 때문에 변화가 일어나지 않는다면 

    그 자리가 새로운 배열의 자리이므로 더 이상 비교해줄 필요가 없다.

새롭게 2가 삽입되었을 때

void push_heap(int value) {
	//새로운 원소를 배열에 추가해준 후, size를 뜻하는 n을 하나 늘려줌
	n++;
	heap[n] = value;
    //힙상태로 만들어주자
	int parent = n / 2;
	while (parent > 0) {
		int temp = parent, left = 2 * parent, right = 2 * parent + 1;
		if (left <= n && heap[left] < heap[temp]) temp = left;
		if (right <= n && heap[right] < heap[temp]) temp = right;
		if (parent != temp) {
			swap(heap[parent], heap[temp]);
			parent /= 2;
		}
		else break;
	}
}

 

 

• 삭제

삭제 또한 시간복잡도가 $log N$ 이다. 

1. 반환해줄 heap[1]을 저장한 후, 배열의 맨 끝으로 보내준다. ->맨 끝값인 heap[n]과 swap해주면 됨   

맨 끝값은 없다고 생각할 거기 때문에 n을 하나 줄여준다.  

2. 인덱스가 1인 부모노드부터 시작해서 아래로 내려가며 자식노드와 비교해준다. 

3. 자식노드와 비교 시 자식노드가 더 작다면 자식노드 중 더 작은 값과 바꿔준 후 , 바뀐 자식노드를 부모노드로 해 내려가며 비교한다.

4. 자식노드와 비교시 자식노드가 더 크다면 즉, 변화가 일어나지 않는다면 멈춘다. 이미 힙상태인 배열에 새로운 배열의 위치를 정해주는 거기 때문에 변화가 일어나지 않는다면 그 자리가 새로운 배열의 자리이므로 더 이상 비교해줄 필요가 없다. 

5. while문을 탈출한 후 1번에서 저장해주었던 값을 반환해준다. 

 

 

이 코드에서는 힙이 비었을 때 0을 반환하도록 되어있다!  이 부분은 문제에 따라 바꾸면 된다. 

int pop_heap() {
	//첫 번째 원소랑 맨 마지막 원소랑 바꿔치기 후 맨 마지막 원소 이전으로만 바라보기 위해 n을 하나 줄여줌
	if (n == 0) return 0;
	int pop_result = heap[1];
	swap(heap[1], heap[n]);
	n--;
	//다시 힙상태로 만들어주자.
	int parent = 1;
	while (parent <= n / 2) {
		int temp = parent, left = 2 * parent, right = 2 * parent + 1;
		if (left <= n && heap[left] < heap[temp]) temp = left;
		if (right <= n && heap[right] < heap[temp]) temp = right;
		if (parent != temp) {
			swap(heap[parent], heap[temp]);
			parent = temp;
		}
		else break;
	}
	return pop_result;
}

 

3) 힙 예제 

백준 1927번 최소힙 (www.acmicpc.net/problem/1927) 문제다. 

이 문제는 stl로 풀거나 힙을 구현해 풀지 않으면 시간초과가 난다. 

pop을 구현하지 않고 그냥 erase를 썼더니 erase의 시간복잡도가 logN이라 시간초과가 났다.

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

int heap[1000000]; //힙배열
int n = 0; //힙 사이즈 


void push_heap(int value) {
	//새로운 원소를 배열에 추가해준 후, size를 뜻하는 n을 하나 늘려줌
	n++;
	heap[n] = value;
	int parent = n / 2;

	while (parent > 0) {
		int temp = parent, left = 2 * parent, right = 2 * parent + 1;
		if (left <= n && heap[left] < heap[temp]) temp = left;
		if (right <= n && heap[right] < heap[temp]) temp = right;
		if (parent != temp) {
			swap(heap[parent], heap[temp]);
			parent /= 2;
		}
		else break;
	}
}

int pop_heap() {
	//첫 번째 원소랑 맨 마지막 원소랑 바꿔치기 후 맨 마지막 원소 이전으로만 바라보기 위해 n을 하나 줄여줌
	if (n == 0) return 0;
	int pop_result = heap[1];
	swap(heap[1], heap[n]);
	n--;
	//다시 힙상태로 만들어주자.
	int parent = 1;
	while (parent <= n / 2) {
		int temp = parent, left = 2 * parent, right = 2 * parent + 1;
		if (left <= n && heap[left] < heap[temp]) temp = left;
		if (right <= n && heap[right] < heap[temp]) temp = right;
		if (parent != temp) {
			swap(heap[parent], heap[temp]);
			parent = temp;
		}
		else break;
	}
	return pop_result;
}


int main() {
	heap[0] = 0;
	int N;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int value;
		scanf("%d", &value);
		if (!value) printf("%d\n", pop_heap());
		else push_heap(value);
	}
}

4 ) 우선순위 큐란 ?

• 큐는 FIFO로 먼저 들어온 원소가 먼저 나가는 형태이다.

  우선순위 큐는 말 그대로 큐에다가 우선순위의 개념을 적용한 자료구조다. 우선순위가 높은 순서대로 나가게 된다.

EX ) 1 9 7 2 순서대로 입력됐다면 출력되는 순서는 

큐 : 1 9 7 2

우선순위 큐 (최소) : 1 2 7 9 

 

• 우선순위는 greater, less 같이 오름차순,내림차순이 가능하고, sort와 비슷하게 사용자 비교연산자를 따로 만들어 오버라이딩 시켜도 된다. 
•  우선순위 큐를 구현하는데 배열 ,연결 리스트 ,힙 이렇게 세가지 방법이 있다. 

	삽입	삭제
배열	O(N)	O(1)
연결 리스트	O(N)	O(1)
힙	O(log N)	O(log N)

삭제는 배열이나 연결리스트가 훨씬 빠르지만 삽입은 힙이 더 빠르므로, 삽입과 삭제에 걸리는 시간이 똑같은 힙으로 구현하는 것이 보통이다. 

 

• STL의 기능으로는 push, pop , top , empty , size 가 있다. 

우선순위 큐 구현을 힙으로 하면 위에서 구현했던 힙코드에 

1. heap[1] 을 반환하는 top()

2. 힙의 사이즈 n 이 0이라면 1을 반환하고 0이 아니라면 0을 반환하는 empty()

3. 힙의 사이즈 n을 반환하는 size()

세 개만 추가해주면 된다. 

int heap[1000000]; //힙배열
int n = 0; //힙 사이즈 


void push(int value) {
	//새로운 원소를 배열에 추가해준 후, size를 뜻하는 n을 하나 늘려줌
	n++;
	heap[n] = value;
	int parent = n / 2;

	while (parent > 0) {
		int temp = parent, left = 2 * parent, right = 2 * parent + 1;
		if (left <= n && heap[left] < heap[temp]) temp = left;
		if (right <= n && heap[right] < heap[temp]) temp = right;
		if (parent != temp) {
			swap(heap[parent], heap[temp]);
			parent /= 2;
		}
		else break;
	}
}

int pop() {
	//첫 번째 원소랑 맨 마지막 원소랑 바꿔치기 후 맨 마지막 원소 이전으로만 바라보기 위해 n을 하나 줄여줌
	if (n == 0) return 0;
	int pop_result = heap[1];
	swap(heap[1], heap[n]);
	n--;
	//다시 힙상태로 만들어주자.
	int parent = 1;
	while (parent <= n / 2) {
		int temp = parent, left = 2 * parent, right = 2 * parent + 1;
		if (left <= n && heap[left] < heap[temp]) temp = left;
		if (right <= n && heap[right] < heap[temp]) temp = right;
		if (parent != temp) {
			swap(heap[parent], heap[temp]);
			parent = temp;
		}
		else break;
	}
	return pop_result;
}

int top() {
	return heap[1];
}

int empty() {
	if (n == 0) return 1;
	return 0;
}

int size() {
	return n;
}