[자료구조] 우선순위 큐(Priority Queue)란? + 힙(heap)이란? - 컴도리돌이

우선순위 큐(Priority Queue)란?

 

모든 데이터가 우선순위를 가지고 있고, 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 출력된다.

스택이나 큐를 우선순위 큐로 구현할 수 있으며, 응용분야로는 네트워크 트래픽 제어, os의 작업 스케쥴링 등이 있다.

 

우선순위 큐 구현 방법

 

우선순위 큐 구현 방법

힙(heap)이란?

 

완전 이진트리(complete binary tree)로 구성되며 최대 힙, 최소 힙의 두 가지 표현법이 있다. 우선순위 큐를 위해 만들어진 자료구조로 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도의 느슨한 정렬 상태를 유지한다. 힙의 목적이 삭제 연산에서 가장 큰 값을 효율적으로 찾아내기만 하면 되는 것이므로 전체를 정렬할 필요는 없다.(최대 힙을 가정할 때)

 

최대 힙(max heap)과 최소 힙(min heap)

 

힙(heap)의 구현

 

힙(heap)의 구현

 

부모 노드와 자식 노드의 관계

 왼쪽 자식의 인덱스 = 부모의 인덱스 * 2

 오른쪽 자식의 인덱스 = 부모의 인덱스 * 2 + 1

 부모의 인덱스 = 자식의 인덱스 / 2

 

힙(heap)의 삽입 연산 그림 예시 && c언어 코드

 

힙(heap)의 삽입 연산 그림예시

힙(heap)의 삽입 C언어 코드

 

힙(heap)의 삭제 연산 그림 예시 && c언어 코드

 

힙(heap)의 삭제 연산 그림 예시

1. 루트 삭제

2. 루트에서부터 단말 노드까지의 경로에 있는 노드들을 교환하여 힙(heap) 성질을 만족시킨다.

3. 힙(heap)의 마지막 노드를 루트 노드에 가져가서 아래 방향으로 노드들을 비교한다.

 

힙(heap)의 삭제 연산 C언어 코드

 

 

 

#include <stdio.h>
#include <stdlib.h>
#define MAX_HEAP_NODE    200

void error(char str[])
{
    printf("%s\n", str);
    exit(1);
}

typedef int HNode;
#define Key(n)   (n)

HNode heap[MAX_HEAP_NODE];
int heap_size;

#define Parent(i) (heap[i/2])        
#define Left(i) (heap[i*2])       
#define Right(i) (heap[i*2+1])  

void init_heap() { heap_size = 0; }
int is_empty_heap() { return heap_size == 0; }
int is_full_heap() { return (heap_size == MAX_HEAP_NODE - 1); }
HNode find_heap() { return heap[1]; }

void insert_heap(HNode n)
{
    int i;
    if (is_full_heap()) return; 
    i = ++(heap_size); 
    while (i != 1 && Key(n) > Key(Parent(i))) {  
        heap[i] = Parent(i);
        i /= 2;
    }
    heap[i] = n;
}



HNode delete_heap()
{
    HNode hroot, last;
    int parent = 1, child = 2;
    
    if (is_empty_heap() != 0)
        error("힙 트리 공백 에러");
    
    hroot = heap[1];
    last = heap[heap_size--];
    while (child <= heap_size) {
        if (child<heap_size && Key(Left(parent))<Key(Right(parent)))
            child++;
        if (Key(last) >= Key(heap[child]))
            break;
        heap[parent] = heap[child];
        parent = child;
        child *= 2;
    }
    heap[parent] = last;
    return hroot;
}



void print_heap()
{
    int i, level;
    for (i = 1, level = 1; i <= heap_size; i++) {
        if (i == level) {
            printf("\n");
            level *= 2;
        }
        printf("%2d ", Key(heap[i]));
    }
    printf("\n-----------");
}