-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHeap Sort.html
More file actions
73 lines (62 loc) · 3.03 KB
/
Heap Sort.html
File metadata and controls
73 lines (62 loc) · 3.03 KB
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
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<script>
// 힙 정렬 O(N * log N) - 힙(Heap)을 이용해 데이터를 정렬하면 어떨까?
// 힙 : 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리
// 최대 힙(Max Heap) : 부모 노드가 자식 노드보다 작지만 않으면 된다. + 완전이진트리
// 최소 힙(Min Heap) : 부모 노드가 자식 노드보다 크지만 않으면 된다. + 완전이진트리
// 1. 처음에 최대 힙 만들기 (가장 큰 값이 맨 위 존재하게 됩니다.)
// 2. 루트의 값과 마지막 요소 바꾸기
// 3. 다시 최대 힙 구조 만들기
// 4. 2,3번 반복
let number = 9;
let heap = [7, 6, 5, 8, 3, 5, 9, 1, 6];
// 먼저 전체 트리 구조를 '최대' 힙 구조로 바꿉니다.
for (let i = 0; i < number; i++) {
let c = i;
do {
let root = parseInt((c - 1) / 2); // 특정한 원소(c)의 부모를 가리킵니다.
if (heap[root] < heap[c]) { // 부모 값 < 자식 값
let temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
c = root; // 위치를 바꿨으면, 자식이 부모의 위치로 이동합니다.
} while (c !== 0) // c가 양수일 때만, 작동
// i의 위치에서 점점 0번 인덱스(맨 위)까지 큰값으로 바꿔나갑니다.
} // 데이터 개수(N) * 완전이진트리(log N)
// 크기를 줄여가며, 반복적으로 힙을 구성
for (let i = number - 1; i >= 0; i--) {
let temp = heap[0]; // 맨 뒤 값과, 맨 앞 값 교체
heap[0] = heap[i];
heap[i] = temp;
let root = 0;
let c;
do {
c = (2 * root) + 1; // 왼쪽 자식
// 자식 중에 더 큰 값을 찾기 (자식이 부모에 대해 한 개만 있을 수 있어서 범위를 벗어나지 않게 해야 합니다.)
if (heap[c] < heap[c + 1] && c < i - 1) c++; // 오른쪽 값이 더 크다면, 오른쪽으로 이동
// 루트보다 자식이 더 크다면 교환
if (heap[root] < heap[c] && c < i) {
let temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
root = c; // 그 후, 루트가 그 자식이 됩니다.
} while (c < i);
// 0번 인덱스(맨 위)에서 점점 아래로 더 큰 자식의 값으로 바꿔나갑니다.
}
for (i = 0; i < 10; i++) {
console.log(heap[i]);
}
</script>
</body>
</html>
<!-- https://velog.io/@gnwjd309/data-structure-heap -->