Indexed Priority Queue - 우선순위 큐의 임의 원소 삭제

삼성 B형 전체 링크

 

참고

- 우선순위 큐 Priority Queue

- 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기

- 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기

- 우선순위 큐 임의 원소 삭제

- 우선순위 큐 임의 원소 삭제 최적화

- 우선순위 큐 임의 원소 갱신, 변경

 

Indexed Priority Queue, Heap - 삭제 구현

 

B형에서는 우선순위 큐를 이용해 문제를 풀어야 하는 경우가 많다.

우선순위 큐를 쓰면 임의의 값을 push해도 정렬을 유지할 수 있고,

가장 우선순위가 높은 값을 제거해도 정렬을 유지할 수 있다.

하지만 우선순위 큐를 쓰면 될 것 같은데, 애매한 상황이 하나가 있다.

우선순위는 낮지만, 특정 값을 제거해야하는 경우에는 우선순위 큐를 이용하면 성능이 나빠진다.

 

다음과 같은 문제의 조건을 보자.

 

어떤 학원에서 시험을 쳐서 (1) 점수(value)가 낮은 학생을 내보내려고 한다.

이때, 점수가 같으면 (2) 먼저 들어온 학생(id가 낮은 순)이 나간다. (즉, id는 유일하다)

그런데, 시험을 치기 싫은 (3) 어떤 학생(id)은 학원을 옮기려고 한다.

 

(1), (2) 조건은 기존의 우선순위 큐 방식대로 구현할 수 있다.

따라서 heap 구조체는 value와 id로 구성하고, 우선순위 판단은 아래와 같이 구현하면 된다.

typedef struct st
{
	int value;
	int id;
}HEAP;

HEAP heap[16];
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; /* id가 낮을수록 우선순위가 높다 */
	
	return 0;
}

 

점수가 낮을수록, 같은 점수인 경우 id가 낮을수록 우선순위가 높다.

 

이제 (3) 조건의 학생을 pop시키는 방법을 생각해보자. 예를 들어 id가 3인 학생이 나간다고 가정하자.

우선순위는 (1), (2) 조건 때문에 계속 유지시키고 싶으므로, id = 3이 나올 때 까지 pop해서 임시 배열에 저장한다.

id = 3인 학생이 pop되면, 임시 배열에 있는 학생을 다시 push한다.

 

이러면 id = 3인 학생이 제거되고, 우선순위는 여전히 (1), (2)를 만족한다.

 

하지만 문제는 id = 3인 학생이 점수가 가장 높은 경우이다.

이런 경우에 heap의 크기만큼 pop하게 되어 성능이 매우 떨어진다. (O(NlogN)만큼 비용이 들게 된다.)

---

이제 id = 3인 학생을 좀 더 효율적으로 제거해보자.

 

편의상 점수는 0이상이고, id는 1부터 시작한다. 

따라서 for문을 이용해 heap에 input(점수)를 넣고 id = i + 1로 push하자.

HEAP pop(HEAP* heap, int& hn);
void push(HEAP* heap, int& hn, int value, int id);

int main(void)
{
	int input[] = { 6, 5, 3, 5, 2, 3, 4, 5, 6, 7, 2, 5, 6, 7, 0 }; /* 점수 input */
	int size = sizeof(input) / sizeof(int);

	for (int i = 0; i < size; i++) push(heap, hn, input[i], i + 1);
    
	return 0;
}

 

그러면 아래와 같은 heap이 만들어진다.

 

이제 id = 3의 value를 -1로 바꿔보자.

 

그림을 보면 heap의 우선순위가 망가졌다.

하지만 정말 쓸모 없을 정도로 망가졌을까?

 

그렇지 않다.

 

왜냐하면 지금 저 상황을 다른 시각으로 보면,

heap을 유지하기 위해, heap을 갱신하는 과정 중 하나로 볼 수 있기 때문이다.

 

value = -1은 최고의 우선순위이므로, heap[1]로 이동하게 될 것이다.

heap을 갱신해보자.

---

 

특정 heap의 value를 임의로 바꾸고, 다시 갱신을 시도하였더니, 여전히 heap을 유지하게 되었다.

