[Data Structure] 힙

힙이란

힙은 우선순위 큐를 위해 만들어진 자료구조이다. 우선순위 큐란 큐에 우선순위 개념을 도입한 것으로 큐에 들어온 데이터들이 나갈 때는 우선순위에 따르는 것을 말한다. 

 

힙은 완전 이진 트리의 일종으로 여러 값 중 최대값 또는 최소값을 빠르게 찾아내도록 만들어진 자료구조이다. 반정렬 상태이며 이진 탐색 트리와 다르게 중복된 값을 허용한다. 

 

종료

• 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• 최소 힙 : 보모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

 

구현

힙은 배열로 구현한다. 

배열의 인덱스 0은 사용하지 않는다. 

왼쪽 자식 index = 부모 index * 2
오른쪽 자식 index = 부모 index * 2 +1

부모 index = 자식 index / 2

 

삽입

1. 힙에 새로운 요소가 들어온다.
2. 새로운 노드를 힙의 마지막 노드로 삽입
3. 부모 노드와 비교하며 조건에 맞춰 교환한다.

삭제

1. 언제나 루트 노드가 삭제된다.
2. 삭제된 루트 노드에 힙의 마지막 노드를 가져온다.
3. 자식 노드와 비교하며 교환을 통해 힙을 재구성한다.