우선순위큐(Priority Queue) 알고리즘....

프로그램을 하다 보면, 실시간 소팅일 필요한 경우가 있다.

이때 문제점이 데이터의 값 하나가 바뀔때 마다 qsort()을 하더라도 엄청난 자원을 필요로 한다는 것이다.
이러한 문제점을 해결하기 위한 방법이 소개할 우선순위큐(Priority Queue)라는 알고리즘 이다.

이 알고리즘은 일반적인 소팅알고리즘과 틀리게 전체를 소팅하지 않는다는 특징을 가지고 있어 실시간 소팅을
할때 상당히 유용하다. (문제는 전체를 소팅하지 않기 때문에 최상의 값 만이 의미를 갖는다는 것이다.)

이 알고리즘이 STL에도 존재한다. 그러나 STL과 같은 알고리즘은 데이터를 push()하고 pop()하는 것에 맞춰져 있다. 즉, 저장된 데이터의 값이 변경되거나 데이터를 삭제하고자 할 경우 전체를 다 꺼냈다가 다시 집어넣어야 하는 처리를 해야하는 경우도 있다는 것이다.

우선순위큐(Priority Queue) 자체에 대한 자세한 알고리즘 설명은
      http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Priority-Q/
참고하면 좋을듯 하다.

나는 여기에서 알고리즘에 대한 구현 방법을 소개 하고자 한다. - 알고리즘은 C로 구현되어 있다~
지금은 더 좋은 방법들도 많겠지만.. 아직 C++ 변환의 필요를 못 느끼고 있어 그대로 쓰고 있다^^;

typedef struct pq__State {
 void **heap;          //!< 객체 저장 포인터 (할당되는 배열은 size + 1)
 struct {
  int nobject;         //!< 저장된 항목수
  bool (*lessThen)( const void *, const void *);  //!< 비교함수
 }; int size, nalloc;        //!< 최대 저장 가능한 객체 수
} *pq_pState;

여기에서 lessThen은 데이터를 정렬하기 위한 비교 함수로,

bool lessThen( const void *l, const void *r)
{
     return (l <= r); // l이 r보다 앞으로 정렬되어 진다.
}

로 구현해 사용되어 진다. -- 일단, 데이터를 처리하기 위한 구조체 이다.

그리고, 데이터를 정렬하는 알고리즘을 구현한 함수이다~

static int __upObject( int offset, pq_pState pState) // 0 ~ offset 까지 정렬한다.
{
 void *node = pState->heap[offset]; {
  register int shift = (offset >> 1);

  while ((shift > 0) &&
    pState->lessThen( node, pState->heap[shift]))
  {
   pState->heap[offset] = pState->heap[shift]; {
    offset = shift;
   } shift >>= 1;
  } pState->heap[offset] = node;
 } return offset;
}

static int __downObject( int offset, pq_pState pState) // offset ~ MAX 까지 정렬한다.
{
 void *node = pState->heap[offset]; {
  register int delta,
               down;

_gWhile:down = (delta = offset << 1) + 1;
  if ((down > pState->nobject) ||
    !pState->lessThen( pState->heap[down], pState->heap[delta]))
   ;
  else delta = down;

  if ((delta > pState->nobject) ||
    !pState->lessThen( pState->heap[delta], node))
   ;
  else {
   pState->heap[offset] = pState->heap[delta]; {
    offset = delta;
   } goto _gWhile;
  } pState->heap[offset] = node;
 } return offset;
}

static int __adjustObject( int n, pq_pState pState) // n 위치를 중심으로 정렬위치를 결정한다.
{
 int shift;
 
 if (!(shift = (n >> 1)))
  ;
 else {
  if (pState->lessThen( pState->heap[n], pState->heap[shift]))
   return __upObject( n, pState);
 } return __downObject( n, pState);
}

이제는 데이터를 저장하는 함수이다.

