힙(heap) 이란 ?
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
[자료구조] 힙(heap)이란 - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io
그림같은 자료를 가져다 쓴 곳입니다! ( 또한 잘 정리가 되어 있어서 참고 하면서 공부 했습니다. )
"C언어로 쉽게 풀어쓴 자료구조" 를 가지고 공부 중에 있습니다. 책의 내용을 정리해서 쓰고 있습니다.
여기는 그냥 제가 공부한 것을 정리하는 TIL 공간입니다. ( 책과 블로그 글 내용이 비슷하네요 )
우선순위 큐에 대해서는 다른 글에서 따로 정리하려 한다.
힙(heap)의 개념
- 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
- 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
- 힙은 느슨한 정렬 상태를 유지한다. (완전히 정렬된 것은 아니지만, 전혀 정렬이 안된 것도 아님)
- 힙 트리에서는 중복된 값을 허용한다.
- 히프의 목적은 삭제 연산이 수행될 때마다 가장 큰 값을 찾아내기만 하면 되는 것이다(가장 큰 값은 루트 노드)
힙(heap)의 종류
- 최대 힙(max heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
- key(부모 노드) >= key(자식 노드)
- 최소 힙(min heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
- key(부모 노드) <= key(자식 노드)
힙(heap)의 구현
- 힙을 저장하는 표준적인 자료구조는 배열이다.
- 프로그램 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0는 사용되지 않는다.
- 특정 위치의 노드 번호는 새로운 노드가 추가 되어도 변하지 않는다.
힙에서의 부모 노드와 자식 노드의 관계
- 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
- 오른쪽 자식의 인덱스 = (부모의 인덱스) *2 + 1
- 부모의 인덱스 = (자식의 인덱스) / 2
이렇게 각각의 노드들은 1번 인덱스부터 번호가 지정되어 있다. 이진트리 이므로 루트노드의 왼쪽자식은 2번, 오른쪽 자신은 3번 이런식으로 번호를 정하다 보면 위의 공식이 나오게 된다.
힙(heap) 삽입 연산
- 히프에 새로운 요소가 들어오면, 일단 새로운 노드를 히프의 마지막 노드로 삽입된다.
- 따라서 삽입 후에 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시켜 주어야 한다.
이렇게 이론적으로 그림을 통해서 삽입연산을 보면 이해는 잘 된다. 하지만 구현은 정말 쉽지 않았던 것 같다.. 그리고 이진탐색트리에서도 그랬지만, 삽입 연산보다는 삭제연산이 더 어렵다
코드를 읽는거랑 구현하는 건 천지 차이일텐데.. ( 읽는 것도 어렵다. )
이제 자바를 이용해서 최대 힙의 삽입연산을 구현해보자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public class MaxHeapTest {
private ArrayList<Integer> heap;
public MaxHeapTest() {
heap = new ArrayList<>();
heap.add(0); // 인덱스 0번은 버림
}
public void insert(int val) {
heap.add(val);
int p = heap.size()-1;
while (p > 1 && heap.get(p / 2) < heap.get(p)) {
int temp = heap.get(p / 2);
heap.set(p/2, heap.get(p));
heap.set(p, temp);
p = p / 2;
}
}
|
힙(heap 삭제연산
- 최대 힙에서 삭제 연산은 최대값을 가진 요소를 삭제하는 것이다.
- 최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제된다.
이번에는 최대힙의 삭제 연산을 구현해보자.
|
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
|
public int delete() {
if (heap.size()-1 < 1) {
return 0;
}
int deleteItem = heap.get(1);
heap.set(1,heap.get(heap.size()-1));
heap.remove(heap.size()-1);
int parent = 1;
int child = 2;
while (child < heap.size()) {
int max = heap.get(child);
if (child < heap.size()-1 && max < heap.get(child + 1)) {
max = heap.get(child + 1);
child++;
}
if (heap.get(parent) > max) {
break;
}
int temp = heap.get(parent);
heap.set(parent, heap.get(child));
heap.set(child, temp);
parent = child;
child+=2;
}
return deleteItem;
}
|