[Data Structures] 우선순위 큐 (Priority Queue)와 힙 (Heap)

1. 우선순위 큐 (Priority Queue)

• 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다 
• 우선순위 큐 구현을 위한 세가지 방법
  1. 배열을 기반으로 구현하는 방법 - 장점: 우선순위가 높을수록 배열의 앞쪽에 데이터를 위치시키고 우선순위가 높은 데이터를 반환 및 소멸 / 단점: 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야 함 & 삽입의 위치를 찾기 위해서 배열에 저장된 모든 데이터와 우선순위의 비교를 진행해야 할 수도 있다 
  2. 연결리스트 기반으로 구현하는 방법 - 배열 기반의 두번째 단점을 동일하게 가지고 있다
  3. 힙 (Heap)을 이용하는 방법
     • 힙은 이진 트리이되 완전 이진 트리이다
     • 부모 노드에 저장된 값이 자식 노드보다 커야한다
     • '값'을 '우선순위'로 정의하면 힙을 우선순위 큐에 이용할 수 있다
     • 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진 트리 = '최대 힙 (max heap)'
     • 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리 = '최소 힙 (min heap)'
     • 힙 기반 데이터 저장의 시간 복잡도는 트리의 높이에 해당하는 수만큼만 비교연산을 진행하면 되므로 O(log₂n), 힙 기반 데이터 삭제의 시간 복잡도 역시 O(log₂n)
     • 힙에서의 데이터 저장 및 삭제 과정
      

출처: https://hyunyoung2.github.io/2016/03/28/Priority_Queue_And_Heap/

 

 

 

 

2. 우선순위 큐 (Priority Queue)의 구현

• 배열 vs 연결 리스트 기반 힙의 구현 -- 연결 리스트를 기반으로 힙을 구현하면, 새로운 노드를 힙의 마지막 위치에 추가하는 것이 쉽지 않다. 따라서, 힙과 같이 새로운 노드를 추가한 이후에도 완전 이진 트리를 유지해야 하는 경우에는 연결 리스트가 아닌 배열을 기반으로 트리를 구현한다
• 배열 기반 힙 구성 방법
  1. 노드에 고유 번호를 부여하고 그 번호가 각 노드의 데이터가 저장 될 배열의 인덱스 값이 된다
  2. 구현의 편의를 위해서 인덱스가 0인 배열 요소는 사용하지 않는다
  3. 인덱스 값을 얻는 방법
     • 왼쪽 자식 노드의 인덱스 값 - 부모 노드의 인덱스 값 x 2
     • 오른쪽 자식 노드의 인덱스 값 - 부모 노드의 인덱스 값 x 2 + 1
     • 부모 노드의 인덱스 값 - 자식 노드의 인덱스 값 / 2
      

출처: https://hyunyoung2.github.io/2016/03/28/Priority_Queue_And_Heap/

• 배열 기반 힙 헤더파일 정의 및 구현 코드

//"SimpleHeap.h"
#ifndef __SIMPLE_HEAP_H__
#define __SIMPLE_HEAP_H__
#define TRUE 1
#define FALSE 0
#define HEAP_LEN 100
 
typedef char HData;
typedef int Priority;
 
typedef struct _heapElem
{
    Priority pr;    //값이 작을수록 높은 우선순위
    HData data;
} HeapElem;
 
typedef struct _heap
{
    int numOfData;
    HeapElem heapArr[HEAP_LEN];
} Heap;
 
void HeapInit(Heap * ph);
int HIsEmpty(Heap * ph);
void HInsert(Heap * ph, HData data, Priority pr);
HData HDelete(Heap * ph);
 
#endif
 
//"SimpleHeap.c"
#include "SimpleHeap.h"
 
void HeapInit(Heap * ph)
{
    ph->numOfData = 0;
}
int HIsEmpty(Heap * ph)
{
    if (ph->numOfData == 0)
        return TRUE;
    else
        return FALSE;
}
 
int GetParentIDX(int idx)
{
    return idx/2;    
}
int GetLChildIDX(int idx)
{
    return idx*2;
}
int GetRChildIDX(int idx)
{
    return GetLChildIDX(idx)+1;
}
 
//삭제를 진행할 때 필요한 함수
//두 개의 자식 노드 중 높은 우선순위의 자식 노드 인덱스 값 반환
int GetHiPriChildIDX(Heap * ph, int idx)
{
    //자식 노드가 존재하지 않는다면
    //힙은 완전 이진 트리이므로 오른쪽 자식 노드만 존재하는 상황은 발생하지 않는다
    if (GetLChildIDX(idx) > ph->numOfData)
        return 0;
    //자식 노드가 왼쪽만 존재한다면
    //하나뿐인 자식 노드는 왼쪽 자식 노드이고, 그것이 힙의 마지막 노드이다
    else if (GetLChildIDX(idx) == ph->numOfData)
        return GetLChildIDX(idx);
    //자식 노드가 양쪽에 모두 존재한다면
    else
    {
        //오른쪽 자식 노드의 우선순위가 높다면
        if(ph->heapArr[GetLChildIDX(idx)].pr > ph->heapArr[GetRChildIDX(idx)].pr)
            return GetRChildIDX(idx);
        //왼쪽 자식 노드의 우선순위가 높다면
        else
            return GetLChildIDX(idx);
    }
}
//합에 데이터 저장
void HInsert(Heap * ph, HData data, Priority pr)
{
    int idx = ph->numOfData + 1;
    HeapElem nelem = {pr, data};
 
    while(idx != 1)
    {
        if(pr < (pr->heapArr[GetParentIDX(idx)].pr))
        {
            ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
            idx = GetParentIDX(idx);
        }
        else
            break;
    }
    
    ph->heapArr[idx] = nelem;
    ph->numOfData += 1;
}
//힙에서 데이터 삭제
HData HDelete(Heap * ph)
{
    HData retData = (ph->heapArr[1]).data;                // 반환을 위해서 삭제할 데이터 저장
    HeapElem lastElem = ph->heapArr[ph->numOfData];        // 힙의 마지막 노드 저장
 
    int parentIdx = 1; 
    int childIdx;
 
    // 루트 노드의 우선순위가 높은 자식 노드를 시작으로 반복문 시작
    while(childIdx = GetHiPriChildIDX(ph, parentIdx))
    {
        if (lastElem.pr <= ph->heapArr[childIdx].pr) //힙의 마지막 노드와 우선순위가 높은 자식노드를 비교해 봐ㅆ을때
            break;                                     //마지막 노드의 우선순위가 높으면 반복문 탈출
    
        // 마지막 노드보다 우선순위 높으니, 비교대상 노드의 위치를 한 레벨 올림
        ph->heapArr[parentIdx] = ph->heapArr[childIdx];
        parentIdx = childIdx;
    }    // 반복문 탈출하면 parentIdx에는 마지막 노드의 위치 정보가 저장된다
 
    ph->heapArr[parentIdx] = lastElem;
    ph->numOfData -= 1;
    return retData;
}