[자료구조] 힙(Heap)

🤔 힙(Heap)이란

힙은 완전 이진 트리로 구현된 자료구조입니다. 완전 이진트리는 마지막을 제외한 모든 노드에서 자식들이 꽉 채워진 이진트리를 말합니다.
부모 노드가 가진 값은 자식 노드의 값보다 무조건 크거나(Max Heap) 작아야(Min Heap)하며, 배열을 통해 구현가능 합니다.

🗂 힙의 종류

최대 힙(max heap)
부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
key(부모 노드) >= key(자식 노드)

최소 힙(min heap)
부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
key(부모 노드) <= key(자식 노드)

➕ 힙의 삽입

1. 새로운 노드를 트리의 맨 뒤에 추가
2. 추가된 노드와 부모 노드를 비교하여 자식 노드가 크다면 서로의 위치 교환
3. 2번 작업을 부모 노드가 더 클 때까지 반복

➖ 힙의 삭제

자료가 삭제되는 경우는 맨 위에있는 Root노드가 빠지는 경우밖에 없다.
그렇게되면 다시 힙의 형태를 갖추어야한다.
1. 맨 뒤에있는 노드를 Root(최상단)자리로 옮김
2. 자식 노드중 값이 더 큰 노드와 비교하여 자식 노드가 값이 더 크다면 위치 교환
3. 2번 작업을 자식노드보다 자신이 더 클 때까지 반복

🔍 힙의 사용 사례

• 시뮬레이션 시스템
• 네트워크 트래픽 제어
• 운영 체제에서의 작업 스케쥴링
• 수치 해석적인 계산