힙(Heap)

힙이란?

1. 이진 트리의 일종으로, 여러 개의 값 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있도록 구성된 자료구조

 - 최대 힙(Max Heap) : 부모 노드의 값이 항상 하위 노드의 값보다 큰 경우

 - 최소 힙(Min Heap) : 부모 노드의 값이 항상 하위 노드의 값보다 작은 경우

2. 컴퓨터에서 프로세스가 만들어질 때 메모리를 할당하는 데, 이 때 메모리를 할당하는 방법 중 하나.

 

용도

프로세스의 우선순위를 결정하는 방법으로 최대 힙을 사용할 경우.

- 우선순위 숫자가 큰 프로세스가 최상위에 위치한다.

- 프로세스를 요청할 때는 최상위 노드(루트 노드)에 있는 프로세스를 반환한다.

- 루트 노드가 반환되면 나머지 노드를 우선순위 숫자에 근거하여 트리 구조를 재구성하고, 가장 높은 우선순위를 가지는 프로세스가 루트 노드에 위치한다.

 

최대 힙에서의 삽입 과정

1. 기존 힙에 22를 추가할 경우, 일단 22를 힙의 다음 위치에 추가한다.

2. 22가 적당한 위치에 가도록 부모 노드와 계속 자리를 바꾼다.

 

최대 힙에서의 삭제 과정

1. 루트 노드를 삭제할 경우 마지막 노드를 루트 노드 자리에 올린다.

2. 마지막 노드였던 루트 노드가 적당한 위치에 가도록 서브 노드와 계속 자리를 바꾼다.