[ 자료구조 ] Heap

시험장에서 자주 사용하는 Heap에 대해 적어보려한다.

Heap이란, 최솟값이나 최댓값을 빠르게 찾아 내기 위해 고안된 완전이진트리의 일종으로 우선순위큐라고도 불린다.

(적다보니 트리에 대해서도 적어봐야지 싶다)

Heap에는 최대힙(Max Heap), 최소힙(Min Heap)이 있는데 부모 자식노드 관계에 따라 정해진다.

예를들어, A가 B의 부모 노드라면, A의 key값과 B의 key값은 대소관계가 성립한다 (Max는 부모가 key값이 크다)

-> key(T.parent(v)) < key(v) 또는 key(T.parent(v)) > key(v)

 

일반적으로 정렬을 해야할 상황이 생기면 Heap에 모두 넣고, 하나씩 빼면 정렬된 형태로 값을 얻을 수 있어서 자주 사용하며

시간복잡도는 O(logN)으로 Quick sort와 비슷한 속도를 보인다.

상황에 맞게 삽입정렬, 퀵정렬, 힙정렬을 잘 사용해야 하는데 정렬에 대해서도 N의 크기에 따라 어떤걸 사용할지 판단할 수 있어야겠다.

 

아래는 Max Heap에서 삽입이 일어났을때의 예시를 나타낸다.

#define MAX_HEAP 5001
#define swap(a,b,t)((t) = (a), (a) = (b), (b) = (t))

using namespace std;

int heap[MAX_HEAP];
int heap_size = 0;

void insert_heap(int item) {
    heap[++heap_size] = item;
    int index = heap_size;
    int temp;
    
    while (index / 2 >= 1 && heap[index/2] < heap[index]) {
        swap(heap[index], heap[index/2], temp);
        index /= 2;
    }
}

시험장에서는 자주 사용하는 코드에 대해 자신만의 코드가 있으면 빠르게 적용하는데 용이한것같다.

그래서 나만의 insert_heap을 정해놓고 외워두는 편이다.

 

 

아래는 Max Heap에서 삭제에 대한 예시이다.

#define MAX_HEAP 5001
#define swap(a,b,t)((t) = (a), (a) = (b), (b) = (t))

using namespace std;

int heap[MAX_HEAP];
int heap_size = 0;

int delete_heap() {
    int item = heap[1];
    heap[1] = heap[heap_size--];
    int temp;
    int current = 1;
    int child = 2;
    
    while (child <= heap_size) {
        if (child < heap_size && heap[child] < heap[child+1]) child++;
        if (heap[current] > heap[child]) break;
        swap(heap[current], heap[child], temp);
        current = child;
        child *= 2;
    }
    
    return item;
}

delete_heap에 대해서는 다양한 코드가 존재하지만, 본인이 이해한 대로 코드를 작성할줄 아는 능력도 필요한것 같다.

코드를 보고 위에서 예시로 보인 노드의 움직임을 생각할 수 있거나,

노드의 움직임을 보고 아래의 코드를 생각해낼 수 있는 능력이 필요한것 같다.

공부를 한지 몇개월이 지나긴 했지만 아직 생각나는게 신기하기도 하면서도, 처음에 제대로 이해를 했구나 싶다.