[알고리즘] 우선순위 큐

일반적인 큐는 FIFO 구조이다.
먼저 들어온 데이터가 먼저 나간다.

우선순위 큐는 들어온 데이터에 우선순위를 부여하여 나갈 때 우선순위가 높은 데이터가 먼저 나간다.

들어올 땐 니 맘 나갈땐 내맘

그렇다면 우선순위 큐에 대표적인 자료구조는 뭐가 있을까

힙 트리(HEAP TREE)

힙 트리는 여러값 중에서 작은값이나 큰 값을 빠르게 찾기 위해 만든 이진 트리이다.

생긴거

이러 식으로 부모가 가장 작은 값을 가지고 있으면 최소 힙
가장 큰 값을 가지고 있으면 최대힙으로 분류할 수 있다.
그러다 보니 루트노트에는 가장 큰 값 or 가장 작은 값을 O(1)으로 찾을 수 있다.

데이터처리

데이터 삽입( O(logN) 소요 )

'68'이라는 새로운 데이터 삽입

삽입된 후 부모 노드와 비교후 더 크면 스왑

스왑 후 부모 노드와 비교후 더 크면 스왑

데이터삭제

1.루트 노드를 삭제한다.
2.삭제한 루트 노드에 가장 마지막 노드를 가져와 넣는다.
3.새로운 노드의 자식 노드랑 비교하면서 내려간다.
-비교는 최대 힙 or 최소 힙에 따라 결정


Q. 그러면 루트 노드말고 다른 노드는 삭제못하나...?
A. 이 힙은 우선순위 큐를 기반한다. 즉 우선순위가 높은 루트 노트를 삭제하는 것이 이 자료구조의 핵심이다.

표현

지금까지 말한 내용을 토대로 코드로 옮기면 이진트리가 될 것 같지만 더 쉽고 가독성 좋게 개발하는 방법이 있다.
바로 배열로 구현하는 방법이다.
이진 트리의 구조를 보면

한 노드의 자식 인덱스는 이러한 규칙이 있다.

• 왼쪽 자식은 자기 주소값에 2배를 하면된다.
• 오른쪽 자식은 자기 주소값에 2배+1을 하면된다.
  이러한 규칙을 이용하면 배열로 구현하기가 쉬워진다.

코드

코드는 개념을 보고 직접 생각해서 짜는 편이라 정석이랑은 거리가 멀 수도 있음🌟

#include <Stdio.h>
#include <stdlib.h>
#pragma warning (disable:4996)

typedef struct Heap
{
    int data[100];
    int size;
    int type;// 0최소힙, 그외숫잔 최대힙
}Heap;

void insert(Heap* Hp, int num);
int delete(Heap* Hp);

void main() {
    Heap* Hp = (Heap*)malloc(sizeof(Heap));;
    Hp->size = 0;
    printf("0:최소힙이고 그 외 숫자는 최대힙으로 설정\n입력:");
    scanf("%d", &Hp->type);

    insert(Hp, 3);
    insert(Hp, 6);
    insert(Hp, 1);
    insert(Hp, 2);
    printf("%d\n", delete(Hp));

    for (int i = 1; i <= Hp->size; i++)
        printf("%d ", Hp->data[i]);
}

void insert(Heap* Hp, int num) {
    //맨 마지막 노드에 데이터 추가
    Hp->data[++Hp->size] = num;

    int idx = Hp->size;
    if (Hp->type) {//최대 힙
        while (idx > 1 && Hp->data[idx / 2] < Hp->data[idx]) {
            int tmp = Hp->data[idx / 2];
            Hp->data[idx / 2] = Hp->data[idx];
            Hp->data[idx] = tmp;
            idx /= 2;
        }
    }
    else if (!Hp->type) {//최소 힙
        while (idx > 1 && Hp->data[idx / 2] > Hp->data[idx]) {
            int tmp = Hp->data[idx / 2];
            Hp->data[idx / 2] = Hp->data[idx];
            Hp->data[idx] = tmp;
            idx /= 2;
        }
    }
}

int delete(Heap* Hp) {
    if (Hp->size < 1) return -1;
    else if (Hp->size == 1) return Hp->data[Hp->size--];

    int ret = Hp->data[1];

    Hp->data[1] = Hp->data[Hp->size--];


    int idx = 1;
    if (Hp->type) {//최대 힙
        while (idx * 2 <= Hp->size) {
            if (Hp->data[idx * 2] > Hp->data[idx]) {
                int tmp = Hp->data[idx * 2];
                Hp->data[idx * 2] = Hp->data[idx];
                Hp->data[idx] = tmp;
                idx *= 2;
            }
            else if (Hp->data[idx * 2 + 1] > Hp->data[idx]) {
                int tmp = Hp->data[idx * 2 + 1];
                Hp->data[idx * 2] = Hp->data[idx];
                Hp->data[idx] = tmp;
                idx *= 2 + 1;
            }
            else break;
        }
    }
    else if (!Hp->type) {//최소 힙
        while (idx * 2 <= Hp->size) {
            if (Hp->data[idx * 2] < Hp->data[idx]) {
                int tmp = Hp->data[idx * 2];
                Hp->data[idx * 2] = Hp->data[idx];
                Hp->data[idx] = tmp;
                idx *= 2;
            }
            else if (Hp->data[idx * 2 + 1] < Hp->data[idx]) {
                int tmp = Hp->data[idx * 2 + 1];
                Hp->data[idx * 2] = Hp->data[idx];
                Hp->data[idx] = tmp;
                idx *= 2 + 1;
            }
            else break;
        }
    }
    return ret;
}