[HackerRank] QHEAP1 *****

 

https://www.hackerrank.com/challenges/qheap1/problem

QHEAP1 | HackerRank

EASY라고 되어있지만 난이도는 EASY가 아니었던 문제였다.

이 문제는 3가지 query로 이루어져 있다.

1. add 

2. delete

3. print minimum

 

1번은 그냥 heap에 원소를 더하는 것과 같이 하면된다.

3번은 minimum을 출력하는 것으로 Min Heap으로 heap을 구성하였다.

 

2번이 가장 큰 문제였다.

보통 heap에서 delete를 한다고 하면 가장 큰 원소/가장 작은 원소를 지운다.

그러나 이 문제에서 delete를 하려면 delete를 하고자 하는 원소를 지운다. 이 부분이 매우 까다로웠다.

 

heap은 배열로 구성하는게 편하다고 해서 배열로 문제를 풀었다.

 

add함수 같은 경우 다음과 같이 코드를 짰다.

void add(long long item, int *n){
    
    int i;
    
    i=++(*n);
    while(i!=1&&item<heap[i/2]){ //min heap
        heap[i]=heap[i/2];
        i=i/2;
    }
    heap[i]=item;
}

 

add를 할 경우 node의 수가 증가하기 때문에 i에 원래의 노드+1 값을 넣어주었다.

i가 1이 아니고 item<heap[i/2]일동안 heap[i]=heap[i/2](child = parent)를 해주었고 i=i/2를 해주었다.

이것을 해주는 이유는 min heap으로 item이 저장되어야 할 위치를 찾아주어야 되기 때문에 위를 이용하여 item의 위치를 찾아주는 것이다. 

while문에 빠져나와서 heap[i]에 item을 넣어주었다. 

 

min함수는 min heap이기 때문에 root를 리턴한다.

long long min(void){
    return heap[1];
}

 

del함수, min_heap함수, heap_search함수는 연관되어 있다.

 

del함수 인자에 찾고자 하는 item이 전달이 된다.

void del(long long item, int *n){
    int i, parent, child;
    long long val, temp;
    
    i=heap_search(item, *n);
    val = heap[i];
    temp = heap[(*n)--];
    heap[i] = temp;
    
    min_heap(i, *n);
    
}

우리는 그 item의 index값을 알아야 한다. 따라서 heap_search 함수를 이용하여 index의 값을 찾는다.

val에 heap[i](item)의 값을 저장하고 temp에는 heap의 마지막 노드값을 저장하고 노드의 값을 1 줄여준다.

그리고 heap[i]에 temp값을 저장해준다. 이렇게 되면 item값이 heap에서 사라지게 된다.

 

그리고 min_heap함수를 시행한다. min_heap함수는 heap을 min heap으로 만들어준다. 

void min_heap(int i, int n){
    int parent = i, child = 2*i;
    long long temp;
    if(child<=n&&heap[child]<heap[parent])
        parent=child;
    if(child+1<=n&&heap[child+1]<heap[parent])
        parent=child+1;
    if(parent != i){
        temp = heap[i];
        heap[i] = heap[parent];
        heap[parent] = temp;
        min_heap(parent, n);
    }
}

min_heap함수의 인자로는 item의 index, 노드의 개수가 전달이 된다.

 

child(left)가 n개 이하이고 heap[child]<heap[parent]이면 parent=child 해준다. 또한 child+1(right)가 n개이하이고 heap[child+1]<heap[parent]이면 parent에 child+1를 넣어준다. 

 

parent가 i가 아니면(이 말은 parent가 left child/right child와 같다는 얘기. 즉, min_heap을 만족을 못한다는 얘기) i에 있는 원소와 parent에 있는 원소를 바꿔준다. 

 

그리고 다시 min_heap함수를 호출한다. 이때는 parent가 인자로 전달이 되고 노드의 개수는 변함이 없으므로 그대로 n개를 전달한다. 

 

언젠가 min heap을 만족하게 될건데 그때 이 함수를 빠져나올수 있게 된다.