1. HEAP 힙 요약
힙은 우선순위가 가장 높은 원소가 루트(첫번째 인덱스)에 존재하는 것이 보장된 자료구조입니다. 또한, 부모노드는 자식노드보다 우선순위가 높습니다.(우선순위가 같은 경우가 있을 수는 있음)
힙은 트리로 표현 가능한데, 완전이진트리의 한 종류입니다(자식 최대 2개, 자식은 왼쪽부터 생김)
그리고 힙은 STL의 우선순위 큐랑 같은 것이라고 보시면 됩니다. STL의 우선순위 큐를 사용해도 되지만, 힙의 경우 구현이 간단하므로 직접 구현해서 사용하는 것 좋습니다. 왜냐하면 STL을 사용하는 것 보다는 직접 만들어 사용하면 실행시간을 꽤 많이 줄일 수 있기 때문입니다.
주의) Heap은 전체 원소가 우선순위대로 정렬된 자료구조가 아닙니다. 특정원소의 왼쪽 자식이 오른쪽 자식보다 클 수도 있고, 작을수도 있습니다. 이건 보장되지 않습니다. 모든 원소가 우선순위대로 정렬된 자료구조는 이진탐색트리(ex.레드블랙트리)입니다.
주의) Heap은 중복된 원소를 허용합니다. 그래서 부모와 자식의 우선순위가 동일한 경우가 발생할 수 있습니다. 그렇더라도, 루트에 가장 우선순위가 높은 원소가 존재한다는 사실은 항상 보장되므로 문제가 없습니다.
2. HEAP 연산 시간 복잡도
힙의 전체 원소수가 N일때,
1)push(힙에 원소 하나 추가하기) : O(logN)
2)pop(힙의 루트 원소 뽑아내기) : O(logN)
3)top(힙의 루트 원소 값만 가져오기) : O(1)
3. C언어로 구현한 힙
힙은 완전이진트리의 한 종류입니다. 완전이진트리는 배열로 깔끔하게 표현가능합니다. 그래서 heap도 배열로 구현하면 깔끔하게 구현할 수 있습니다.
루트의 인덱스는 1부터 시작합니다. 이 경우, 특정노드의 인덱스를 i라고 했을 때,
특정노드의 왼쪽 자식노드의 인덱스는 2×i 로 표현가능합니다.
특정노드의 오른쪽 자식노드의 인덱스는 2×i+1로 표현가능합니다.
특정노드의 부모 노드의 인덱스는 i/2로 표현가능합니다.
힙을 구현할 때 주의할 점은 인덱스가 유효범위를 벗어나지 않는지를 항상 확인해야 한다는 것입니다. 만약에 인덱스가 1보다 작거나, 힙 사이즈보다 클 경우 오류를 발생시키는 우선순위 비교가 발생하므로 매우 주의해야합니다.
아래 코드는 C언어로 구현한 힙입니다. 실제 문제풀이에서는 아래 코드처럼 구조체를 만들고, 구조체의 몇 개의 필드들의 크기를 기준으로 우선순위를 설정하는 경우가 많습니다.
#include<stdio.h> //인덱스 1부터 시작하는 힙
const int MAXN = 1000;
typedef struct _Data {
int id;
int p1;
int p2;
int num;
}Data;
Data temp;
Data heap[MAXN];
int heapSize = 0;
//p1 큰게 앞에, p1이 같다면 p2 큰게 앞에 오는 힙 만든다.
int comparePriority(int index1, int index2) {
return (heap[index1].p1 > heap[index2].p1) ||
((heap[index1].p1 == heap[index2].p1) && (heap[index1].p2 > heap[index2].p2));
}
void heapInit() {
heapSize = 0;
}
void push(Data data) {
heap[++heapSize] = data;
int curIndex = heapSize;
int parentIndex = (curIndex >> 1); // curIndex/2
while (parentIndex > 0 && comparePriority(curIndex, parentIndex)) {
temp = heap[curIndex];
heap[curIndex] = heap[parentIndex];
heap[parentIndex] = temp;
curIndex = parentIndex;
parentIndex = (curIndex >> 1);
}
}
Data top() {
if (heapSize == 0)return { -1,-1,-1,-1 };
return heap[1];
}
Data pop() {
if (heapSize == 0)return { -1,-1,-1,-1 };
Data ret = heap[1];
heap[1] = heap[heapSize--];
int curIndex = 1;
int childIndex = (curIndex << 1); // curIndex*2
while (childIndex <= heapSize) {
if (childIndex + 1 <= heapSize) {
childIndex = comparePriority(childIndex, childIndex + 1) ? childIndex : childIndex + 1;
}
if (comparePriority(curIndex, childIndex))break;
temp = heap[curIndex];
heap[curIndex] = heap[childIndex];
heap[childIndex] = temp;
curIndex = childIndex;
childIndex = (curIndex << 1); //curIndex*2
}
return ret;
}
int main(void) {
push({ 1,1,1,100 });
push({ 2,1,2,100 });
push({ 3,2,1,100 });
push({ 4,2,2,100 });
push({ 5,3,1,100 });
Data ans = pop(); printf("id: %d, p1: %d, p2: %d, num: %d\n", ans.id, ans.p1, ans.p2, ans.num);
ans = pop(); printf("id: %d, p1: %d, p2: %d, num: %d\n", ans.id, ans.p1, ans.p2, ans.num);
ans = pop(); printf("id: %d, p1: %d, p2: %d, num: %d\n", ans.id, ans.p1, ans.p2, ans.num);
ans = pop(); printf("id: %d, p1: %d, p2: %d, num: %d\n", ans.id, ans.p1, ans.p2, ans.num);
ans = pop(); printf("id: %d, p1: %d, p2: %d, num: %d\n", ans.id, ans.p1, ans.p2, ans.num);
/*
id: 5, p1 : 3, p2 : 1, num : 100
id : 4, p1 : 2, p2 : 2, num : 100
id : 3, p1 : 2, p2 : 1, num : 100
id : 2, p1 : 1, p2 : 2, num : 100
id : 1, p1 : 1, p2 : 1, num : 100
*/
return 0;
}4. 만약 Heap 내의 특정 원소를 삭제하거나, 값을 수정하고 싶다면?
push와 pop 연산을 활용해서 heap내의 특정 원소를 삭제하거나 수정하고 싶다면 어떻게 해야 할까요?
(1) 첫 번째 시도
먼저, 특정원소 삭제의 경우 heap은 루트 원소의 값에만 접근이 가능하다는 점을 알고 있습니다. 그러므로 가장 쉽게 생각할 수 있는 방법은 원하는 원소를 찾을 때까지 계속 pop을 시키는 것입니다. 그러다 원하는 원소를 찾는다면, 그 이전에 pop시켰던 원소들을 다시 heap에 push 해주면 됩니다.
특정원소 업데이트의 경우, 위의 방법과 비슷하게 원하는 원소를 찾을 때까지 계속 pop시킨 뒤, 원하는 원소를 찾으면, 그 원소의 값을 수정하고, pop시켰던 원소들을 다시 heap에 push 해주면 됩니다.
그런데, 시간복잡도를 생각해보도록 하겠습니다. 두 경우 모두 최악의 경우는, 찾는 원소가 heap의 맨 뒤에 존재하는 경우입니다. 이 경우 pop을 N번 수행해야합니다. pop 1회의 시간복잡도가 O(logN)이므로, O(NlogN)만큼 소요됩니다.
그 다음, push의 경우도 특정원소 삭제기능의 경우, N-1번 해줘야 하고, 특정원소 값 수정기능의 경우 N번 해줘야 합니다. push 1회의 시간복잡도가 O(logN)이므로, (N-1은 N으로 생각) 두 기능 모두 push에서 O(NlogN)이 소요됩니다.
그래서 결론적으로 특정원소 삭제의 경우 2×O(NlogN) , 특정원소 값 수정의 경우도 2×O(NlogN)의 시간이 소요됩니다.
그래서, 문제 풀이시 시간제한에 걸릴 위험이 있습니다.
(2) 조금 더 나은 두 번째 시도
우리는 배열로 HEAP을 구현했습니다. 그러므로 그냥 배열 첫번째 인덱스부터 쭈욱 보면서 원하는 원소를 찾을 수 있습니다. 이 경우 O(N)의 시간이 걸립니다. 해당하는 원소를 조작하면 그 원소를 삭제시키거나 값을 업데이트 할 수 있습니다.
-삭제의 경우: 해당 원소가 root까지 올라올 수 있도록 우선순위를 가장 높게 값들을 변경시킨 뒤 루트로 올려보냅니다. 그 다음 pop 연산을 수행합니다. 결과적으로 특정 원소 삭제가 수행되었습니다. 해당 원소를 root까지 올려보내는 연산(O(logN)), pop연산(O(logN)) 총 2×O(logN)만큼 소요됩니다.
-값 변경의 경우: 해당 원소의 값을 변경시킵니다. 해당 원소를 우선순위에 따라 위로 올려보내거나, 아래로 내려보냅니다. 결과적으로 특정 원소의 값도 변경되고, Heap 구조도 유지됩니다. 해당 원소를 올려보내거나 내려보내는 연산에 O(logN)만큼 소요됩니다.
결과적으로 삭제 및 값 변경의 경우 O(N+logN)의 시간이 소요됩니다.
아래 코드는 삭제 및 값 변경에 O(N+logN)이 소요되는 Heap을 구현한 코드입니다. 코드 길이를 줄이기 위해 특정 원소를 우선순위를 비교하면서 아래로 내려주는 함수를 down()으로 따로 빼줬고, 위로 올려주는 함수를 up()으로 따로 빼줬습니다. update()와 remove()함수의 맨 처음을 보시면, Heap 처음부터 끝까지 반복문을 돌리면서 특정 원소를 찾는 코드를 확인하실 수 있습니다.
#include<stdio.h> //힙 응용(특정원소 삭제 O(N+logN), 업데이트 O(N+logN))
#include<unordered_map>
using namespace std;
const int MAX_N = 1000;
struct Student {
int p1, p2, id;
};
Student heap[MAX_N];
int heapSize = 0;
void heapInit() {
heapSize = 0;
}
//p1큰게 앞에, 같다면 p2작은게 앞으로
int cmpStudent(int index1, int index2) {
return (heap[index1].p1 > heap[index2].p1) || ((heap[index1].p1 == heap[index2].p1) && (heap[index1].p2 < heap[index2].p2));
}
void up(int index) {
int cur = index;
int parent = (cur >> 1);
while (parent > 0 && cmpStudent(cur, parent)) {
Student temp = heap[cur];
heap[cur] = heap[parent];
heap[parent] = temp;
cur = parent;
parent = (cur >> 1);
}
}
void down(int index) {
int cur = index;
int child = (cur << 1);
while (child <= heapSize) {
if (child + 1 <= heapSize) {
child = cmpStudent(child, child + 1) ? child : child + 1;
}
if (cmpStudent(cur, child))break;
Student temp = heap[cur];
heap[cur] = heap[child];
heap[child] = temp;
cur = child;
child = (cur << 1);
}
}
void push(Student data) {
heap[++heapSize] = data;
up(heapSize);
}
Student pop() {
Student ret = heap[1];
if (heapSize == 1) {
heapSize--;
}
else {
heap[1] = heap[heapSize--];
}
down(1);
return ret;
}
//id에 해당하는 학생 힙에서 삭제하기
void remove(int id) {
//1.해당 학생의 힙 인덱스 구하기
int index = -1;
for (int i = 1; i <= heapSize; i++) {
if (heap[i].id == id) {
index = i; break;
}
}
//2.그 노드의 우선순위 최대로 만들어주기
heap[index].p1 = 99999; heap[index].p2 = -1;
//3.루트로 올려주자
up(index);
//4. pop해주자
pop();
}
void update(int id, int newP1, int newP2) {
//1.해당 학생의 힙 인덱스 구하기
int index = -1;
for (int i = 1; i <= heapSize; i++) {
if (heap[i].id == id) {
index = i; break;
}
}
//2.그 노드 우선순위 변화시키기
heap[index].p1 = newP1; heap[index].p2 = newP2;
//3.위로 보내기
up(index);
//4. 아래로 보내기
down(index);
}
int main(void) {
heapInit();
int p1 = 1; int p2 = 2; int id = 10;
Student student;
for (int i = 0; i < 10; i++) {
student.p1 = p1; student.p2 = p2; student.id = id;
push(student);
if (i & 1)p1++;
if (p2 == 1)p2 = 2;
else p2--;
id--;
}
// 초기에 전체 pop하면 이 순서임
/*
p1: 5, p2: 1, num: 1
p1: 5, p2: 2, num: 2
p1: 4, p2: 1, num: 3
p1: 4, p2: 2, num: 4
p1: 3, p2: 1, num: 5
p1: 3, p2: 2, num: 6
p1: 2, p2: 1, num: 7
p1: 2, p2: 2, num: 8
p1: 1, p2: 1, num: 9
p1: 1, p2: 2, num: 10
*/
//num=6인 원소 삭제 해보자
remove(6);
/*
p1: 5, p2: 1, num: 1
p1: 5, p2: 2, num: 2
p1: 4, p2: 1, num: 3
p1: 4, p2: 2, num: 4
p1: 3, p2: 1, num: 5
p1: 2, p2: 1, num: 7
p1: 2, p2: 2, num: 8
p1: 1, p2: 1, num: 9
p1: 1, p2: 2, num: 10
*/
//id=5인 원소 update 해보자.
update(5, 10, 1);
for (; heapSize != 0;) {
Student ret = pop();
printf("p1: %d, p2: %d, num: %d\n", ret.p1, ret.p2, ret.id);
}
printf("\n");
/*
p1: 10, p2 : 1, num : 5
p1 : 5, p2 : 1, num : 1
p1 : 5, p2 : 2, num : 2
p1 : 4, p2 : 1, num : 3
p1 : 4, p2 : 2, num : 4
p1 : 2, p2 : 1, num : 7
p1 : 2, p2 : 2, num : 8
p1 : 1, p2 : 1, num : 9
p1 : 1, p2 : 2, num : 10
*/
}(3) 최고의 방법
놀랍게도 특정 원소 삭제, 특정 원소 수정 기능을 O(logN)만에 수행할 수 있는 방법이 있습니다.
O(N+logN)에서 원하는 원소를 찾는데 사용한 O(N)을 줄일 수 있는 방법이 있습니다. 이 방법은 다음 글에서 알려드리도록 하겠습니다.
