힙이란?

힙

• 우선순위 큐를 구현하는 가장 효율적인 자료구조이다.
• 완전 이진 트리의 일종이며, 여러 개의 값들 중 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
• 반정렬 상태 (느슨한 정렬 상태)를 유지한다.
• 힙 트리에서는 이진 탐색 트리와 달리 중복된 값을 허용한다.
• 배열을 이용하여 구현한다.
• 0번 인덱스는 사용되지 않으며, 특정 위치의 노드번호는 변하지 않는다.

최대 힙

힙을 배열로 구현한 모습

힙의 종류

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

힙의 삽입

• 마지막 노드 다음 노드에 새로운 요소를 삽입한다.
• 삽입한 노드가 부모 노드보다 크면 자리를 바꾼다.
• 부모 노드가 삽입한 노드보다 클 때까지 반복한다.

힙의 삭제

• 힙에서 삭제는 루트 노드를 삭제하는 것이다.
• 루트 노드 자리에는 마지막 노드를 삽입한다.
• 힙을 재구성한다.