참고
- 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기
- 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기
- 우선순위 큐 임의 원소 갱신, 변경
[수정]
항상감사합니다.님의 의견에 따라 방어코드가 필요한 것을 확인하였습니다.
제 코드는 update할 index = updatehn이 updatehn * 2 == hn(힙의 현재 크기)인 경우 문제가 발생합니다.
PRO 시험에 제 코드를 사용하시는 분들은 아래 추가된 글 참고 부탁드립니다.
Indexed Priority Queue, Heap - update 구현
우선순위 큐의 삭제에서 O(logN)으로 (id가 유일하면) 우선순위 큐의 원소를 삭제할 수 있었다.
삭제의 원리는 아래와 같다.
1) heap index를 heapIdx[] 배열에 저장해둔다.
2) heap에 바로 접근하여 값을 최고의 우선순위가 되도록 변경한다.
3) 위로 갱신한다.
4) pop한다.
위의 원리에서, 최고의 우선순위가 아니라 갱신할 값을 변경하고, 도중에 멈춘다면?
바로 우선순위 큐의 update가 된다.
1) heap index를 heapIdx[] 배열에 저장해둔다.
2) heap에 바로 접근하여 값을 원하는 값(갱신할 값)으로 변경한다.
3) 위로 갱신하거나 아래로 갱신한다.
4) pop한다.
update의 핵심은 pop하지 않는 것이다.
delete의 경우 필요 없는 원소이기 때문에 pop하여 제거하였지만,
원하는 값으로 변경한 후에 pop하지 않으면 여전히 우선순위 큐에 남아 있기 때문에 update가 완료된다.
delete의 경우는 반드시 pop하기 때문에 최고의 우선순위로 변경하여 위로 올려보냈다.
하지만 update의 경우는 위나 아래로 이동할 수 있으므로, 둘 다 해본다.
다시 우선 순위 큐의 임의 원소 삭제로 돌아가서 아래의 경우를 보자.
삭제에서는 id가 3인 학생의 점수(value)를 -1로 변경하였다.
이번에는 id가 4인 학생의 점수 5를 1로 변경해보자.
우선순위가 변경되었으므로, 우선순위를 갱신한다.
id가 3이고 점수가 3인 node보다 우선순위가 높으므로 heap이 교체된다.
다시 id가 11, 점수가 2인 node보다 우선순위가 높으므로 heap이 교체된다.
id가 15, 점수가 0인 node보다는 우선순위가 낮기 때문에 멈추게 된다.
update의 코드를 한번 살펴보자.
void update(HEAP* heap, int& hn, int id, int* heapIdx, int value)
{
HEAP tmp;
/* int ret; */
int updatehn = heapIdx[id]; // findIndex(id);
heap[updatehn].value = value;
for (int i = updatehn; i > 1; i /= 2)
{
if (isMin(heap[i / 2], heap[i])) break;
tmp = heap[i];
heap[i] = heap[i / 2];
heap[i / 2] = tmp;
heapIdx[heap[i].id] = i;
heapIdx[heap[i / 2].id] = i / 2;
}
/* pop(heap, hn, heapIdx); */
/* return ret; */
}
update는 return할 것이 따로 없으므로, ret, return ret은 지운다.
마찬가지로, pop은 갱신이 완료되고 delete 하기 위한 코드이므로 지운다.
그 외에는 deleteId와 같다. (delhn → updatehn으로 이름 변경)
즉, 우선순위를 변경하여 위로 올리고 if (isMin(heap[i / 2], heap[i])) break; 에 의해 적절한 위치에서 멈추게 된다.
하지만 이 코드는 아직 불완전하다.
왜냐하면, 점수가 낮아지는 경우(우선순위가 높아지는 경우)만 update가 가능하기 때문이다.
점수가 높아지면 우선순위가 낮아지므로, 아래로 교체되는 경우도 구현해야 한다.
위로 올라가는 경우는 push를 이용하였으므로, 아래로 내려가는 경우는 pop을 이용하면 된다.
먼저 그림으로 살펴보자.
id가 5인 학생의 점수를 2에서 4로 변경하자.
자식 node보다 우선순위가 낮아졌으므로(점수가 높아졌으므로) heap의 아래로 내려가야 한다.
pop에서 자식 node 중 우선순위가 더 높은 자식과 교체하므로, 여기서도 그렇게 한다.
왼쪽 자식 node(id = 2)는 점수가 5고,
오른쪽 자식 node(id = 6)의 점수는 3이기 때문에 오른쪽 heap과 교체 된다.
다시 자식 node와 우선순위를 비교해보자.
왼쪽 자식 node(id = 14)는 점수가 7이기 때문에 교체할 필요가 없다.
오른쪽 자식 node(id = 7)과 점수가 같지만, id가 더 낮기 때문에 교체할 필요가 없다.
update가 완료 되었다.
void update(HEAP* heap, int& hn, int id, int* heapIdx, int value)
{
HEAP tmp;
/* int ret; */
int updatehn = heapIdx[id]; // findIndex(id);
heap[updatehn].value = value;
/* 위로 교체 */
for (int i = updatehn; i > 1; i /= 2)
{ ... }
/* 아래로 교체 */
/* i * 2 => i * 2 + 1이 된다. pop을 하지 않기 때문에 update이므로 index 관리가 필요. */
for (int i = updatehn; i * 2 + 1 <= hn;)
{
if (isMin(heap[i], heap[i * 2]) && isMin(heap[i], heap[i * 2 + 1])) break;
else if (isMin(heap[i * 2], heap[i * 2 + 1]))
{
tmp = heap[i * 2];
heap[i * 2] = heap[i];
heap[i] = tmp;
heapIdx[heap[i].id] = i;
heapIdx[heap[i * 2].id] = i * 2;
i = i * 2;
}
else
{
tmp = heap[i * 2 + 1];
heap[i * 2 + 1] = heap[i];
heap[i] = tmp;
heapIdx[heap[i].id] = i;
heapIdx[heap[i * 2 + 1].id] = i * 2 + 1;
i = i * 2 + 1;
}
}
/* pop(heap, hn, heapIdx); */
/* return ret; */
}
pop의 로직을 이전의 update의 아랫 부분에 추가해주면 된다.
여기서 주의할 점이 두 가지가 있다.
1) pop에서는 for (int i = hn; i * 2 <= hn;) 이지만
update에서는 for (int i = updatehn; i * 2 + 1 <= hn;) 이다.
pop에서는 원소 1개를 반드시 없애므로, hn--로 hn의 값을 줄였었다.
하지만 update는 갱신만 하므로 i * 2를 그대로 놔두면 안된다.
2) 위로 올라갈지, 아래로 올라갈지 모르기 때문에, 두 코드를 모두 추가해야 한다.
여기서 알아야 할 점은, 어떤 heap의 값이 변경되었더라도,
위로 올라가거나 아래로 올라가는 것 둘 중 하나만 실행된다는 점이다.
이미 변경된 heap외에는 우선순위가 유지되어있기 때문이다.
(삭제의 원리가 heap을 갱신하는 과정 중 하나로 볼 수 있기 때문인 것과 비슷한 원리이다.)
덕분에 위로 올라가는 경우, 아래로 올라가는 경우의 update를 따로 구현할 필요는 없다.
최종 코드는 아래와 같다. 학생의 점수를 변경하면서 실제 heap이 변경되는 것을 확인해보자.
#include <stdio.h>
typedef struct st
{
int value;
int id;
}HEAP;
HEAP heap[16];
int heapIdx[16]; /* id가 heap의 어느 위치에 있는지 저장할 배열 */
int hn;
int isMin(HEAP a, HEAP b)
{
if (a.value < b.value) return 1;
else if (a.value == b.value && a.id < b.id) return 1;
return 0;
}
void output(HEAP* heap)
{
for (int i = 1; i <= 15; i++)
{
printf("%d (id : %d) ", heap[i].value, heap[i].id);
if ((i & (i + 1)) == 0) putchar('\n');
}
putchar('\n');
}
void outputHeapIdx(int* heapIdx)
{
for (int i = 1; i <= 15; i++) printf("%d ", heapIdx[i]);
putchar('\n');
}
HEAP pop(HEAP* heap, int& hn, int* heapIdx)
{
register HEAP tmp, ret;
ret = heap[1];
heap[1] = heap[hn];
heap[hn].value = 0x7fff0000;
heap[hn--].id = 0x7fff0000;
for (register int i = 1; i * 2 <= hn;)
{
if (isMin(heap[i], heap[i * 2]) && isMin(heap[i], heap[i * 2 + 1])) break;
else if (isMin(heap[i * 2], heap[i * 2 + 1]))
{
tmp = heap[i * 2];
heap[i * 2] = heap[i];
heap[i] = tmp;
heapIdx[heap[i].id] = i;
heapIdx[heap[i * 2].id] = i * 2;
i = i * 2;
}
else
{
tmp = heap[i * 2 + 1];
heap[i * 2 + 1] = heap[i];
heap[i] = tmp;
heapIdx[heap[i].id] = i;
heapIdx[heap[i * 2 + 1].id] = i * 2 + 1;
i = i * 2 + 1;
}
}
return ret;
}
void push(HEAP* heap, int& hn, int value, int id, int* heapIdx)
{
register HEAP tmp;
heap[++hn].value = value;
heap[hn].id = id;
heapIdx[id] = hn;
for (register int i = hn; i > 1; i /= 2)
{
if (isMin(heap[i / 2], heap[i])) break;
tmp = heap[i / 2];
heap[i / 2] = heap[i];
heap[i] = tmp;
heapIdx[heap[i].id] = i;
heapIdx[heap[i / 2].id] = i / 2;
}
}
void update(HEAP* heap, int& hn, int id, int* heapIdx, int value)
{
HEAP tmp;
/* int ret; */
int updatehn = heapIdx[id]; // findIndex(id);
heap[updatehn].value = value;
for (int i = updatehn; i > 1; i /= 2)
{
if (isMin(heap[i / 2], heap[i])) break;
tmp = heap[i];
heap[i] = heap[i / 2];
heap[i / 2] = tmp;
heapIdx[heap[i].id] = i;
heapIdx[heap[i / 2].id] = i / 2;
}
/* i * 2 => i * 2 + 1이 된다. pop을 하지 않기 때문에 update이므로 index 관리가 필요. */
for (int i = updatehn; i * 2 + 1 <= hn;)
{
if (isMin(heap[i], heap[i * 2]) && isMin(heap[i], heap[i * 2 + 1])) break;
else if (isMin(heap[i * 2], heap[i * 2 + 1]))
{
tmp = heap[i * 2];
heap[i * 2] = heap[i];
heap[i] = tmp;
heapIdx[heap[i].id] = i;
heapIdx[heap[i * 2].id] = i * 2;
i = i * 2;
}
else
{
tmp = heap[i * 2 + 1];
heap[i * 2 + 1] = heap[i];
heap[i] = tmp;
heapIdx[heap[i].id] = i;
heapIdx[heap[i * 2 + 1].id] = i * 2 + 1;
i = i * 2 + 1;
}
}
/* pop(heap, hn, heapIdx); */
/* return ret; */
}
int main(void)
{
int input[] = { 6, 5, 3, 5, 2, 3, 4, 5, 6, 7, 2, 5, 6, 7, 0 };
int size = sizeof(input) / sizeof(int);
for (int i = 0; i < size; i++) push(heap, hn, input[i], i + 1, heapIdx);
update(heap, hn, 4, heapIdx, 1); /* id가 4인 학생의 점수를 1로 교체 */
update(heap, hn, 5, heapIdx, 4); /* id가 5인 학생의 점수를 4로 교체 */
output(heap); printf("\n");
outputHeapIdx(heapIdx);
return 0;
}우선순위 큐의 갱신 문제는 BOJ 20920 : 영단어 암기는 괴로워를 연습해보자.
+ 수정
위 코드는 update할 heapIndex = updatehn 이 updatehn * 2 == hn인 경우에 문제가 발생한다.
아래의 예시를 보자.
id = value이고 {1, 2, 3, 4, 5, 6}이 heap에 들어있는 경우를 그림으로 그리면 아래와 같다.
따라서 현재 hn은 6이다.
이제 id = 3인 값을 8로 변경해보자.
즉 updatehn = 3, 3 * 2 == 6을 만족한다.
update가 되면 id = 6과 id = 3의 위치가 변경되어야 한다.
하지만 아래의 코드를 실행해서 output(heap)을 확인해보면 힙이 갱신되지 않는 것을 확인할 수 있다.
int main(void)
{
int input[] = { 1, 2, 3, 4, 5, 6 };
int size = sizeof(input) / sizeof(int);
for (int i = 0; i < size; i++) push(heap, hn, input[i], i + 1, heapIdx);
update(heap, hn, 3, heapIdx, 8); /* id가 3인 학생의 점수를 8로 교체 */
output(heap); printf("\n");
outputHeapIdx(heapIdx);
return 0;
}
문제가 되는 코드는 update 함수의 pop이 된다.
update * 2 + 1 <= hn → 3 * 2 + 1 <= 6 의 조건을 만족하지 않기 때문에 힙이 갱신되지 않는다.
( {1, 2, 3, 4, 5, 6, 7} 로 tc를 만들면 아무 이상 없다.)
void update(HEAP* heap, int& hn, int id, int* heapIdx, int value)
{
HEAP tmp;
...
/* i * 2 => i * 2 + 1이 된다. pop을 하지 않기 때문에 update이므로 index 관리가 필요. */
for (int i = updatehn; i * 2 + 1 <= hn;)
pop을 하지 않기 때문에 i * 2 → i * 2 + 1로 수정이 필요하다고 생각하였지만, 예외처리 경우가 생기게 되었다.
+ 방어코드
세 가지 방어 코드가 있다.
1. 항상감사합니다.님 의견
항상감사합니다.님의 의견에 따라 update의 pop 코드에서 i를 뺀 후, 아래 코드를 추가한다.
void update(HEAP* heap, int& hn, int id, int* heapIdx, int value)
{
HEAP tmp;
...
int i;
for (i = updatehn; i * 2 + 1 <= hn;)
{
...
}
/* 방어코드 추가 */
if (i * 2 <= hn)
{
if (isMin(heap[i], heap[i * 2])) return;
tmp = heap[i * 2];
heap[i * 2] = heap[i];
heap[i] = tmp;
heapIdx[heap[i].id] = i;
heapIdx[heap[i * 2].id] = i * 2;
}
/* pop(heap, hn, heapIdx); */
/* return ret; */
}
즉, 위의 case에 대해 한번 더 node를 체크하는 코드를 추가하면 된다.
2. isMin 코드의 추가
문제가 되는 코드는
i * 2 => i * 2 + 1이 된다. pop을 하지 않기 때문에 update이므로 index 관리가 필요의 로직이 틀렸기 대문이다.
따라서 i * 2 + 1 → i * 2로 그대로 두고 isMin 코드를 변경한다.
i * 2로 변경하면서 생기는 문제는 updatehn이 오른쪽의 node를 검사해서는 안되지만, 검사하는 경우 발생하게 된다.
현재, updatehn * 2 == hn일 때 i * 2(왼쪽 node)만 비교하여야 하지만, i * 2 + 1(오른쪽 node)도 비교를 하고 있다.
실제 아래의 heap에서 7번째 node는 아무것도 없는 것이 아니라 초기화된 값인 0이 들어가있다.
update할 경우 i * 2 + 1의 node도 검사하기 때문에, 0 / 0 으로 된 값이 우선순위가 높아져 8 / 3이 0 / 0과 교체된다.
따라서 isMin 코드에서 heap이 변경되지 않은 경우(id == 0)는 교체되지 않도록 코드를 수정한다.
위 case의 경우 id가 0인 경우는 비교할 필요가 없는 node이므로 아래와 같이 고칠 수 있다.
int isMin(HEAP a, HEAP b)
{
if (b.id == 0) return 1; /* 비교가 불필요한 heap */
if (a.value < b.value) return 1;
else if (a.value == b.value && a.id < b.id) return 1;
return 0;
}
/* i * 2 + 1 -> i * 2로 수정 */
void update(HEAP* heap, int& hn, int id, int* heapIdx, int value)
{
HEAP tmp;
...
//for (int i = updatehn; i * 2 + 1 <= hn;)
for (int i = updatehn; i * 2 <= hn;)
{3. 우선순위 큐의 초기화
좀 더 간단하게 우선순위 큐를 최악의 값으로 초기화하면 된다.
2에서는 isMin에서 if문을 추가하여 비교할 필요가 있는 node인지 체크하였지만,
애초에 모든 node를 최악의 우선순위로 초기화해두면 불필요한 갱신이 일어나지 않는다.
/* i * 2 + 1 -> i * 2로 수정 */
void update(HEAP* heap, int& hn, int id, int* heapIdx, int value)
{
HEAP tmp;
...
//for (int i = updatehn; i * 2 + 1 <= hn;)
for (int i = updatehn; i * 2 <= hn;)
{
...
}
int main(void)
{
int input[] = { 1, 2, 3, 4, 5, 6 };
int size = sizeof(input) / sizeof(int);
/* 최악의 우선순위로 초기화 */
for (int i = 0; i < 16 /* heap size */; i++) heap[i].id = heap[i].value = 0x7fff0000;
...
value가 작고, id가 작을수록 우선순위가 높으므로 value와 id를 모두 최댓값으로 설정해주면 된다.
최종코드는 아래와 같다.
#include <stdio.h>
typedef struct st
{
int value;
int id;
}HEAP;
HEAP heap[16];
int heapIdx[16]; /* id가 heap의 어느 위치에 있는지 저장할 배열 */
int hn;
int isMin(HEAP a, HEAP b)
{
//if (b.id == 0) return 1;
if (a.value < b.value) return 1;
else if (a.value == b.value && a.id < b.id) return 1;
return 0;
}
void output(HEAP* heap)
{
for (int i = 1; i <= 15; i++)
{
printf("%d (id : %d) ", heap[i].value, heap[i].id);
if ((i & (i + 1)) == 0) putchar('\n');
}
putchar('\n');
}
void outputHeapIdx(int* heapIdx)
{
for (int i = 1; i <= 15; i++) printf("%d ", heapIdx[i]);
putchar('\n');
}
HEAP pop(HEAP* heap, int& hn, int* heapIdx)
{
register HEAP tmp, ret;
ret = heap[1];
heap[1] = heap[hn];
heap[hn].value = 0x7fff0000;
heap[hn--].id = 0x7fff0000;
for (register int i = 1; i * 2 <= hn;)
{
if (isMin(heap[i], heap[i * 2]) && isMin(heap[i], heap[i * 2 + 1])) break;
else if (isMin(heap[i * 2], heap[i * 2 + 1]))
{
tmp = heap[i * 2];
heap[i * 2] = heap[i];
heap[i] = tmp;
heapIdx[heap[i].id] = i;
heapIdx[heap[i * 2].id] = i * 2;
i = i * 2;
}
else
{
tmp = heap[i * 2 + 1];
heap[i * 2 + 1] = heap[i];
heap[i] = tmp;
heapIdx[heap[i].id] = i;
heapIdx[heap[i * 2 + 1].id] = i * 2 + 1;
i = i * 2 + 1;
}
}
return ret;
}
void push(HEAP* heap, int& hn, int value, int id, int* heapIdx)
{
register HEAP tmp;
heap[++hn].value = value;
heap[hn].id = id;
heapIdx[id] = hn;
for (register int i = hn; i > 1; i /= 2)
{
if (isMin(heap[i / 2], heap[i])) break;
tmp = heap[i / 2];
heap[i / 2] = heap[i];
heap[i] = tmp;
heapIdx[heap[i].id] = i;
heapIdx[heap[i / 2].id] = i / 2;
}
}
void update(HEAP* heap, int& hn, int id, int* heapIdx, int value)
{
HEAP tmp;
/* int ret; */
int updatehn = heapIdx[id]; // findIndex(id);
heap[updatehn].value = value;
for (int i = updatehn; i > 1; i /= 2)
{
if (isMin(heap[i / 2], heap[i])) break;
tmp = heap[i];
heap[i] = heap[i / 2];
heap[i / 2] = tmp;
heapIdx[heap[i].id] = i;
heapIdx[heap[i / 2].id] = i / 2;
}
for (int i = updatehn; i * 2 <= hn;)
{
if (isMin(heap[i], heap[i * 2]) && isMin(heap[i], heap[i * 2 + 1])) break;
else if (isMin(heap[i * 2], heap[i * 2 + 1]))
{
tmp = heap[i * 2];
heap[i * 2] = heap[i];
heap[i] = tmp;
heapIdx[heap[i].id] = i;
heapIdx[heap[i * 2].id] = i * 2;
i = i * 2;
}
else
{
tmp = heap[i * 2 + 1];
heap[i * 2 + 1] = heap[i];
heap[i] = tmp;
heapIdx[heap[i].id] = i;
heapIdx[heap[i * 2 + 1].id] = i * 2 + 1;
i = i * 2 + 1;
}
}
/* pop(heap, hn, heapIdx); */
/* return ret; */
}
int main(void)
{
int input[] = { 1, 2, 3, 4, 5, 6 };
int size = sizeof(input) / sizeof(int);
for (int i = 0; i < 16 /* heap size */; i++) heap[i].id = heap[i].value = 0x7fff0000;
for (int i = 0; i < size; i++) push(heap, hn, input[i], i + 1, heapIdx);
update(heap, hn, 3, heapIdx, 8); /* id가 3인 학생의 점수를 8로 교체 */
output(heap); printf("\n");
outputHeapIdx(heapIdx);
return 0;
}아래의 우선순위 큐 갱신 문제는 case 3으로 수정하였다.
'알고리즘 > [PRO] 삼성 SW 역량 테스트 B형' 카테고리의 다른 글
| BOJ 2042 : 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) (0) | 2023.01.15 |
|---|---|
| BOJ 2042 : 구간 합 구하기 with 제곱근 분할법 (Sqrt Decomposition) (0) | 2023.01.15 |
| BOJ 14427 : 수열과 쿼리 15 (Reference) (0) | 2021.07.03 |
| BOJ 14427 : 수열과 쿼리 15 with 우선순위 큐 (0) | 2021.07.03 |
| 우선순위 큐 갱신 - B형 Reference 코드 (0) | 2021.06.09 |
댓글