우선순위 대기열와 힙

우선순위 대기열과 힙은 대기열와(큐) 이진트리에서 나온 이진트리에 기반을 둔 것이다.

 

우선순위 대기열과 힙은 게임프로그래밍에서 상당히 자주사용되긴하나

직접적으로 쓰이는것은 아니다.

어떤 문제의 해결에 도움을 주는 보조적인 자료구조로 쓰인다.

 

우선순위 대기열에서는 항목이 그냥 대기열의 끝에 차례로 추가되는 것이 아니다.

항목의 위치는 그 항목의 우선순위에 따라 달라진다.(즉 좀더 중요한 항목이 앞쪽에 위치함)

뽑는것은 일반 대기열과 같음

 

구현하는 방법중 가장 쉬운것은 연결된 목록(list)사용

그런데..느리다 이런 방법으로 우선순위 큐를 구현하는 경우는 거의없다

 

힙이라고하는 특별한 이진트리를 사용하면 좀 더 빠르고 효율적인 우선순위 대기열을 만들 수 있다.

(그런데 이진트리를 또 연결된 목록으로 구현하면 조밀성 여부를 판단하는게 배열로 된 이진트리 보다 복잡하다!!)

 

힙은 모든 노드가 자신의 모든 자식들보다 더 크다는 특성을 지닌 특별한 형태의 이진트리이다.

힙에서 가장 큰 값은 항상 루트 노드이며 이것으로 우선 순위 대기열로 쓰일 수 있다.

바꿔말해서 이진트리의 모든 노드들이 힙의 그러한 특성(1. 자신의 모든 자식들보다 더 크다 2. 가장 큰 값은 루트노드) 만족한다면 그 트리는 힙이다.

 

힙과 우선순위 대기열의 관계(어떤 종류의 힙들이 구현에 쓰이는가를 봄)

1. 힙의 요구사항 : 조밀성

힙은 연결된 이진트리보다 배열로 된 이진트리로 구현되는 경우가 많다. 이는 조밀성과 연결됨

(보통 왼쪽부터 생기는것을..표현?)

연결된 이진트리가 조밀한지의 여부를 판단하는것은 배열로된 이진트리의 경우보다 훨씬 복잡하다.

 

2. 힙에 항목을 삽입

힙의 항목을 삽일할때 중요한 점은 항목이 삽인된 이후에도 트리의 모든 노드들이 힙 특성을 만족해야한다(위의 2가지)

 

루트로부터 시작해서 모든 노드갖 ㅔ대로 된 자리에 놓이도록 노드들을 교환해나갈 수도 있지만..

복잡하고 시간도 많이 소비됨.

 

그래서 힙에 노드를 삽입할때는 따라 올라가기 알고리즘을 사용

즉, 새 항목을 트리의 가장 아래에 삽입 그리고 제자리를 찾을 때까지 올려보냄

알고리짐의 시간 복잡도는 0(log2n)이다

왜냐면 4수준 트리에서는 하나의 삽입에 최대 세번의 비교가 필요하고 5수준은 네번..

즉 수준이 늘 때마다 비교회수는 1회증가 그러나 수준이 하나늘면 노드들을 최대 개수가 두배로 증가, 그러나 삽입에 필요한 비교회수는 1증가

따라서 시간복잡도는 위에 0(log2n)이 된다.

이건 배열일때 만약 연결목록이면 모든 항목들을 살펴봐야할 수도 있으니..O(n)이다.

 

3. 힙에서 항목제거

루트노드 뿐만 아니라 다른 어떠한 노드도 제거할 수 있어야한다.

먼저 루트를 제거한다고 하자.. 제거 후에는?

가장 쉬운 방법은 트리의 최하위노드를 루트로 옮기고 그것을 적절한 자리로 내리는것

(최하위 노드란?가장 아래의 오른쪽 노드를 이야기함 왜 오른쪽일까? 위에서 이야기한 가장 효율적일때가 조밀성을 갖췄을때 이므로)

따라 올라가는것보다 따라 내려가는게 어려움(삽입보다 삭제가 어렵다는 이야기)

왜냐면 따라 올라갈때는 부모만 보면되지만 내려갈땐 자식 2개를 다 봐야함

(사실 그냥 두 자식들 중 더 큰것을 택해서 현재 노드와 바꾸면 된다)

 