이제 여기서 pop만 하면 id = 3인 학생이 제거된다.

게다가 다시 갱신을 하는 로직은 push의 로직과 같다. 

push에서는 for의 초기값을 i = hn에서 부터 시작하지만, 여기에서는 삭제될 index부터 시작하면 된다.

int findIndex(int id)
{
	for (int i = 1; i <= hn; i++)
		if (heap[i].id == id) return i;

	return 0;
}

int deleteId(HEAP* heap, int& hn, int id)
{
	HEAP tmp;
	int ret;
	int delhn = findIndex(id); /* 삭제할 id의 index를 찾는다 */

	ret = heap[delhn].value; /* return할 value를 저장한다 */
	heap[delhn].value = -1; /* 최고의 우선순위로 바꾼다 */

	for (int i = delhn; i > 1; i /= 2) /* push를 delhn부터 시작한다 */
	{
		if (isMin(heap[i / 2], heap[i])) break;

		tmp = heap[i];
		heap[i] = heap[i / 2];
		heap[i / 2] = tmp;
	}

	pop(heap, hn); /* 삭제할 id를 pop 한다 */
	
	return ret;
}

 

deleteId는 입력된 id를 heap에서 삭제하고, 삭제될 id의 value를 return한다.

 

1. findIndex로 id = 3인 heap 배열의 index를 찾는다.

2. id = 3인 heap을 최고의 우선순위 값으로 바꾼다. (점수가 0이상이므로, -1로 바꾸면 최고의 우선순위이다.)

3. heap을 findIndex에서 찾은 index부터 갱신한다.

4. 가장 우선순위가 높아진 id = 3을 pop한다.

5. id = 3의 원래 value인 3을 return 한다.

 

hn = 15 부분이 최악의 우선순위로 변경되고, hn = 14가 된다.

그리고 pop에 의한 갱신이 일어나 아래와 같이 변경된다. 

 

처음에 생각했던, id = 3이 나올 때 까지 pop하여 임시 배열을 넣고, id = 3이 나온 후,

다시 push하는 방법은 최악의 경우에 O(NlogN)가 되지만,

현재의 방법은 삭제할 id를 찾는 것에 O(N), 갱신하는데 O(logN)이 걸리게 된다.

 

이러한 힙, 우선순위 큐를 indexed heap, priority queue 라고 한다.

 

최종 코드는 아래를 참고하자.

#include <stdio.h>

typedef struct st
{
	int value;
	int id;
}HEAP;

HEAP heap[16];
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');
}

HEAP pop(HEAP* heap, int& hn)
{
	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;

			i = i * 2;
		}
		else
		{
			tmp = heap[i * 2 + 1];
			heap[i * 2 + 1] = heap[i];
			heap[i] = tmp;

			i = i * 2 + 1;
		}
	}

	return ret;
}

void push(HEAP* heap, int& hn, int value, int id)
{
	register HEAP tmp;

	heap[++hn].value = value;
	heap[hn].id = id;
	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;
	}
}

int findIndex(int id)
{
	for (int i = 1; i <= hn; i++)
		if (heap[i].id == id) return i;

	return 0;
}

int deleteId(HEAP* heap, int& hn, int id)
{
	HEAP tmp;
	int ret;
	int delhn = findIndex(id);

	ret = heap[delhn].value;
	heap[delhn].value = -1;

	for (int i = delhn; i > 1; i /= 2)
	{
		if (isMin(heap[i / 2], heap[i])) break;

		tmp = heap[i];
		heap[i] = heap[i / 2];
		heap[i / 2] = tmp;
	}

	pop(heap, hn);
	
	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);

	printf("%d\n", deleteId(heap, hn, 3)); /* id = 3 삭제 */

	output(heap);

	return 0;
}

실제 문제에서는 삭제될 id가 없는 경우, 어떻게 처리해야하는 지에 대한 구현이 조금 추가될 수 있다.

---

하지만 아직 최적화할 것이 남아있다.

id가 원래 어디에 index에 위치하고 있는지 memoization하면 id를 찾는 방법 O(N)을 O(1)로 줄일 수 있다.

 

다음 글을 참고하자.