// 데이터를 저장한다. 여기에서 저장할 버퍼가 없다면 큐에 존재하는 데이터중 정렬값이 가장 낮은
// 데이터를 반환한다.
void *pq_push( pq_pState pState, void *obj)
{
 if (pState->nobject < pState->size)
  pState->heap[++pState->nobject] = obj;
 else { // 큐에 저장 공간이 없다면...
  if ((pState->nobject <= 0) ||
    pState->lessThen( obj, pState->heap[1]))
   ;
  else {
   void *top = pState->heap[1];

   pState->heap[1] = obj; {
    __downObject( 1, pState);
   } obj = top;
  } return obj;
 } __upObject( pState->nobject, pState); return NULL;
}

// 상위 데이터를 읽는다. (물론, 정렬된 값을 반환한다)
void *pq_top( pq_pState pState)
{
 return pState->nobject ? pState->heap[1]: NULL;
}

다음으로, 이 함수는 정렬된 순서대로 데이터를 얻는 역활을 한다.

// 최상위 데이터를 제거하고, 나머지 데이터를 대상으로 상위 값을 추출한다.
void *pq_pop( pq_pState pState)
{
 void *obj;
 
 if (pState->nobject <= 0)
  return NULL;
 else {
  obj = pState->heap[1]; {
   pState->heap[1] = pState->heap[pState->nobject]; {
    ;
   } pState->heap[pState->nobject--] = NULL;
  } __downObject( 1, pState);
 } return obj;
}

다음 루틴이 저장된 큐에서 원하는 데이터를 순차검색으로 찾아 제거 하거나 데이터가 바뀌었을때 갱신하는 역활을 하는 함수이다.
 

// 순차 검색으로 큐에 저장된 데이터를 찾는다. 여기에서 n의 범위는 0 ~ N 까지 이다.
void *pq_each( pq_pState pState, int n)
{
 if ((n <= 0) || (n > pState->nobject))
  errno = ERANGE;
 else {
  return pState->heap[n];
 } return NULL;
}

// n 위치의 데이터값을 재 정력한다.
int pq_resort( pq_pState pState, int n)
{
 if ((n <= 0) || (n > pState->nobject))
  errno = ERANGE;
 else {
  return __adjustObject( n, pState);
 } return -1;
}

// n 위치의 값을 제거하고, 나머지 데이터를 대상으로 재정렬을 수행한다.
void *pq_remove( pq_pState pState, int n)
{
 if ((n <= 0) || (n > pState->nobject))
  errno = ERANGE;
 else {
  void *obj = pState->heap[n];

  if (n >= pState->nobject)
   pState->heap[pState->nobject--] = NULL;
  else {
   pState->heap[n] = pState->heap[pState->nobject]; {
    pState->heap[pState->nobject--] = NULL;
   } if (pState->nobject > 0) __adjustObject( n, pState);
  } return obj;
 } return NULL;
}

// n위치의 데이터를 새로운 데이터로 변경하고 큐를 재정렬한다.
void *pq_update( pq_pState pState, int n, void *obj)
{
 if ((n <= 0) || (n > pState->nobject))
  errno = ERANGE;
 else {
  void *now = pState->heap[n];

  pState->heap[n] = obj; {
   __adjustObject( n, pState);
  } return now;
 } return NULL;
}

pq_remove() 및 pq_update() 함수는 pq_each()를 통해 순차 검색된 데이터를 삭제하거나, 저장된 데이터를 변경후 재 정렬 하도록 하는 기능을 수행한다. == 정렬방식을 이해한다면 이러한 순차 검색을 사용하지 않고도 검색하는 방법을 찾을수도 있겠으나, 나는 이러한 데이터에 대한 변경 작업이 수시로 발생되지 않는다고 가정했기 때문에 더 좋은 알고리즘을 찾기 보다는 기존의 순차검색을 그대로 사용하였다~

** STL과 같은 우선순위큐 접근 방식으로 데이터를 삭제하거나 update를 할 경우, 원하는 데이터가 추출될때 까지 pop()을 수행해야 하는데 이때 문제가 pop 될때 마다 저장된 데이터의 정렬이 발생되는데 이를 방지하기 위해 일반 순차 검색 방법을 사용했다.