Heap.h

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
#ifndef HEAP_H
#define HEAP_H
 
#include<stdio.h>
#include<memory.h>
#include<stdlib.h>
 
typedef int ElementType;
 
typedef struct tagHeapNode
{
    ElementType Data;
}HeapNode;
 
typedef struct tagHeap
{
    HeapNode* NodeArr;
    int Capacity;
    int UsedSize;
}Heap;
 
Heap* HEAP_Create(int InitialSize);
void HEAP_Destroy(Heap* H);
void HEAP_Insert(Heap* H, ElementType NewData);
void HEAP_DeleteMin(Heap* H, HeapNode* Root);
int HEAP_GetParent(int index);
int HEAP_GetLeftChild(int index);
void HEAP_SwapNode(Heap* H, int index1, int index2);
void HEAP_PrintNodes(Heap* H);
#endif
cs

Heap.cpp

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
#include "Heap.h"
 
Heap* HEAP_Create(int InitialSize)
{
    Heap* NewHeap = (Heap*)malloc(sizeof(Heap));
    NewHeap->Capacity = InitialSize;
    NewHeap->UsedSize = 0;
    NewHeap->NodeArr = (HeapNode*)malloc(sizeof(HeapNode) * NewHeap->Capacity);
 
    printf("size : %d\n", sizeof(HeapNode));
 
    return NewHeap;
}
 
void HEAP_Destroy(Heap* H)
{
    free(H->NodeArr);
    free(H);
}
 
void HEAP_Insert(Heap* H, ElementType NewData)
{
    int CurrentPosition = H->UsedSize;
    int ParentPosition = HEAP_GetParent(CurrentPosition);
 
    if (H->UsedSize == H->Capacity)
    {
        H->Capacity *= 2;
        H->NodeArr = (HeapNode*)
            realloc(H->NodeArr, sizeof(HeapNode) * H->Capacity);
    }
 
    H->NodeArr[CurrentPosition].Data = NewData;
 
    while (CurrentPosition > 0
        && H->NodeArr[CurrentPosition].Data < H->NodeArr[ParentPosition].Data)
    {
        HEAP_SwapNode(H, CurrentPosition, ParentPosition);
        CurrentPosition = ParentPosition;
        ParentPosition = HEAP_GetParent(CurrentPosition);
    }
 
    H->UsedSize++;
}
 
void HEAP_SwapNode(Heap* H, int index1, int index2)
{
    int CopySize = sizeof(HeapNode);
    HeapNode* Temp = (HeapNode*)malloc(CopySize);
 
    memcpy(Temp, &H->NodeArr[index1], CopySize);
    memcpy(&H->NodeArr[index1], &H->NodeArr[index2], CopySize);
    memcpy(&H->NodeArr[index2], Temp, CopySize);
 
    free(Temp);
}
 
void HEAP_DeleteMin(Heap* H, HeapNode* Root)
{
    int ParentPosition = 0;
    int LeftPosition = 0;
    int RightPosition = 0;
 
    memcpy(Root, &H->NodeArr[0], sizeof(HeapNode));
    memset(&H->NodeArr[0], 0, sizeof(HeapNode));
    H->UsedSize--;
    HEAP_SwapNode(H, 0, H->UsedSize);
 
    LeftPosition = HEAP_GetLeftChild(0);
    RightPosition = LeftPosition + 1;
 
    while (1)
    {
        int SelectedChild = 0;
 
        if (LeftPosition >= H->UsedSize)
        {
            break;
        }
        else if (RightPosition >= H->UsedSize)
        {
            SelectedChild = LeftPosition;
        }
        else
        {
            if (H->NodeArr[LeftPosition].Data > H->NodeArr[RightPosition].Data)
            {
                SelectedChild = RightPosition;
            }
            else
            {
                SelectedChild = LeftPosition;
            }
        }
 
        if (H->NodeArr[SelectedChild].Data < H->NodeArr[ParentPosition].Data)
        {
            HEAP_SwapNode(H, ParentPosition, SelectedChild);
            ParentPosition = SelectedChild;
        }
        else
        {
            break;
        }
 
        LeftPosition = HEAP_GetLeftChild(ParentPosition);
        RightPosition = LeftPosition + 1;
    }
    if (H->UsedSize < (H->Capacity / 2))
    {
        H->Capacity /= 2;
        H->NodeArr =
            (HeapNode*)realloc(H->NodeArr, sizeof(HeapNode) * H->Capacity);
    }
}
 
int HEAP_GetParent(int index)
{
    return (int)((index - 1) / 2);
}
 
int HEAP_GetLeftChild(int index)
{
    return (2 * index) + 1;
}
 
void HEAP_PrintNodes(Heap* H)
{
    for (int i = 0; i < H->UsedSize; i++)
    {
        printf("%d ", H->NodeArr[i].Data);
    }
    printf("\n");
}
cs

test file

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
#include "Heap.h"
 
int main()
{
    Heap* H = HEAP_Create(3);
    HeapNode MinNode;
 
    HEAP_Insert(H, 32);
    HEAP_Insert(H, 87);
    HEAP_Insert(H, 111);
    HEAP_Insert(H, 34);
    HEAP_Insert(H, 16);
    HEAP_Insert(H, 75);
    HEAP_PrintNodes(H);
 
    HEAP_DeleteMin(H, &MinNode);
    HEAP_PrintNodes(H);
 
    HEAP_DeleteMin(H, &MinNode);
    HEAP_PrintNodes(H);
 
    HEAP_DeleteMin(H, &MinNode);
    HEAP_PrintNodes(H);
 
    HEAP_DeleteMin(H, &MinNode);
    HEAP_PrintNodes(H);
 
    HEAP_DeleteMin(H, &MinNode);
    HEAP_PrintNodes(H);
    return 0;
}
cs

힙은 가장 작은 자료가 루트에 있는 것을 보장하는 힙 순서 속성(Heap-Order-Property)를 만족하는 이진트리이다.

Heap-Order-Property란 트리 내의 모든 노드가 부모 노드보다 커야 한다는 규칙이다.

 

이 간단한 자료구조를 구현하는데 책에 있는 소스코드를 고쳐서 썼더니 예외가 떴다.

한 3번 정도

 

근데 책 다음 진도를 나가려면 이 책에 있는 힙 소스코드를 먼저 구현해놔야 한다. 

 

그래서 나는 일단 코드를 알아보기 쉽게 만드는 일은 포기했다. 

오늘 안좋은 일도 있어서 머리 안쓰고 무지성으로 코드를 따라쳤다.

오늘 코딩은 힐링(?)이었다.

 

'algorithm & data structure > 자료구조' 카테고리의 다른 글

최소 신장 트리  (2) 2022.12.02
우선순위 큐  (0) 2022.11.29
그래프 구현: 책에 있는 코드를 내 스타일대로 바꿔봤음  (0) 2022.11.27
트리  (0) 2022.11.24
그래프(Graph)  (0) 2022.11.16

+ Recent posts

티스토리툴바