[자료구조] 우선순위 큐

main.c 

#include <stdio.h>

#include "heap.h"

int main(){

struct heap heap;

init(&heap);

insert(&heap, 'C');

insert(&heap, 'B');

insert(&heap, 'A');

while(!empty(&heap)){

printf("%c \n", remove1(&heap));

}

return 0;

}

heap.c

#include <stdio.h>

#include "heap.h"

void init(struct heap *a){

a->num = 0;   // 노드 개수 초기화

}

int empty(struct heap *a){

if(a->num == 0){  // 노드 개수가 0 일때 비어있으므로 1 반환

return 1;

}else{

return 0;

}

}

int getlchild(int a){

return a*2;  // 왼쪽 노드 접근

}

int getrchild(int a){

return a*2+1;  // 오른쪽 노드 접근

}

int getparent(int a){

return a/2;  // 부모 노드 접근

}

int comp(char a, char b){

return b-a;  // 문자의 대소구분

}

void insert(struct heap *a, char ch){

int index = a->num+1;

while(index != 1){

if(comp(ch, a->arr[getparent(index)]) > 0){  // 부모노드와 자식노드 문자를 비교하여 우선순위 높으면 바꿔준다

a->arr[index] = a->arr[getparent(index)];  // 부모노드의 문자를 자식노드에 덮어씀

index = getparent(index);  // 부모노드의 인덱스를 자식노드에 덮어씀

}else{

break;  // 우선순위를 바꾸지 않아도 될 때

}

}

a->arr[index] = ch;  // 1. 자식노드에 문자 넣음 2. 부모노드에 자식노드의 문자 넣음 (결국 서로 바꿔준거)

a->num += 1;

}

int getprichild(struct heap *a, int b){

if(getlchild(b) > a->num){

return 0;

}else if( getlchild(b) == a->num){

return getlchild(b);

}else{

if(comp(a->arr[getlchild(b)], a->arr[getrchild(b)]) > 0){  // 우선순위 비교

return getlchild(b);

}else{

return getrchild(b);

}

}

}

char remove1(struct heap *a){

char ch = a->arr[1];  // 첫번째 노드의 문자

char last = a->arr[a->num];  // 마지막 노드의 문자

int parentindex = 1;

int childindex;

while(childindex = getprichild(a, parentindex)){

if(comp(last, a->arr[childindex]) >= 0){

break;   // 이게 없으면 부모와 자식이 똑같은 노드 나왔을 때 실행함

}

a->arr[parentindex] = a->arr[childindex];  // 부모노드에 자식노드 문자 덮어씀

parentindex = childindex;  // 부모노드 인덱스에 자식노드 인덱스 넣음

}

a->arr[parentindex] = last;  // 마지막 노드의 문자를 자신의 부모 노드에 덮어씀

a->num -= 1;

return ch;   // 첫번째 노드의 문자 반환

}

heap.h

struct heap{

char arr[100];

int num;

};

void init(struct heap *a);

int empty(struct heap *a);

int getlchild(int a);

int getrchild(int a);

int getparent(int a);

void insert(struct heap *a, char ch);

int getprichild(struct heap *a, int b);

char remove1(struct heap *a);

int comp(char a, char b);