DataStructure] C언어로 쉽게 풀어쓴 자료구조 8장 - 4

DataStructure] C언어로 쉽게 풀어쓴 자료구조 8장 - 4

C언어로 쉽게 풀어쓴 자료구조

8장 Exercise 문제다.

필자가 학교 다니면서 자료구조론 수업을 들었는데,

과제로 제출했던 것들이고,

난항을 겪고 있는 사람들에게 참고가 되었으면 하는 마음으로 올린다.

자고로, 버그가 존재할 수 있으니 디버깅 작업은 필수다.

19. 우선순위 큐 추상 자료형의 연산들 중에서

find 연산, is_empty 연산, is_full 연산을 구현하여보라.

우선순위 큐가 히프로 구현되었다고 가정한다.

<HeapPQ.h>

#ifndef __HEAP_PQ_H__
#define __HEAP_PQ_H__
 
#define MAX_ELEMENT 200
 
typedef struct {
    int key;
} element;
typedef struct {
    element heap[MAX_ELEMENT];
    int size;
} PriorityQueue;
 
void Init(PriorityQueue* pq);
 
void InsertElement(PriorityQueue* pq, element item);
int DeleteTopPriority(PriorityQueue* pq);
int FindTopPriority(PriorityQueue* pq);
 
void PrintQueue(PriorityQueue* pq);
 
#endif

<HeapPQ.cpp>

#include <stdio.h>
#include <math.h>
#include "HeapPQ.h"
 
void Init(PriorityQueue* pq)
{
    pq->size = 0;
}
 
void InsertElement(PriorityQueue* pq, element item)
{
    int i;
    i = ++(pq->size);
 
    while ((i != 1) && item.key > pq->heap[i / 2].key)
    {
        pq->heap[i] = pq->heap[i / 2];
        i /= 2;
    }
    pq->heap[i] = item;
}
 
int DeleteTopPriority(PriorityQueue* pq)
{
    int parent, child;
    element max, temp;
 
    max = pq->heap[1];
    temp = pq->heap[pq->size--];
    parent = 1;
    child = 2;
 
    while (child <= pq->size)
    {
        if ((child < pq->size) && pq->heap[child].key < pq->heap[child + 1].key)
            child++;
        if (temp.key >= pq->heap[child].key)
            break;
        pq->heap[parent] = pq->heap[child];
        parent = child;
        child *= 2;
    }
    pq->heap[parent] = temp;
    return max.key;
}
int FindTopPriority(PriorityQueue* pq)
{
    return pq->heap[1].key;
}
 
void PrintQueue(PriorityQueue* pq)
{
    for (int i = 1; i <= pq->size; i++)
        printf("(%d) ", pq->heap[i]);
    printf("\n");
}

<main.cpp>

#include <stdio.h>
#include "HeapPQ.h"
 
int main()
{
    PriorityQueue queue;
 
    Init(&queue);
 
    InsertElement(&queue, { 210 });
    InsertElement(&queue, { 40 });
    InsertElement(&queue, { 30 });
    InsertElement(&queue, { 5 });
    InsertElement(&queue, { 12 });
    InsertElement(&queue, { 6 });
    InsertElement(&queue, { 115 });
    InsertElement(&queue, { 9 });
    InsertElement(&queue, { 100 });
 
    printf("<<Heap기반 최대 우선 순위 큐 구현>>\n\n");
    PrintQueue(&queue);
    printf("\n최우선 순위 값 탐색 및 삭제 : %d\n\n", DeleteTopPriority(&queue));
    PrintQueue(&queue);
    printf("\n최우선 순위 값 탐색 결과 : %d\n", FindTopPriority(&queue));
}