테스트 성공!

예아 쎾쓰


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#ifndef NULL
#define NULL 0
#endif // !NULL
 
#define MAX_ELEMENT    200
//#define max(x, y)        (((x) > (y)) ? (x) : (y))
#define swap(x,y, temp)    ((temp)=(x), (x)=(y), (y)=(temp))
 
typedef struct {
    int key;
}Element;
typedef struct {
    Element* arr[MAX_ELEMENT];
    int heapSize;
}Heap;
 
 
void initHeap(Heap* heap);
int insertMaxHeap(Heap* heap, Element* elem);
Element* deleteMaxHeap(Heap* heap);
cs


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
void initHeap(Heap* heap)
{
    int i;
    for(i = 0; i < MAX_ELEMENT; i++) {
        heap->arr[i] = NULL;
    }    
    heap->heapSize = 0;
}
 
//0 success
//1 heap overflow
int insertMaxHeap(Heap* heap, Element* elem)
{
    int index;
 
    if(heap->heapSize > MAX_ELEMENT) {
        printf("heap이 최대크기에 도달하였습니다.");
        return 1;
    }
    else {
        heap->heapSize += 1;
        heap->arr[heap->heapSize] = elem;
 
        index = heap->heapSize;
 
        // while (node isn't root) AND (child.key > parent.key)
        while(index != 1  &&  heap->arr[index]->key > heap->arr[index/2]->key) {    
            Element* tmp = heap->arr[index/2];        // tmp    <= parent            
            heap->arr[index/2] = heap->arr[index];    // parent <= child
            heap->arr[index] = tmp;                    // child  <= tmp
            
            index = index / 2;                    
        }                                    
    }                                
    return 0;    
}
cs


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
 
//return NULL: failed
Element* deleteMaxHeap(Heap* heap)
{
    int i;
    if(heap->heapSize == 0) {
        printf("heap이 비었습니다.");
        return NULL;
    }
 
    // delete root node
    Element* ret = heap->arr[1];
    heap->arr[1] = heap->arr[heap->heapSize];                
    heap->heapSize--;                                        
    
    i = 1;
    while(i <= heap->heapSize) {
        Element* temp = NULL;                                
        // 1. [i]의 자식이
        if(i*2 > heap->heapSize) {        // 1-1. 없다
            break;
        } 
        else if(i*2 == heap->heapSize){    // 1-2. 1개다
            // left_key가 current_key보다 크면 교환
            if(heap->arr[i*2]->key > heap->arr[i]->key){    
                swap(heap->arr[i], heap->arr[i*2], temp);    
                i = i*2;
            } else {
                break; 
            }
        } 
        else {// 1-3. 2개다(대부분의 경우)
            if(heap->arr[i*2]->key > heap->arr[i*2 + 1]->key){// 2-1. right보다 left_key가 클 경우
                //left_key > current_key
                if(heap->arr[i*2]->key > heap->arr[i]->key){    
                    swap(heap->arr[i], heap->arr[i*2], temp);
                    i = i*2;
                } else {
                    break;
                }
            } else {// 2-2. left보다 right_key가 크거나 같은 경우
                //right_key > current_key
                if(heap->arr[i*2 + 1]->key > heap->arr[i]->key){    
                    swap(heap->arr[i], heap->arr[i*2 + 1], temp);
                    i = i*2 + 1;
                } else {
                    break;
                }
            }
        }
    }
    return ret;
}
cs


이제 책에 있는 아름다운 해답 코오드를 보고 좌절할 시간입니다



힙을 만들면 힙소트가 딸려옴!

물로 봤는데 생각보다 어려웠다...


내일은 뭐지소트를 해보겠읍니다.