리루

[자료구조] 힙과 우선순위 큐 본문

# Study/Basic

[자료구조] 힙과 우선순위 큐

뚱보리루 2017. 1. 20. 02:31

삽입과 삭제가 빈번하게 발생하는 집합에서 가장 크거나 가장 작은 원소를 빨리 결정할 수 있는지에 의존하는 문제들이 많이 있다.

이 문제들에 접근하는 한 방법은 정렬된 집합을 유지하는 것이다.

이 방법에서 가장 크거나 가장 작은 항목을 정렬하는 순서에 따라 항상 집합의 가장 첫 원소가 된다.

그러나 매번 집합을 정렬하는 것은 비싸다. 게다가 모든 항목들이 정렬되는 것이 목표가 아니므로 실제로 필요한 것보다 더 많은 일을 하게된다.

가장 크거나 가장 작은 항목만 빨리 결정하려면 그 항목을 찾을 수 있는 위치에 유지만 시켜주면 된다.

힙(heap)과 우선순위 큐(priority queue)를 이용하면 이것을 효율적으로 할 수 있다.



 가장 큰(작은) 값의 노드를 빠르게 결정할 수 있도록 구조화된 트리이다.

 이런 성질을 유지하는 데 드는 비용이 자료를 정렬된 상태로 유지하는 것보다 싸다.


우선순위 큐

 힙에서 자연스럽게 파생된 자료 구조다.

 우선순위 큐에서 다음 우선순위의 노드를 빠르게 결정할 수 있도록 자료를 힙으로 구조화한다.

 항목의 우선순위는 다른 문제들에는 다른 것들을 의미할 수도 있다.



작업 스케쥴링

 CPU에서 다음에 실행될 프로세스를 결정하기 위해 운영체제가 수행하는 일이다.

 운영체제는 끊임없이 프로세스들의 우선순위를 변경한다.

 우선순위 큐는 최상위 프로세스가 다음에 CPU를 차지하는 것을 보장하는 효율적인 방법이다.


허프만 코딩

 자료의 기호들에 코드를 지정하기 위해 허프만 트리를 사용하는 자료 압축 방법이다.

 가끔 발생하는 기호들에는 긴 코드를 지정하는 반면 자주 발생하는 기호들에는 짧은 코드를 지정한다.

 허프만 트리는 작은 이진 트리를 두 개씩 합치면서 만들어 진다. 키 값이 가장 작은 두 트리를 합치므로 각 단계에서 합쳐지는 두 트리는 우선순위 큐에서 꺼낸다.



다시,

힙.

 힙(heap)은 모든 자식 노드들이 부모보다 작은 값을 갖는 트리(일반적으로 이진 트리)이다. 따라서 루트 노드는 트리에서 가장 큰 노드이다.

 모든 자식 노드들이 부모보다 큰 값을 갖도록 힙의 위치를 바꿀 수 있다.

 각 분기 내의 노드들은 정돈되어 있지만 어떤 단계의 노드들이 다른 단계의 노드들에 대해 정돈되어 있지는 않으므로 이러한 트리를 부분 정돈되었다고 한다.

 힙은 왼쪽 평형이어서 노드들이 누가될 때 트리는 단계별로 왼쪽에서 오른쪽으로 커진다.

 0에서부터 인덱싱되는 배열이라면 위치 i에 있는 노드의 부모는 위치 (i-1)/2 에 있게 되는데 여기서 소수부분은 무시한다.

 노드의 왼쪽과 오른쪽 자식의 위치는 각각 2i+1과 2i+2이다.

 이 구조는 특히 힙에서 중요한데 그것은 힙의 마지막 노드의 위치를 빨리 알 수 있기 때문이다.

 마지막 노드는 가장 깊은 단계의 가장 오른쪽 노드이다.(이것은 특정 힙 함수를 구현할 때 중요하다.)



typedef struct Heap_ {


int        size;

int        (*compare)(const void *key1, const void *key2);

void      (*destroy)(void *data);


void     **tree;


} Heap;


#define heap_parent(npos)  ( (int)(((npos) - 1) /2 ))

#define heap_left(npos)  ((npos) *2 ) +1 )

#define heap_right(npos)  (((npos) *2 ) +2 )


