우선순위 큐(Priority Queue) / 힙(Heap)

우선순위 큐(Priority Queue)

 

우선순위 큐는 말 그대로 Queue 중에서도 특별한 Queue이다.

우선순위를 가지는 큐로써, 가장 우선순위가 높은 자료가 가장 먼저 출력되는 구조를 지닌다.

아래처럼, 완전히 정렬된 형태는 아니지만 출력은 언제나 우선순위가 가장 높은 자료형이 반환된다. 

출처 https://velog.io/@junhok82/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%9E%99heap

 

따라서, 출력될 때 우선순위가 가장 높은 자료가 나올 수 있도록 삽입, 삭제가 이루어져야 한다.

삽입과 삭제의 연산에서 많은 연산들이 소모되어서 비효율적으로 보일 수 있지만 언제나 우선순위가 높은 자료형을 O(1)로 꺼낼 수 있기에 이러한 자료형이 필요시 될 때도 있다.

 

구현 방법에는 다양한 방법이 있지만 Heap을 통해서 우선순위 큐를 구현하는 것이 가장 이상적이다.

출처 gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

아래의 두가지를 만족하는 자료형을 Heap이라고 한다.

• 완전 이진 트리이다.
• 자식 노드는 부모 노드보다 우선순위가 같거나 높다. 

 

Heap을 가장 쉽게 구현하는 방법은 배열의 인덱스를 활용하는 법이다.

자식 노드를 *2, *2+1 로 표현하는 방법이다. 물론 index를 1부터 사용해서 0 index의 공간을 버려야하는 단점이 있다.

그럼에도 불구하고 가장 쉽게 구현할 수 있는 방법이다.

 

• 삽입은 리프노드부터 비교하며 올라오면서 우선순위에 해당하는 위치에 삽입한다. 삽입 후 size +1
• 삭제는 루트노드 값을 출력하고 루트노드와 heap의 가장 끝값을 교환한다. 그리고 size -1 해준 루트노드 부터 다시 내려가면서 위치를 조정해준다. 

 

해당 로직에 대한 이해는 아래의 링크를 통해 따라해보며 이해하는 편이 가장 빠르다.

https://www.cs.usfca.edu/~galles/visualization/Heap.html

Heap Visualization

---

구현

#include <stdio.h>

#define MAX_SIZE 1000
#define SWAP(x,y,z) z=x, x=y, y=z
int heap[MAX_SIZE];

// function define
void heapPush(int, int*);
void heapPop(int*);
void adjust(int, int);
void heapPrint(int);

// heap 삽입함수
void heapPush(int data, int* size) {

    // 끝 값 +1
    int i = ++(*size);

    // 만약 MAX 넘으면 ERROR!
    if (i >= MAX_SIZE) {
        fprintf(stderr, "(ERROR) HEAP FULL\n");
        exit(1);
    }

    // i 가 root가 아닐 동안 && 위치 찾지 못했을 동안
    while (i != 1 && heap[i / 2] > data) {
        heap[i] = heap[i / 2]; // 부모 노드를 내리고
        i = i / 2; //올라가기
    }

    // 탈출하면 위치에 넣기
    heap[i] = data;
}

// heap 삭제함수, size는 Heap의 data 개수 
void heapPop(int * size) {
    int temp = 0;
    printf("heap POP : %d\n", heap[1]);
    SWAP(heap[1], heap[*size], temp); // 위치 바꾸고 
    (*size)--; // 개수하나 제외
    adjust(1, (*size));  //위치 재조정

}

// 위치 조정 함수(자식 노드 중 우선순위에 따라 값을 올린다)
void adjust(int parent, int size) {

    int child = parent * 2; // 자식 노드 
    int p_data = heap[parent]; // 값 임시저장

    while (child+1 <= size) {

        // 둘 중 우선순위가 더 높은 자식 노드 값
        if (heap[child] > heap[child + 1]) {
            child++;
        }

        // 교환 끝
        if (heap[child] > p_data) {
            break;
        }

        // 값 올리기
        else {
            heap[child / 2] = heap[child];
            child *= 2;
        }
    }

    // 위치에 넣기
    heap[child / 2] = p_data;
}

// 출력함수
void heapPrint(int size) {
    printf("HEAP 저장 상황\n");
    int cnt = 2;
    for (int i = 1; i <= size; i++) {
        printf("%d ", heap[i]);
        if (i == cnt -1) {
            printf("\n");
            cnt = cnt * 2;
        }
    }
    printf("\n");
}

void main() {
        // 콘솔 핸들링
        int menu = 0;
        int value = 0;
        int size = 0;

        // 메인 로직
        while (menu <= 3) {
            heapPrint(size);
            printf("\n메뉴\n1.삽입(PUSH)\n2.삭제(POP)\n3.종료(EXIT)\n\n");
            scanf_s("%d", &menu);

            switch (menu) {
                // 삽입
            case 1:
                printf("PUSH 값 입력: ");
                scanf_s("%d", &value);
                heapPush(value, &size);
                break;

                // 삭제
            case 2:
                printf("POP 수행");
                if (size == 0) {
                    printf("(ERROR) HEAP EMPTY\n");
                    break;
                }
                heapPop(&size);
                break;

                // 종료
            case 3:
                menu = 4;
                break;
            }
        }
}