글 읽기 - Priority Queue에서 Binary search를 결합하는 소스..

tjdgns9246 7년 전 0

안녕하세요, 요즘 자료구조 책을 보면서 다시 공부를 하고있는 유저입니다.

제가 지금 Priority Queue를 공부하고 있는데요,

여기서 Heap을 이용한 일반적인 Push()를 하게되면 시간 복잡도가 O(log(n))이라고 알고있습니다.

그런데 책에서 이 Push()함수에다가 이진탐색을 결합시키면 시간복잡도를 O(log(log(n)))으로 줄일 수 있다고 합니다.

그래서 3일동안 고민해서 소스를 만들고 테스트를 해봤는데... 결과가 아래와 같이 나옵니다.

input : 7 16 49 82 5 31 6 2 44
output : 49 82 31 44 5 16 6 2 7

정상적인 결과로는 49 와 82가 바뀐 82 49 31 44 5 16 6 2 7 가 되야하는데요..

왜 이렇게 되는지 이해가 되지 않네요... @.@

또한 궁금한 점은 제 소스의 시간복잡도가 O(log(log(n)))이 맞는지 궁금합니다.

알려주실 고수분들 계신가요?

#include <stdio.h>
#define COMPARE(a, b) (a < b ? -1 : (a == b ? 0 : 1))

typedef struct
{
	int key;
} element;

element heap[200];
int n;

void modifiedPush(element node, int *n);

int main()
{
	element temp;
	
	printf("input  : ");
	while(scanf("%d", &temp.key) != -1)
	{
		modifiedPush(temp, &n);
		printf("%3d", temp.key);
	}
	
	printf("\noutput : ");
	for(int i = 1; i <= n; i++)
		printf("%3d", heap[i].key);
}

void modifiedPush(element node, int *n)
{
	int up, down, mid, i;
	
	if(*n == 199)
	{
		printf("Heap is full\n");
		return;
	}
	
	i = ++(*n);
	up = 1;
	down = i / 2;
	while(up <= down)
	{
		mid = (up + down) / 2;
		
		switch(COMPARE(heap[mid].key, node.key))
		{
			case -1: down = mid - 1; break;
			case 0: break;
			case 1: up = mid + 1; break;
		}
		
		if(node.key > heap[i/2].key)
		{
			heap[i] = heap[i / 2];
			i /= 2;
		}
	}
	heap[i] = node;
}

yukariko 7년 전 0

슬랙에서 얘기 나눈것을 정리해보자면

우선 시간복잡도는 밀어내는 과정이 있기때문에 O(lgN)이 될수밖에 없습니다.

여기서 O(lglgN)은 어느 노드에 위치해야 하는지를 찾는것을 의미한다고 생각됩니다.

구현할 목표는 정해졌고.. 이것을 이진탐색을 이용하려면 우선 데이터가 정렬된 상태여야 합니다.

그런데 힙은 자신의 직접 연결되는 부모간에만 대소관계가 있고 나머지와는 그렇지 못하기 때문에 위 코드 같은 이진탐색은 불가능하다고 생각됩니다.

또한, 저 코드는 결국 1~ N/2 사이의 이진탐색이기 때문에 O(lgN)의 시간복잡도를 갖습니다.

대신 루트노드부터 자기노드까지의 경로로만 생각한다면 정렬된 구조를 갖기때문에 이진탐색이 가능합니다.

자기노드의 깊이를 h라고 하면 h는 lgN일 것이고 1~h 와의 이진탐색이기 때문에 O(lglgN)이 되는 구조로 생각됩니다.

이제 up = 1, down = h로 놓고 이진탐색을 수행하는데, 실제 노드 인덱스는 N >> (h - mid) 같은 방식으로 진행하면 될것 같습니다.

tjdgns9246 7년 전 0

@yukariko 님,

감사합니다. O(log(log(n)))이 그런 뜻을 가지고 있었군요.. ㅎㅎㅎㅎ

덕분에 또 하나 배워갑니다 ^^

참고로, 제 소스에서 잘못된 부분은 42번째 줄에서 "down = i / 2" 에서 "down = i - 1"로 고치니 정상적으로 이진탐색이 되는 것 같네요.

아래의 소스로 정상적으로 push가 이루어지네요.

input : 7 16 49 82 5 31 6 2 44
output : 82 49 31 44 5 16 6 2 7

좋은 하루 되세요 ^^

#include <stdio.h>
#define COMPARE(a, b) (a < b ? -1 : (a == b ? 0 : 1))
 
typedef struct
{
    int key;
} element;
 
element heap[200];
int n;
 
void modifiedPush(element node, int *n);
 
int main()
{
    element temp;
     
    printf("input  : ");
    while(scanf("%d ", &temp.key) != -1)
    {
        modifiedPush(temp, &n);
        printf("%3d", temp.key);
    }
     
    printf("\noutput : ");
    for(int i = 1; i <= n; i++)
        printf("%3d", heap[i].key);
}
 
void modifiedPush(element node, int *n)
{
    int up, down, mid, i;
     
    if(*n == 199)
    {
        printf("Heap is full\n");
        return;
    }
     
    i = ++(*n);
    up = 1;
    down = i - 1;
    while(up <= down)
    {
        mid = (up + down) / 2;
         
        switch(COMPARE(heap[mid].key, node.key))
        {
            case -1: down = mid - 1; break;
            case 0: break;
            case 1: up = mid + 1; break;
        }
         
        if(node.key > heap[i/2].key)
        {
            heap[i] = heap[i / 2];
            i /= 2;
        }
    }
    heap[i] = node;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

Priority Queue에서 Binary search를 결합하는 소스..

tjdgns9246 7년 전 0

yukariko 7년 전 0

tjdgns9246 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말