<알고리즘 문제풀이&연습>/[C++] 백준, 프로그래머스 등등

[C 자료구조] Heap - QHEAP1

BlockDMask 2017. 7. 5. 16:33
반응형

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) 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#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;
}
cs


4)인증


경로 : Dashboard>Data Structures>Heap>QHEAP1

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


반응형