그 외 공부/Algorithm
# 9_Heap
ssangeun
2017. 11. 5. 18:58
# The source code
|
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 |
#include<stdio.h>
#include<stdlib.h>
int data[20] = { 0, 6, 3, 5, 7, 10, 1, 2 };
void swap(int i, int j)
{
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
void findLocation(int cur_idx, int lastidx)
{
int leftidx = cur_idx * 2;
int rightidx = leftidx + 1;
int biggest = cur_idx;
if (leftidx <= lastidx && data[leftidx] > data[cur_idx])
{
biggest = leftidx;
}
if (rightidx <= lastidx && data[rightidx] > data[biggest])
{
biggest = rightidx;
}
if (biggest == cur_idx)
{
return;
}
else // cur_idx가 자기 자리로 가도록 위치를 바꿔준다
{
swap(cur_idx, biggest);
findLocation(biggest, lastidx);
}
}
void heapify(int lastidx)
{
int cur_idx = lastidx / 2;
while (cur_idx >= 1)
{
//cur_idx가 가리키는 노드가 maxheap에서 제자리를 찾도록 재배열
findLocation(cur_idx, lastidx);
cur_idx--;
}
}
void addToheap(int value, int lastidx)
{
int cur_idx = lastidx + 1;
int parent_idx = cur_idx / 2;
data[cur_idx] = value;
while (1)
{
if (data[parent_idx] > data[cur_idx]) return;
else
{
swap(parent_idx, cur_idx);
cur_idx = parent_idx;
parent_idx = cur_idx / 2;
if (parent_idx < 1)
{
return;
}
}
}
}
int removeRoot(int lastidx)
{
int reValue = data[1];
data[1] = data[lastidx];
data[lastidx] = 0;
findLocation(1, lastidx-1);
return reValue;
}
void main(void)
{
int k;
printf("1st : %d \n", data[1]);
heapify(7);
printf("data[1] after heaping : %d \n", data[1]);
addToheap(30, 7);
printf("data[1] after adding : %d \n", data[1]);
k = removeRoot(7);
printf("data[1] after removing root(%d) : %d \n", k, data[1]);
} |
cs |
* heap은 root의 index가 1이므로 배열의 0의 자리는 비워줘야합니다.
# The result
