Chap9. Priority Queue & Heap

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

typedef char HData;
typedef int Priority;

typedef struct _heapElem
{
  Priority pr; // 값이 작을 수록 높은 우선순위
  HData data;
} HeapElem;   // data와 우선순위 각각 구분

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); // 우선순위 높은 데이터 삭제

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// 우선 순위가 높은 자식의 인덱스 값 반환
int GetHiPriChildIDX(Heap * ph, int idx)
{
  // 자식 노드가 없다면
  // numOfData는 마지막 노드의 고유번호라서, 자식 노드의 값이 이보다 크면 존재하지 않는 자식 노드이다.
  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); // 왼쪽 자식 노드 인덱스 값 반환
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// 굳이 루트 노드의 자리로 옮기지 않아도 된다.
HData HDelete(Heap * ph)
{
  HData retData = (ph->heapArr[1]).data; // 삭제할 데이터 저장
  HeapElem lastElem = ph->heapArr[ph->numOfData]; // 힙의 마지막 노드 저장
  
  // parentIdx 에는 마지막 노드가 저장 될 위치 정보가 담긴다
  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; // 삭제 데이터 반환
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// 마지막 노드에 저장했다고 가정하고 임시저장 & idx 유지
void HInsert(Heap * ph, HData data, Priority pr)
{
  int idx = ph->numOfData + 1;  // 새 노드가 저장될 인덱스 값을 idx에 저장
  HeapElem nelem = {pr, data};  // 새 노드의 생성 및 초기화
  
  // 새 노드가 저장될 위치가 루트 노드의 위치가 아니라면 while문 반복
  while(idx != 1)
  {
    // 새 노드와 부모 노드의 우선순위 비교
    if(pr < (ph->heapArr[GetParentIDX(idx)].pr)) // 새 노드의 우선순위가 높다면
    {
      // 부모 노드를 한 레벨 내림, 실제로 내림
      ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
      
      // 새 노드를 한 레벨 올림, 실제로 올리지는 않고 인덱스 값만 갱신
      idx = GetParentIDX(idx);
    }
    else    // 새 노드의 우선순위가 높지 않다면 
      break;
  }
  ph->heapArr[idx] = nelem; // 새 노드를 배열에 저장
  ph->numOfData += 1;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

int main()
{
  Heap heap;
  HeapInit(&heap);
  
  HInsert(&heap, 'A', 1);
  HInsert(&heap, 'B', 2);
  HInsert(&heap, 'C', 3);
  printf("%c \n", HDelete(&heap));
  
  HInsert(&heap, 'A', 1);
  HInsert(&heap, 'B', 2);
  HInsert(&heap, 'C', 3);
  printf("%c \n", HDelete(&heap));
  
  while(!HIsEmpty(&heap))
    printf("%c \n", HDelete(&heap));
  
  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

/* 우선순위를 별도로 저장하지 않고 함수의 호출 결과로 판단하기 할 것 
 구조체 자료형 HeapElem : 우선순위 정보를 묶기 위함 -> 사용자가 직접 지정해줘야 하기에 직접 사용하기에는 무리가 있음
*/

typedef int PriorityComp(HData d1, HData d2);
// * 없음 : "PriorityComp형 포인터 면수 선언시 반드시 *를 붙여라"

typedef struct _heap
{
  PriorityComp * comp;
  int numOfData;
  HData heapArr[HEAP_LEN];
} Heap;

// 구조체 변경에 따른 초기화 함수 변경
// 프로그래머가 힙의 우선순위 판단 기준을 설정할 수 있어야 함
void HeapInit(Heap * ph, PriorityComp pc)
{
  ph->numOfData = 0;
  ph->comp = pc;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

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) 
    if(ph->comp(ph->heapArr[GetLChildIDX(idx)], ph->heapArr[GetRChildIDX(idx)]) < 0) // comp에 등록된 함수의 호출결과로 우선순위를 판단한다.
      return GetRChildIDX(idx);
    else
      return GetLChildIDX(idx);
  }
}

void HInsert(Heap * ph, HData data)
{
  int idx = ph->numOfData+1;
  
  while(idx != 1)
  {
    // if(pr < (ph->heapArr[GetParentIDX(idx)].pr))
    if(ph->comp(data, ph->heapArr[GetParentIDX(idx)]) > 0)
    {
      ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
      idx = GetParentIDX(idx);
    }
    else
    {
      break;
    }
  }
  
  ph->heapArr[idx] = data;
  ph->numOfData += 1;
}

HData HDelete(Heap * ph)
{
  HData retData = ph->heapArr[1];
  HData lastElem = ph->heapArr[ph->numOfData];
  
  int parentIdx = 1;
  int childIdx;
  
  while(childIdx = GetHiPriChildIDX(ph, parentIdx))
  {
    // if(lastElem.pr <= ph->heapArr[childIdx].pr)
    if(ph->comp(lastElem, ph->heapArr[childIdx]) >= 0) // comp함수가 판단 기준
      break;
    
    ph->heapArr[parentIdx] = ph->heapArr[childIdx];
    parentIdx = childIdx;
  }
  
  ph->heapArr[parentIdx] = lastElem;
  ph->numOfData -= 1;
  
  return retData;
}

int DataPriorityComp(char ch1, char ch2)
{
  return ch2 - ch1; // 내림차순
  // return ch1 - ch2
} // 아스키 코드 값이 작은 문자의 우선순위가 더 높다.

int main()
{
  Heap heap;
  HeapInit(&heap, DataPriorityComp); // 우선순위 판단기준 등록
  
  HInsert(&heap, 'A', 1);
  HInsert(&heap, 'B', 2);
  HInsert(&heap, 'C', 3);
  printf("%c \n", HDelete(&heap));
  
  HInsert(&heap, 'A', 1);
  HInsert(&heap, 'B', 2);
  HInsert(&heap, 'C', 3);
  printf("%c \n", HDelete(&heap));
  
  while(!HIsEmpty(&heap))
    printf("%c \n", HDelete(&heap));
  
  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#include "UsefulHeap.h"

typedef Heap PQueue;
typedef HData PQData;

void PQueueInit(PQueue * ppq, PriorityComp pc);
int PQIsEmpty(PQueue * ppq);

void PEnqueue(PQueue * ppq, PQData data);
PQData PDequeue(PQueue * ppq);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

void PQueueInit(PQueue * ppq, PriorityComp pc)
{
  HeapInit(ppq, pc);
}

int PQIsEmpty(PQueue * ppq)
{
  return HIsEmpty(ppq);
}

void PEnqueue(PQueue * ppq, PQData data)
{
  HInsert(ppq, data);
}

PQData PDequeue(PQueue * ppq)
{
  return HDelete(ppq);
}