[C 자료구조] Heap - QHEAP1

0) 제목

• Hackerrank 의 Heap 부분의 QHEAP1 문제입니다.

• C언어를 이용하여 풀었습니다.

1) 문제 설명 

• 기본적인 배열기반 최소힙 구조입니다.

• minheap을 구현하는 것인데

• 1->insert

• 2->delete

• 3->peek입니다.

• insert 할때에는 변수를 받아서 삽입,

• delete 할때에는 맨위의 최소값을 삭제하는게 아니라, 입력한 변수를 찾아서 삭제,

• peek일때는 minheap의 최소값(root)를 출력하는 문제입니다.

2) 풀이 과정 

• 동적할당을 이용하여 처음 입력 받은 N 에서 N+1 만큼의 용량을 할당했습니다.

• N+1로 동적할당 한 이유는 arr[0]이 아닌 arr[1]부터를 힙의 루트로 사용하는게 더 편리하기 때문입니다.

• HeapInsert 함수는 heap 포인터와 data를 파라이터로 받아서, 받은 data가 올바른 위치에 삽입되도록 하는 함수입니다.

• 맨 아래 노드로 인식한뒤 차례대로 부모노드와 비교하여 스왑하는 생각으로 구현했습니다. (실제로는 마지막에 삽입합니다.) 

• HeapRemove 함수는 Heap 포인터와 찾을 data를 파라미터로 입력 받아서, 삭제하는 함수입니다.

• 이 함수 내부에서 HeapSearch 함수와 Heapify 함수를 호출합니다.

• HeapSearch 함수는 Heap 포인터와 찾을 data를 파라미터로 입력받아서, 

• 해당하는 데이터를 Linear Search를 통해서 찾고, 해당하는 Index(idx)를 반환하는 함수입니다.

• Heapify 함수는 Heap 포인터와 Idx를 입력받습니다. 맨마지막 data 값을 입력받은 idx에 저장 한다고 생각하고(실제로는 마지막에 저장합니다.) 그 idx의 Left, Right child node와 값을 비교해나가면서, heap 을 구축해 나갑니다.

• peek 함수는 heap의 root node의 data를 반환합니다.

3) 코드

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
 
enum {INSERT=1, REMOVE, PEEK};
typedef long long Data;
typedef struct _node{
    Data * arr;
    int numOfData;
} Node;
typedef Node Heap;
 
int getLeftChildIdx(int idx){
    return idx*2;
}
int getRightChildIdx(int idx){
    return idx*2 +1;
}
int getParentIdx(int idx){
    return (int)idx/2;
}
 
void HeapInit(Heap * ph, int n){
    //'+1' because first index of heap is one.
    ph->arr = (Data *)malloc(sizeof(Data) * n +1);
    ph->numOfData =0;
}
void HeapFree(Heap *ph){
    free(ph->arr);
}
 
void Heapify(Heap *ph, int idx){
    int pIdx = idx;
    int cIdx;
    
    Data tmpData = ph->arr[ph->numOfData]; //last data.
    
//왼쪽 자식의 idx와 우측 자식의 idx가 heap의 갯수를 넘지 않고,
//tmpData의 값이 자식(대표:왼쪽) 노드보다 크면
//while내부로 들어가고. 왼쪽 오른쪽 자식들중 더 작은 값을 현재 tmpData와 스왑한다.
    while(tmpData > ph->arr[getLeftChildIdx(pIdx)] 
        && getLeftChildIdx(pIdx) < ph->numOfData
        && getRightChildIdx(pIdx) < ph->numOfData){
    
        if(ph->arr[getLeftChildIdx(pIdx)] < ph->arr[getRightChildIdx(pIdx)]){
            ph->arr[pIdx] = ph->arr[getLeftChildIdx(pIdx)];
            pIdx = getLeftChildIdx(pIdx);
        }else{
            ph->arr[pIdx] = ph->arr[getRightChildIdx(pIdx)];
            pIdx = getRightChildIdx(pIdx);
        }
    }
    
//적절한 위치를 while에서 찾아서 내려왔고, 
//른쪽 자식의 idx가 heap의 갯수를 넘지 않는지 확인 하고 (존재여부확인)
//넘지 않는다면 왼쪽 자식과 비교해서 누가더 작은지 비교 후 tmpData와 비교 및 스왑
//오른쪽 자식이 없다면, 왼쪽 자식의 idx가 heap의
//갯수를 넘지 않는지 확인 하고 (존재여부확인)
//넘지 않는다면 tmpData와 비교 및 스왑
 
    if(getRightChildIdx(pIdx) < ph->numOfData 
        && ph->arr[getLeftChildIdx(pIdx)] > ph->arr[getRightChildIdx(pIdx)]){
        
        if(tmpData > ph->arr[getRightChildIdx(pIdx)]){
            ph->arr[pIdx] = ph->arr[getRightChildIdx(pIdx)];
            pIdx = getRightChildIdx(pIdx);
        }
 
    }else if(getLeftChildIdx(pIdx) < ph->numOfData){
 
        if(tmpData > ph->arr[getLeftChildIdx(pIdx)]){
            ph->arr[pIdx] = ph->arr[getLeftChildIdx(pIdx)];
            pIdx = getLeftChildIdx(pIdx);
        }
    }
    
//마지막에 tmpData를 적절한위치(pIdx)에 삽입.
    ph->arr[pIdx] = tmpData;
}
 
void HeapInsert(Heap *ph, Data data){
    if(ph->numOfData == 0){
        ph->arr[++(ph->numOfData)] = data;
        return ;
    }
    int cIdx = ph->numOfData +1;
    int pIdx = getParentIdx(cIdx);
    
    //find the position.
    while(ph->arr[pIdx] > data && pIdx != 1){
        ph->arr[cIdx] = ph->arr[pIdx];
        cIdx = pIdx;
        pIdx = getParentIdx(pIdx);
    }
    
    if(pIdx ==1 && ph->arr[pIdx] > data) {
        ph->arr[cIdx] = ph->arr[pIdx];
        ph->arr[pIdx] = data;
    }else{
        ph->arr[cIdx] = data;
    }
    (ph->numOfData)++;
 
}
 
//linear Search. 
int HeapSearch(Heap * ph, Data search){
    int i;
    for(i=0;i<ph->numOfData; i++){
        if(ph->arr[i+1] == search)
            return i+1;
    }
    return -1;
}
 
void HeapRemove(Heap *ph, Data search){
    int findIdx;
    findIdx = HeapSearch(ph, search);
    if(findIdx == -1){
        return ;
    }
    Heapify(ph, findIdx);
    (ph->numOfData)--;
}
 
Data peek(Heap * ph){
    return ph->arr[1];
}
 
int main() {
    int i, N, type;
    Heap heap;
    Data data;
    scanf("%d", &N);
    HeapInit(&heap, N);
    for(i=0; i<N; i++){
        scanf("%d", &type);
        switch(type){
            case INSERT:
                scanf("%lld", &data);
                HeapInsert(&heap, data);
                break;
            case REMOVE:
                scanf("%lld", &data);
                HeapRemove(&heap, data);
                break;
            case PEEK:
                printf("%lld\n", peek(&heap));
                break;
        }    
    }
    
    HeapFree(&heap);
    return 0;
}

4)인증

경로 : Dashboard>Data Structures>Heap>QHEAP1

출처 : [HackerRank] https://www.hackerrank.com/challenges/qheap1/problem