힙, heap

완전이진트리에 있는 노드 중에서 키값이 가장 큰 노드 또는 가장 작은 노드를 찾기 위해 만들어진 자료구조

🖐🏻 완전이진트리?
트리의 처음부터 끝까지 왼쪽에서부터 빈 노드 없이 쭈루루룩 짜여진 트리

• 왼쪽부터 차곡차곡 연결되어있으므로 완전이진트리가 맞다.
• 90의 왼쪽자식이 비어있으므로 완전이진트리가 아니다.

• 가장 작은 노드가 루트노드라면? 최소힙
  • 부모 노드는 자식 노드보다 작다.
• 가장 큰 노드가 루트노드라면? 최대힙
  • 부모 노드는 자식 노드보다 크다.

힙의 연산

최대힙의 상황을 가정하였다.

삽입

☝🏻 맨 마지막 자리에 임시 삽입한다.

• 17이 힙에 들어왔다면

이렇게 배치된다.

✌🏻 부모 노드와 크기 조건이 만족하도록 삽입 원소의 위치를 찾는다.

• 현재 부모 노드 >= 삽입된 노드 : 해당 자리 확정
• 현재 부모 노드 < 삽입된 노드 : 서로 자리 바꾸기

삭제

📌 힙은 루트노드만 삭제한다.
b/c 가장 큰 값(또는 가장 작은 값)을 빠르게 찾기 위해 고안된 자료구조이기 때문
즉, 루트 노드를 꺼냈을 때 가장 큰 값(또는 가장 작은 값)을 확인할 수 있다.

☝🏻 루트노드의 원소를 return하고, 트리에서 삭제한다.

✌🏻 재구성 작업을 한다.

• 루트 노드를 삭제한다.
• 가장 마지막 노드를 루트 자리에 놓는다.
• 루트에서부터 자식 노드의 값과 비교한다.
  • 현재 노드 >= 자식 노드 : 자리 확정
  • 현재 노드 < 자식 노드 : 자리 바꾸기

두 자식 모두 13보다 크다.

• 자식끼리 비교한 후 더 큰 자식과 비교한다.
• 더 큰 자식보다 작다면 자리를 바꾼다.

힙의 구현

• 배열로 구현한다.

트리에 배치된 각 노드의 값들은 배열에서 이러한 순서로 배치된다.

• 부모-자식의 index 관계
  • 왼쪽 자식: 부모 index × 2 + 1
  • 오른쪽 자식: 부모 index × 2 + 2

따라서, 삽입과 삭제 연산을 할 때마자 부모와 자식 비교를 index 값으로 접근하여 한다.
제자리를 찾을 때까지 재귀를 돌려 연산한다.