[자료구조] 배열로 된 힙

우선순위에 따라 배열의 순서가 결정되는 힙을 만들겠다.

우선순위큐와 구조는 비슷하며 완전 이진트리이다.

우선순위를 작은 정수 값으로 정했을 때

C(3) - B(2) - A(1) 순으로 입력하면 입력순서에 상관없이 우선순위에 따라

배열 1 - A 1

배열 2 - B 2

배열 3 - C 3

이런 방식으로 저장하게 만든다.

배열1은 루트노드이며 배열2는 1의 왼쪽 자식노드, 배열3는 1의 오른쪽 자식 노드이다.

힙은 노드의 인덱스, 키값 등을 비교하여 배열로 정렬한다.

main.c

#include <stdio.h>

#include "heap.h"

int main(){

struct heap heap;

init(&heap);

insert(&heap, 'C', 3);

insert(&heap, 'B', 2);

insert(&heap, 'A', 1);

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;  // 전체 노드의 수를 0으로 초기화

}

int empty(struct heap *a){

if(a->num == 0){

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;  // 자식노드 기준으로 부모 노드의 인덱스 반환

}

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

int index = a->num+1;

struct data nel = {key, ch};  // 배열에 저장할 노드 정보 설정

while(index != 1){

if(key < a->arr[getparent(index)].key){  // 새로운 자식 노드의 키값 부모노드의 키값 비교 (작은것이 우선순위가 높다)

a->arr[index] = a->arr[getparent(index)];   // 부모노드 정보를 새로운 자식 노드에 저장

index = getparent(index);  // 부모 인덱스도 새로운 자식 노드에 저장

}else{  

break;  // 새로운 자식노드들이 부모노드보다 우선순위가 높지 않을때

}

}

a->arr[index] = nel;  // 1. 새로운 자식 노드 저장 2. (while문 거친경우) index가 부모의 인덱스이므로 부모노드에 새노드 저장

a->num += 1;  // 전체 노드수 +1

}

char remove1(struct heap *a){

char ch = a->arr[1].ch;  // 루트노드에 있는 문자를 반환할 예정이다. 고로 루트노드는 계속 바뀐다.

struct data last = a->arr[a->num];  // last는 하나가 출력될때마다 한 배열씩 루트노드 방향으로 이동할 것이다.

int parentindex = 1; 

int childindex;

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

if(last.key <= a->arr[childindex].key){   // 부모와 자식 비교함

break;  

}  

a->arr[parentindex] = a->arr[childindex];  // 자식노드가 부모노드로 이동한다.

parentindex = childindex;

}

a->arr[parentindex] = last;  // 마지막 노드의 정보가 방금 부모노드로 이동한 자식노드의 값을 덮어쓴다. 

                                      // 마지막 노드이면서 자신이 자식노드라면 자기 자신을 덮어쓸수도 있음

a->num -= 1;  // 출력했으므로 노드 1개를 뺀다.

return ch;  // 루트노드의 문자를 반환한다.

}

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

if(getlchild(key) > a->num){ // 노드가 1개 일때 (키값이 아닌 높이를 비교했기 때문)

return 0;

}else if(getlchild(key) == a->num){  // 노드가 2개일때 (키값이 아닌 높이를 비교했기 때문)

return getlchild(key);

}else{ // 노드가 3개 이상일때 높이 비교아니라 직접 키 값을 비교한다.

if(a->arr[getlchild(key)].key > a->arr[getrchild(key)].key){  // 왼쪽과 오른쪽 노드의 키값 비교

return getrchild(key);  // 우선순위 높은것 반환

}else{

return getlchild(key);

}

}

}

heap.h

struct data{

int key;  // 우선순위 결정하는 키 값

char ch;  // 보여줄 문자

};

struct heap{

struct data 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);  // 부모노드를 나타냄

int getprichild(struct heap *a, int key);  // 자식 중 우선순위를 나타냄

void insert(struct heap *a, char ch, int key);  // 배열에 노드를 입력함

char remove1(struct heap *a);  // 삭제하며 출력한다