Heap(힙)

Heap

데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리

완전 이진 트리
: 이진 트리에 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리

• (부모 노드의 인덱스) = (자식 노드 인덱스) // 2
• (왼쪽 자식 노드의 인덱스) = (부모 노드의 인덱스) * 2
• (오른쪽 자식 노드의 인덱스) = (부모 노드의 인덱스) * 2 + 1
• 중복 허용

 

종류

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

 

동작

☁️ 삽입

삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워진다.

1️⃣ 15를 왼쪽 최하단 노드에 삽입한다.

2️⃣ 10을 왼쪽 최하단 노드에 삽입한 뒤, 부모와 비교한다. 부모보다 작으므로 그 자리에 위치한다.

3️⃣ 왼쪽 최하단 노드가 이미 있으므로 8을 오른쪽 최하단 노드에 삽입한 뒤, 부모와 비교한다. 부모보다 작으므로 그 자리에 위치한다.

4️⃣ 3을 왼쪽 최하단 노드에 삽입한 뒤, 부모와 비교한다. 부모보다 작으므로 그 자리에 위치한다.

5️⃣왼쪽 최하단 노드가 이미 있으므로 4를 오른쪽 최하단 노드에 삽입한 뒤, 부모와 비교한다. 부모보다 작으므로 그 자리에 위치한다.

 

📍 힙의 데이터보다 클 경우

1️⃣ 20을 왼쪽 최하단부 노드에 삽입한다.

2️⃣ 20의 부모 노드인 8과 비교한다. 20이 더 크므로 8과 위치를 바꾼다. (swap)

3️⃣ 20의 부모 노드인 15와 비교한다. 20이 더 크므로 15와 위치를 바꾼다. (swap)

 

 

☁️ 삭제

데이터가 삭제 된다면 가장 큰 값인 부모 노드의 값이 삭제된다.

1️⃣ 최대값을 갖는 부모 노드를 삭제한다.

2️⃣ 부모 노드가 비었으므로, 가장 최하단부 노드를 루트로 옮긴다.

3️⃣ 부모 노드인 8보다 값이 큰 자식 노드가 있는지 비교한다.1) 왼쪽, 오른쪽 자식 노드 모두 부모 노드보다 클 경우2) 왼쪽, 오른쪽 자식 노드 중 하나만 부모 노드보다 클 경우

 

• 왼쪽 자식 노드와 오른쪽 자식 노드를 비교하여, 더 큰 자식 노드와 부모 노드의 위치를 바꾼다. (swap)
• 둘 중에 부모 노드보다 큰 자식 노드와 부모 노드의 위치를 바꾼다. (swap)