힙(Heap)

힙이란?

• 완전 이진 트리의 일종으로 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해서 만들어졌다.
• 위에서부터 밑으로 탐색하고, 왼쪽부터 오른쪽으로 탐색한다.
• (부모 노드의 인덱스) = (자식 노드의 인덱스)//2
• (왼쪽 자식 노드의 인덱스) = (부모 노드의 인덱스)*2
• (오른쪽 자식 노드의 인덱스) = (부모 노드의 인덱스)*2+1
• 우선순위 큐를 가장 효율적으로 구현할 수 있다.

우선순위 큐를 구현하는 표현 방법	삽입	삭제
순서 없는 배열	O(1)	O(n)
순서 없는 연결 리스트	O(1)	O(n)
정렬된 배열	O(n)	O(1)
정렬된 연결 리스트	O(n)	O(1)
힙(heap)	O(logn)	O(logn)

↑ 최대 힙 구조

힙의 기능(최대 힙)

1. 삽입

• 힙은 완전 이진 트리이기때문에 기본적으로 왼쪽 하단부 노드부터 저장된다.
• 저장하고 힙은 부모 노드와 비교를 하는데 자신이 부모 노드보다 크다면 부모노드와 자리를 교환하게 된다. 이 동작은 자신이 부모 노드보다 작아질때까지 반복한다.
• 여기서는 값이 100 19 36 17 25 3 120 순서로 들어온다고 가정해본다.

1) 100 삽입

2) 19 삽입(왼쪽부터 저장)

3) 36 삽입(왼쪽에 값이 있으므로 오른쪽 노드에 저장)

4) 17 삽입

• 100의 양쪽에 값이 저장되어 있으므로 왼쪽 자식 노드의 왼쪽에 저장된다.
• 저장된 후 17은 자신의 부모 노드와 비교하여 작은 경우 그대로 저장되고, 만약 크다면 자신의 부모 노드와 자리를 바꾼다.
• 여기서는 부모 노드가 더 크기때문에 그대로 저장된다.

5) 25 삽입

• 마찬가지로 100의 양쪽에 값이 저장되어 있으므로 왼쪽 자식 노드의 오른쪽에 저장된다.
• 여기서 25는 자신의 부모 노드인 19보다 값이 크기 때문에 자리를 바꿔서 저장된다.

6) 3 삽입

• 왼쪽 하단이 모두 채워졌으므로 오른쪽 자식 노드의 왼쪽에 저장된다.

7) 120 삽입

• 오른쪽 자식 노드의 오른쪽에 저장된다.
• 120이 자신의 부모 노드보다 크기 때문에 36과 자리를 바꿔서 저장된다.
• 자리를 바꾼후에 다시 부모 노드와 비교해보면 자신의 부모 노드인 100보다 크기 때문에 다시 자리를 바꿔서 저장된다.
• 더이상 비교할 노드가 없으므로 반복이 종료된다.

2. 제거

• 힙에서 값을 제거하면 그 자리를 채우기 위해 마지막 노드를 가져온다.
• 마지막 노드는 채워진 위치에서 자식노드와 비교하면서 자신이 더 작다면 위치를 변경하면서 저장된다.
• 자신의 자식 노드보다 크거나 더이상 비교할 노드가 없으면 비교를 멈춘다.
• 여기서는 힙의 최댓값 120을 제거해본다.

1) 120 제거

• 힙에서 120을 제거한다.

2) 마지막 노드 가져오기

• 힙에서 가장 마지막 노드인 36을 120자리에 가져오고, 자신의 자식 노드와 비교한다.
• 왼쪽 자식 노드부터 비교를 시작하고, 여기서는 왼쪽 자식 노드인 25보다 크기 때문에 오른쪽 자식 노드도 비교해본다.
• 오른쪽 자식 노드가 36보다 크기 때문에 위치를 교환해서 저장한다.

3) 제거 완료

• 자리를 바꾼 후 다시 자식 노드와 비교한다.
• 현재 자식 노드보다 값이 크기 때문에 비교를 종료하고 제거 동작을 완료한다.