int heap_insert(Heap *heap, const void *data) {


void        *temp;

int           ipos, ppos;


// 노드의 메모리 할당.

if ((temp = (void **)realloc(heap->tree, (heap_size(heap) +1) *sizeof(void*))) == NULL {

return -1;

}


else

heap->tree = temp;


// 마지막 노드 다음에 노드 삽입

heap->tree[heap_size(heap)] = (void*)data;


//새 노드의 내용을 올리면서 트리 재힙화.

ipos = heap_size(heap);

ppos = heap_parent(ipos);


while(ipos > 0 && heap->compare(heap->tree[ppos], heap->tree[ipos]) <0 {

//현재 노드와 부모 노드의 내용을 바꿈.

temp = heap->tree[ppos];

heap->tree[ppos] = heap->tree[ipos];

heap->tree[ipos] = temp;


//재힙화를 계속하기 위해 트리의 위 단계로 이동.

ipos = ppos;

ppos = heap_parent(ipos);

}


//삽입된 노드를 반영하기 위해 힙 크기 조정

heap->size++;

return 0;

}



int heap_extract(Heap *heap, void **data){

void        *save, *temp;

int           ipos, lpos, rpos, mpos;


// 빈 힙에서 추출 금지

if ( heap_size(heap) ==0 )

return -1;


//힙의 최상위 노드를 추출.

*data = heap->tree[0];


//힙에 사용된 메모리 조정.

save = heap->tree[heap_size(heap) -1];


if (heap_size(heap) -1 >0) {

if ((temp = (void **)realloc(heap->tree, (heap_size(heap) -1) * sizeof(void*))) == NULL) {

return -1;

}

else

heap->tree = temp;

}


//추출된 노드를 반영하기 위해서 크기 조정.

heap->size--;

}


else{

//마지막 노드를 추출할 때 힙 처리.

free(heap->tree);

heap->tree = NULL;

heap->size = 0;

return 0;

}


//마지막 노드를 최상위로 복사

heap->tree[0] = save;


//새 최상위 노드의 내용을 아래로 내리면서 트리 재힙화.

ipos = 0;

lpos = heap_left(ipos);

rpos = heap_right(ipos);


while(1){

//현재 노드와 바꿀 자식 선택.

lpos = heap_left(ipos);

rpos = heap_right(ipos);


if(lpos < heap_size(heap) && heap->compare(heap->tree[lpos]), heap->tree[ipos]) >0) {

mpos = lpos;

}

else{

mpos = ipos;

}


if (rpos < heap_size(heap) && heap->compare(heap->tree[rpos], heap->tree[mpos]) > 0){

mpos = rpos;

}


//mpos가 ipos일 떄 힙의 특성이 복구됨.

if(mpos == ipos){

break;

}


else{

//현재 노드와 선택된 자식의 내용을 바꿈.

temp = heap->tree[mpos];

heap->tree[mpos] = heap->tree[ipos];

heap->tree[ipos] = temp;


//재힙화를 계속하기 위해 트리의 아래 단계로 이동.

ipos = mpos;

}

}


return 0;

}






=============================================================================

우선순위 큐.

 - 소화물 정렬

  대부분의 배달 서비스들이 소화물 배달 시간에 관한 여러 옵션들을 제공한다.

  일반적으로 돈을 많이 낼수록 소화물은 더 빨리 도착될 수 있다.

  대형 배달 서비스들은 매일 수백만 개의 소화물을 다루므로 정렬 과정에서 소화물들에 우선순위를 매기는 것이 중요하다.

  배달 절차와 관련된 공간이 제한되어 있을 때 특히 그렇다.

  이 경우에 높은 우선순위를 갖는 소화물들이 먼저 배달된다.


  특정 지역으로 배달된 소화물들을 올바른 우선순위에 따라 처리하는 확실한 하나의 방법은 그들의 정보를 우선순위 큐에 저장하는 것이다.

  정렬 과정은 소화물들을 조사하는 것으로 시작한다.

  각 소화물을 조사할 때 그 소화물의 정보에 우선순위가 매겨져 큐에 들어가고, 소화물이 이동될 때 우선순위가 높은 소화물이 먼저 배달된다.


  Parcel 형의 소화물 기록을 갖는 우선순위 큐에 대해 동작하는 두 함수 get_parcel과 put_parcel이 있다.

  정렬자는 put_parcel을 호출해서 소화물의 정보를 시스템에 넣는다. put_parcel에 전달되는 Parcel 구조체의 멤버는 우선순위 코드이다.

  put_parcel 함수는 소화물을 소화물들의 우선순위를 매기는 우선순위 큐에 넣는다.

  정렬자가 다음 소화물을 처리할 준비가 되면 get_parcel을 호출한다. get_parcel함수는 다음으로 높은 우선순위의 소화물을 가져 와서 소화물들이 올바른 순서대로 처리되도록 한다.


  언제나 다음으로 우선순위가 높은 소화물에만 관심이 있으므로 우선순위 큐는 소화물을 관리하는 좋은 방법이다.

  따라서 완벽하게 정렬되는 부담을 피할 수 있다. 

  get_parcel과 put_parcel은 각각 O(lg n)인 함수 pqueue_extract와 pqueue_insert를 단순히 호출하므로 복잡도가 같다.


'# Study > Basic' 카테고리의 다른 글

Hash와 Hash 충동  (0) 2017.03.31
[자료구조] 트리  (0) 2017.01.18