Heap(힙)

이진 탐색 트리에 이어 트리와 유사한 구조를 가진 Heap에 대해서 알아보자.

 

Heap(힙) 이란?

• 들어간 순서에 상관없이 우선 순위를 근거로 dequeue 연산을 진행하는 우선순위 큐의 형태
• Max Heap과 Min Heap 두가지 컨셉이 존재한다.
• 부모와 자식의 key 값은 같은 경우 허용함
• 완전 이진 트리의 형태

 

■ Max Heap

- key 값이 큰 노드가 가장 우선 순위가 높음

- 각 노드의 key 값이 자식의 key 값보다 큰 트리

- 완전 이진 트리

 

 

■ Min Heap

- key 값이 작은 노드가 가장 우선 순위가 높음

- 각 노드의 key 값이 자식의 key 값보다 작은 트리

- 완전 이진 트리

 

1) Heap 삽입 연산(Max Heap에서)

20

15

19

8

13

10

 23을 삽입(배열의 맨 마지막에 삽입 - enqueue연산)

20

15

19

8

13

10

23

23을 트리 구조에서 부모 19와 자리를 바꿈(Max Heap 상태로 변경하는 작업)

20

15

23

8

13

10

19

23을 트리 구조에서 부모 20과 자리를 바꿈(Max Heap 상태로 변경하는 작업)

23

15

20

8

13

10

19

 

Heap 삽입 구현

 

2) Heap 삭제 연산(Max Heap에서)

20

15

14

8

13

10

dequeue 연산이므로 루트 노드 20을 삭제 -> 마지막 노드가 루트 노드 자리로 이동

10

15

14

8

13

Max Heap 구조를 유지하기 위해 다음 가장 큰 숫자 15와 10의 위치를 바꿈

15

10

14

8

13

Max Heap 구조를 유지하기 위해 10과 13의 위치를 바꿈

15

13

14

8

10

 

완전 이진 트리의 형태와 Max Heap 구조가 완성되었으므로 자리 확정하고 삭제 연산 마무리

 

Heap 삭제 구현

 

이렇게 트리 구조와 구조는 같지만 우선순위 큐의 연산을 따르는 Heap(힙)에 대해서 알아보았다.