근데 만약 루트가 아닌 다른 어떤 노드를 제거 했다면?

최하위 노드를 그 노드 자리에 넣은 다음 거기서부터 따라 내려가면 된다.

 

여담으로 연결된 목록으로 구현된 우선순위 대기열(우선순위 큐)의 경우 제일 앞 노드를 제거하는데 걸리는 시간은 연결된 목록의 제일 앞 노드를 제거하는데 걸리는 시간과 같다.

즉 연결된 목록 우선순위 대기열의 제거 알고리즘은 O(c)인것이다.

(힙을 연결목록으로 구현한게 아니라 그냥 연결목록을 우선순위큐로 구현한거다.!)

따라서 힙의 제거 알고리즘은 연결된 목록 우선순위 대기열의 첫 노드를 제거하는 것보다 훨씬 느리다.

 

그러나..

자료가 많을 수록 힙이 더 효율적이다.

자료가 127개라면 연결된 목록은 127번의 비교가 필요하지만 힙의 경우 21번이면 족하다

---

힙은 배열로된 이진트리로 구현하는것이 가장 좋다.

(배열로된 이진트리는 그냥 배열로 사용하는것일 뿐)

힙에서 비교함수를 사용하는 이유는 힙은 주어진 비교함수를 이용해서 항목들의 대 소비교를 수행한다.

그리고 배열 이진트리를 만들때는 인덱스가 0부터가 아닌 1부터시작해서 만들어야 하기때문에 배열의 크기는 +1 해야한다.

이유는 접근 인덱스나나 오른쪽 왼쪽 접근 방식때문에..그냥 편하게 하려고...0부터하게되면 복잡복잡..

#ifndef HEAP_H_
#define HEAP_H_
#include"Array.h"
 

template<class DataType>
class Heap : public Array < DataType >
{
public:
 int m_count;
 int(*m_compare)(DataType, DataType);

public:
 Heap(int p_size, int(*p_compare)(DataType, DataType)) : Array<DataType>(p_size + 1)
 {
  m_count = 0;
  m_compare = p_compare;
 }

 void Enqueue(DataType p_data)
 {
  m_count++;
  if (m_count >= m_size)
  {
   Resize(m_size * 2);
  }

  m_array[m_count] = p_data;
  WalkUp(m_count);
 }

 /*
  하나의 색인을 매개변수로 받고 트리안의 임의의 칸에 대해서 사용할 수 있다.
 */
 void WalkUp(int p_index)
 {
  int parent = p_index / 2; //현재 부모색인
  int child = p_index; //현재 자식 색인
  
  //트리를 따라 올려보내는 자료를 담는다.
  //빈번한 노드 교환을 피하려고 하는 변수
  DataType temp = m_array[child];

  while (parent > 0)
  {
   if (m_compare(temp, m_array[parent]) > 0)
   {
    m_array[child] = m_array[parent];
    child = parent;
    parent / 2;
   }
   else
    break;
  }

  m_array[child] = temp;
 }

 /*
  힙의 루트노드를 제거
 */
 void Dequeue()
 {
  if (m_count >= 1)
  {
   m_array[1] = m_array[m_count];
   WalkDown(1);
   m_count--;
  }
 }

 void WalkDown(int p_index)
 {
  int parent = p_index;
  int child = p_index / 2;
  DataType temp = m_array[parent];

  while (child < m_count) //자식 색인이 트리의 크기보다 작은 동안에만 반복
  {
   //아래 child < m_count -1이 되는 이유가
   //WalkDown이전에 m_count--; 이런게 없어서 자료를 삭제했더라도
   //m_count는 이전 그대로다
   if (child < m_count - 1) //오른쪽 자식의 존재 여부를 판단
   {
    if (m_compare(m_array[child], m_array[child + 1]) < 0)
    {
     child++;
    }
   }

   // 더큰 자식 노드가 선택이 되었다면 아래 진행
   if (m_compare(temp, m_array[child]) < 0)
   {
    m_array[parent] = m_array[child]; //자식을 부모노드에 넣었으니 수준이 아래로 내려가야함
    parent = child;
    child *= 2; //한 수준아래로 내려가자
   }
   else
    break;
  }
  m_array[parent] = temp;
 }
};