(18)[Chapter7]우선순위 큐와힙트리_이론+코드

 

Chapter7_3_우선순위큐의 이론.pdf

0.78MB

#주요 핵심 이론(일반 힙트리와 우선 순위 힙트리의 차이들)  :

1_ 규칙이 달라짐(삽입, 삭제연산)

- 일반 힙 (최소힙 기준) : 

• 삽입 : 부모노드 값 > 자식노드 값 => SWAP / 부모노드 값 < 자식노드 값 => 종료
• 삭제 : smllest : △내에서 ( Data필드) 값이 가장 작은 값 

- 우선순위 힙(최소 Prior힙 값) :

• 삽입 : 부모노드.Priority값 > 자식노드.Priority값 => SWAP / 부모노드.Priority값 <자식노드.Priority값 => 종료
• 삭제 : smllest : △내에서 ( Priority값) 값이 가장 작은 값 (※그래야 i자리에 가장 )

2_ 구조체 구조

• 일반 힙 : 전역 DATA 타입 선언, 힙트리 구조체
• 우선순위 큐 : 노드 구조체(필드 : void*형 Data 변수, int형 우선순위 변수) , 힙트리 구조체(노드형 배열, 유효개수)

3_ void*형 Data

신경쓰여야 할 요소 :

1. SWAP 할 때, tmp의 자료형 => Node 자료형 (void* x)
2. main에서 함수 매개인자에 대입 시 , 따로 변수를 선언 초기화 후, 주소로 대입해야 한다.
3. 출력시,

• 서식연산자 : "%d"
• 서식연산자에 넣을 시 : *(원하는 Data의 자료형*)변수 이름
• DeleteHeap의 반환값의 자료형 : void*

#전체 코드 :

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
#pragma warning (disable : 4996)
//최대 우선순위 힙
 
//노드 구조체
typedef struct _PHNode {
    void* data;
    int Priority;
}Node;
 
//힙트리 구조체
typedef struct _PriorityHeap 
{
    Node heap[MAX_SIZE];
    int size;
}PHeap;
 
//힙트리 구조체 생성, 초기화
PHeap* CreateHeap(PHeap* H) 
{
    H = (PHeap*)malloc(sizeof(PHeap));
    H->size = 0;
 
    return H;
}
 
//부모, 왼자, 오자 인덱스 반환 메소드
int Parent(int i) 
{
    return ((i - 1) / 2);
}
 
int LeftChild(int i) 
{
    return 2 * i + 1;
}
 
int RightChild(int i)
{
    return 2 * i + 2;
 
}
 
//우선순위 큐 삽입 메소드
//매개변수(3가지) : 힙트리 구조체 , Data(void*형), 우선순위 값
void InsertPHeap(PHeap* H, void* data, int Priority) 
{
    //예외 조건 : 가득 찼을 경우 => 종료
    if (H->size == MAX_SIZE) 
    {
        printf("Priority Heap Full!!\n");
        return;
    }
 
    int i = H->size++;
 
    H->heap[i].data = data;
    H->heap[i].Priority = Priority;
 
    while ((i>0)&&(H->heap[i].Priority<H->heap[Parent(i)].Priority)) 
    {//while조건이 이래야 루트노드가 1등(가장 적은 우선순위)이 된다.
        //tmp 자료형 void* x, Node로 한다.
        Node tmp = H->heap[i];
        H->heap[i] = H->heap[Parent(i)];
        H->heap[Parent(i)] = tmp;
 
        i = Parent(i);
    }
 
    return;
}
 
 
//가장 우선순위가 작은 노드(루트 노드)를 제거 메소드
void* DeletePHeap(PHeap* H) 
{
    if (H->size == 0) 
    {
        printf("Priority Heap Empty!!\n");
        return NULL;//이 땐 NULL이네
    }
    else if (H->size==1) 
    {
        H->size--;
        return H->heap[H->size].data;
    }
 
 
    //반환용 임시변수 선언, 초기화
    void* rootData = H->heap[0].data;
 
    //맨마지막 노드와 루트노드 SWAP
    H->heap[0] = H->heap[--H->size];
 
    int i = 0;
 
    while (1) 
    {
        int smallest = i;
        int L = LeftChild(i);
        int R = RightChild(i);
 
        //삼각형 내에서, Priority값이 가장 큰 노드를 찾기
        if (L<H->size&&H->heap[smallest].Priority>H->heap[L].Priority)
        {
            smallest = L;
        }
        if (R<H->size && H->heap[smallest].Priority>H->heap[R].Priority)
        {
            smallest = R;
        }
 
        if (smallest == i) break;
 
        //i와 smallest노드 SWAP
        Node tmp = H->heap[smallest];
        H->heap[smallest] = H->heap[i];
        H->heap[i] = tmp;
 
        i = smallest;
    }
 
    return rootData;
}
 
void PrintHeap(PHeap* H) 
{
    printf("Priority Heap : ");
 
    for (int i = 0; i < H->size; i++) {
        printf("(Data : %d , Priority : %d) ", *(int*)H->heap[i].data, H->heap[i].Priority);
    }
    printf("\n");
}
 
 
int main() 
{
 
    PHeap* H = NULL;
 
    //★void*이라서, 삽입할 변수를 따로 초기화 해야한다.
 
    H = CreateHeap(H);
 
    int data1 = 3, data2 = 1, data3 = 6, data4 = 5, data5 = 2, data6 = 4;
 
 
    //void* 이라서 매개변수를 변수의 주소"&"로 대입해야 한다.
    InsertPHeap(H, &data1, 3);
    InsertPHeap(H, &data2, 1);
    InsertPHeap(H, &data3, 6);
    InsertPHeap(H, &data4, 5);
    InsertPHeap(H, &data5, 2);
    InsertPHeap(H, &data6, 4);
 
    PrintHeap(H);
 
    printf("Dequeued element: %d\n", *(int*)DeletePHeap(H));
 
    PrintHeap(H);
 
    return 0;
}

위의 코드의 출력 장면