[ch 09-2] 힙의 구현과 우선순위 큐의 완성_2(구현)

[배열 기반의 힙 구현]

- 연결 리스트 기반으로 구현 시 새로운 노드를 '마지막 위치'에 추가하는 것이 쉽지 않음

- 각 노드마다 고유번호가 존재하며, 그 번호가 배열의 인덱스와 동일

■ 그림(배열 기반의 힙)

- 노드 인덱스와 배열 인덱스와 동일하게 만들기 위하여 배열의 0번째는 사용하지 않음

[고유 번호(인덱스)를 통해 부모/자식노드 구하기 규칙]

- 왼쪽 자식노드의 인덱스: 부모노드의 인덱스 * 2

- 오른쪽 자식노드의 인덱스: 부모노드의 인덱스 * 2 + 1

- 부모노드의 인덱스: 자식노드의 인덱스 / 2

  ※ 소수점을 무시하고 정수로 몫을 계산

[힙 구현의 개념 및 규칙]

- 힙은 완전 이진 트리로 구성됨

- 노드 번호와 배열의 인덱스는 동일하며, 마지막 노드 번호는 존재하는 노드의 개수와 동일한 개념으로 판단 가능

- 각 노드에 설정된 우선순위의 값이 낮을수록 순서상 높다고 가정

  ※ '1'이 우선순위 중 가장 높으며, 루트노드를 뜻함

[소스 코딩]

■ SimpleHeap.h

#ifndef SIMPLEHEAP_H_
#define SIMPLEHEAP_H_
 
#define    TRUE        1
#define FALSE        0
 
#define HEAP_LEN    100
 
typedef struct _heapElem
{
    int pr;
    char data;
} HeapElem;
 
typedef struct _heap
{
    int numOfData;
    HeapElem heapArr[HEAP_LEN];
} Heap;
 
void HeapInit(Heap * ph);       // 힙 초기화
int HIsEmpty(Heap * ph);        // 힙에 데이터가 비워져 있는지 확인
 
void HInsert(Heap * ph, char data, int pr);        // 새로운 노드 삽입
char 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);
        }
    }
}
 
/*
 * 새로운 노드 생성 및 우선순위에 맞는 자리 찾아가기
 * - 'idx'에 마지막 노드의 위치를 저장
 * - 생성된 노드에 우선순위 숫자와 데이터 저장
 * - 생성된 노드가 루트 노드가 아닐 경우 다음을 반복
 * - 생성된 노드의 우선순위 숫자가 부모노드의 우선순위 숫자보다 낮을 경우:
 *   생성된 노드가 우선순위가 높다는 것을 의미 -> 부모노드와 위치를 교체
 * - 우선순위 숫자가 같거나 높을 경우 반복 종료
 * - 데이터 개수 1개 추가
 */
void HInsert(Heap * ph, char data, int pr) {
    int idx = ph->numOfData + 1;
    HeapElem nelem = {pr, data};
 
    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;
}
 
/*
 * 루트노드 삭제 및 우선순위에 맞는 자리 찾아가기
 * - 루트노드의 데이터는 반환될 'retData'에 저장
 * - 마지막 노드는 루트노드 자리에 옮기지 않고 'lastElem'을 마지막 노드로 임시 설정하여 우선순위 비교
 * - 우선순위가 높은 자식노드와 비교하여 우선순위가 낮으면 위치를 교체해가며 아래로 내려감
 * - 우선순위가 더 높거나 더 이상 아래로 내려갈 수 없으면 최종적으로 위치가 고정됨
 * - 노드 전체개수를 '1' 감소하고 루트노드의 데이터는 반환
 */
char HDelete(Heap * ph) {
    char 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;
    }
 
    ph->heapArr[parentIdx] = lastElem;
    ph->numOfData -= 1;
    return retData;
}

■ SimpleHeapMain.c

#include <stdio.h>
#include "SimpleHeap.h"
 
int main(void) {
    Heap heap;
    HeapInit(&heap);
 
    HInsert(&heap, 'A', 1);
    HInsert(&heap, 'B', 2);
    HInsert(&heap, 'C', 3);
 
    HInsert(&heap, 'D', 4);
    HInsert(&heap, 'C', 3);
    HInsert(&heap, 'B', 2);
 
    while(!HIsEmpty(&heap))
        printf("%c \n", HDelete(&heap));
 
    return 0;
}

■ 실행결과

■ 그림(실행결과 트리 표현)