[Data Structure] 힙 (heap)

힙(heap)이란?

힙은 일종의 트리로 수의 집합에서 가장 작은 수(키)나 가장 큰 수만을 자주 꺼내올때 유용한 자료구조

 

힙은 완전 이진 트리를 사용하는데 완전이진트리는 자식은 항상 2개, leaf의 가장 왼쪽부터 채우는 트리구조이다.

완전 이진트리 구조 

 

완전 이진 트리 (X)

힙에는 최대힙과 최소힙이 있는데

최소힙은 가장 작은 값이 루트이고 

최대힙은 가장 큰 값이 루트이다.

 

 

1.힙이 삽입(insert) 되는 과정

here 는 현재 삽입될 위치, 인덱스는 8

5와 1을 비교한다. 

1이 더작으므로 5는 here의 자리에 오게된다.

이제 here의 인덱스는 4, 4와 1을 비교한다.

1이 더 작으므로 here의 자리는 4가 들어간다.

마찬가지로 동일하게 1과 2를 비교,

2가 더 크기 때문에 here에는 2가 들어가게 된다.

이제 더이상의 부모는 없으므로 here에는 1이 삽입된다.

 

2.힙을 삭제하는 과정

우선 root에 있는 값을 꺼낸다.

 

 

그리고 가장끝에있는 노드를 (완전이진트리기준) root 위치에 다시 붙인다.

이제 5라는 노드의 자식을 비교해서 위치를 찾아준다.

두 자식이 자신보다 더 작다면 멈춘다.

2 와 6을 비교했을때 2가 더 작고, 2는 5보다 작으므로 2와 5의 위치를 바꾼다.

 

5의 자식인 4와 7을 비교한다.

둘중 4가 더 작고 4는 5보다 작다.

따라서 4와 5의 위치를 바꿔준다.

이제 더이상 내려갈 곳이 없으므로 5의 위치가 정해지게 된다.

 

 

 

 

출처 : https://reakwon.tistory.com/42