1. HEAP 힙 요약
힙은 우선순위가 가장 높은 원소가 루트(첫번째 인덱스)에 존재하는 것이 보장된 자료구조입니다. 또한, 부모노드는 자식노드보다 우선순위가 높습니다.(우선순위가 같은 경우가 있을 수는 있음)
힙은 트리로 표현 가능한데, 완전이진트리의 한 종류입니다(자식 최대 2개, 자식은 왼쪽부터 생김)
그리고 힙은 STL의 우선순위 큐랑 같은 것이라고 보시면 됩니다. STL의 우선순위 큐를 사용해도 되지만, 힙의 경우 구현이 간단하므로 직접 구현해서 사용하는 것 좋습니다. 왜냐하면 STL을 사용하는 것 보다는 직접 만들어 사용하면 실행시간을 꽤 많이 줄일 수 있기 때문입니다.
주의) Heap은 전체 원소가 우선순위대로 정렬된 자료구조가 아닙니다. 특정원소의 왼쪽 자식이 오른쪽 자식보다 클 수도 있고, 작을수도 있습니다. 이건 보장되지 않습니다. 모든 원소가 우선순위대로 정렬된 자료구조는 이진탐색트리(ex.레드블랙트리)입니다.
주의) Heap은 중복된 원소를 허용합니다. 그래서 부모와 자식의 우선순위가 동일한 경우가 발생할 수 있습니다. 그렇더라도, 루트에 가장 우선순위가 높은 원소가 존재한다는 사실은 항상 보장되므로 문제가 없습니다.
2. 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)을 줄일 수 있는 방법이 있습니다. 이 방법은 다음 글에서 알려드리도록 하겠습니다.
'자료구조 > HEAP 힙' 카테고리의 다른 글
| 2. 업그레이드 된 HEAP 힙 (특정원소 삭제, 업데이트 O(logN)만에 가능) (0) | 2023.03.12 |
|---|
댓글