[자료구조] 우선순위 큐(priority queue)와 히프(heap)의 구조

우선순위 큐(priority queue)는 각 요소들이 우선 순위값을 가지고 있으며, 우선 순위가 높은 데이터가 먼저 나가게 되는 구조이다. 우선순위 큐에는 가장 우선 순위가 낮은 요소를 먼저 삭제하는 최소 우선순위 큐, 그리고 반대로 우선 순위가 높은 요소가 먼저 삭제되는 최대 우선순위 큐가 있다.

히프(heap)는 우선순위 큐를 구현하는 가장 효율적인 구조이다. 히프는 완전 이진 트리의 일종으로, 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내는 경우에 매우 유리한 자료 구조이다. 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리로 구현된 것을 최대 히프(max heap),0 반대로 노드의 키 값이 자식 노드의 것보다 항상 작은 히프를 최소 히프(min heap)라고 한다.

히프는 완전 이진 트리이므로 루트 노드부터 시작하여, 각 레벨의 왼쪽부터 순회한다고 하였을 때 각각의 노드에 차례대로 번호를 붙일 수 있다. 1번부터 시작하는 번호들을 배열의 인덱스로 생각하여 배열에 히프의 노드들을 저장할 수 있다. 따라서, 부모 노드와 자식 노드간의 관계를 배열의 인덱스로 쉽게 나타낼 수 있는데, 왼쪽 자식에 인덱스는 부모 노드의 인덱스에 2를 곱한 값이고, 오른쪽 자식의 인덱스는 부모 노드 인덱스에 2를 곱하여 1을 더한 값이다.

다음은 우선 순위를 나타내는 정수형 키 값과 동물의 이름을 요소로 하는 노드를 히프로 구현하는 프로그램이다.

/* 
	프로그램명: 우선순위와 동물들의 이름을 저장하여 히프에 추가하는 프로그램 (최대 히프)
*/
    
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
   
typedef struct element{
	int key;
    char* name;
 }element;

typedef struct { // 히프 구조체
 	element* heap;
    int heap_size;
}HeapType;

void error(char* message) {
	fprintf(stderr, "%s \n", message);
    exit(1);
}

HeapType* create() {
	return (HeapType*)malloc(sizeof(HeapType));
}

void init(HeapType* h) {
	h->heap_size = 0;
 }
 
 // 최대 히프 구현하는 삽입 함수
 void insert_max_heap(HeapType* h, element item) {
 	int i; // 히프 배열 인덱스 값
    i = ++(h->heap_size); // 히프의 크기를 1 증가시킨 값을 i에 저장
    // 첫번째 인덱스값이 아니고, item의 키 값이 부모 노드의 키 값보다 큰 경우
    while ((i != 1) && (item.key > h->heap[i / 2].key)) {
    	h->heap[i] = h->heap[i / 2];
        // i번 인덱스의 요소(자식 노드)에 i/2번 인덱스의 요소(부모 노드) 대입
        i /= 2; // i/2번 인덱스로 이동 (부모 노드)
    }
    h->heap[i] = item; // i번 인덱스에 새로운 item 대입
 }
 
 int main() {
 	FILE* fp;
    element tmp; // 임시 구조체
    char name[20]; // 임시로 저장할 이름 문자 배열
    HeapType* heap; // 히프 구조의 포인터
    int i = 0, size = 0;// 반복문 제어 변수, 히프 전체 출력을 위한 배열 크기
    
    heap = create(); // 히프 생성
    init(heap); // 히프 초기화
    fp = fopen("data.txt", "rt");
    if (fp == NULL) {
    	fprintf(stderr, "파일 열기 오류 \n");
        exit(1);
    }
    
    while (!feof(fp)) {
    	fscanf(fp, "%d %s", &tmp.key, name);
        i++;
    }
    
    rewind(fp);
    heap->heap = (element*)malloc(sizeof(element) * (i + 1));
    
    while (!feof(fp)) {
    	fscanf(fp, "%d %s", &tmp.key, name);
        tmp.name = (char*)malloc(strlen(name) + 1); // 문자열 포인터에 메모리 할당
        
        if (tmp.name == NULL) error("문자 배열 동적 할당 실패");
        else {
        	strcpy(tmp.name, name); // 문자열 복사 
        	printf(">> (%d : %s) 입력 \n", tmp.key, tmp.name);
            insert_max_heap(heap, tmp); // 최대 히프에 삽입
        }
    }
    
    size = heap->heap_size; printf("\n\n===== 동물 히프 출력 ===== \n\n");
        
    for (i = 1; i <= size; i++) {
    // 배열의 순서대로 출력
    printf("%d:%s => ", heap->heap[i].key, heap->heap[i].name);
    free(heap->heap[i].name); // 출력 이후에 해당 문자 배열 메모리 해제
    }

    printf("\n\n");
    free(heap->heap); // 히프 구조체 메모리 해제
    free(heap); // 히프의 모든 메모리 해제
    fclose(fp); // 파일 닫기

    return 0;
}