힙 & 우선순위 큐

우선순위 큐(Priority queue)

큐와 유사하지만 우선순위가 높은 아이템이 먼저 처리되는 큐

우선순위 큐의 주요 동작

• Insert: 우선순위 큐에 데이터 삽입
• Delete: 우선순위 큐의 성질에 따라 제일 상위(최댓값 또는 최솟값) 삭제
• Peek: 우선순위 큐의 성질에 따라 제일 상위(최댓값 또는 최솟값) 확인

힙(Heap)

힙은 주로 이진 트리(Binary tree) 기반으로 구현됨

• 이진 트리: 부모 - 자녀 계층적인 형태를 가지고, 자녀가 최대 두 개인 트리

Max Heap

부모 노드의 키가 자식 노드(들)의 키보다 크거나 같은 트리

Min Heap

부모 노드의 키가 자식 노드(들)의 키보다 작거나 같은 트리

힙의 주요 동작

• Insert: 힙에 데이터 삽입
• Delete: 힙의 성질에 따라 제일 상위(최댓값 또는 최솟값) 삭제
• Peek: 힙의 성질에 따라 제일 상위(최댓값 또는 최솟값) 확인

힙 Insert

아래 Max Heap 기준으로 17을 insert

1. 제일 하위 노드에(2의 오른쪽) 17 삽입

2. max heap 조건 비교 후 위치 변경 반복
   조건: 부모 노드의 키가 자식 노드(들)의 키보다 작거나 같은 트리

2-1. 삽입된 17의 부모노드가 3이므로 위치 변경

2-2. 변경된 위치의 17의 부모 노드가 15이므로 위치 변경

3. max heap 조건이 모두 맞으므로 insert 종료

힙 Delete

아래 Max Heap 기준으로 delete

1. max heap이므로 최댓값인 루트 노드(20) 삭제

2. 현재 트리 구조에서 가장 끝에 있는 노드(2)를 루트 노드로 이동(원래 위치는 삭제)

3. max heap 조건을 충족시키기 위해 선택된 노드(2)와 루트 노드의 자녀 노드를 비교 후 더 큰 자녀 노드와 위치 변경 반복
   조건: 부모 노드의 키가 자식 노드(들)의 키보다 작거나 같은 트리

3-1. 선택된 노드(2)가 자녀 노드들보다 작고 자녀노드인 15, 11 중 15가 더 크기때문에 15와 선택 노드 위치 변경

3-2. 선택된 노드(2)가 자녀 노드들보다 작고 자녀노드인 12, 3 중 12가 더 크기때문에 12와 선택 노드 위치 변경

3-3. 선택된 노드(2)가 자녀 노드들보다 작고 자녀노드인 7, 5 중 7이 더 크기때문에 7과 선택 노드 위치 변경

3. max heap 조건이 모두 delete 맞으므로 종료

Priority queue와 Heap의 관계

힙의 키를 우선순위로 사용한다면 힙은 우선순위 큐의 구현체가 된다.

Heap = 자료 구조(Data Structure)
Priority queue = ADT(Abstract Data Type: 추상 자료형)

Heap은 Priority queue의 구현체 중 하나이다.(일반적으로 우선순위 큐를 힙으로 구현한다.)

우선순위 큐와 힙의 사용 사례

1. 프로세스 스케줄링
   멀티 프로세스 환경에서 P1, P2, P3, P4가 있다면 프로세스마다의 우선 순위를 부여해 가장 우선 순위가 높은 프로세스를 우선으로 수행하는 방법이 존재

2. Heap Sort(힙 정렬)
   N개의 데이터가 존재한다면 전부 힙에 넣고 차례 차례 빼게된다면 해당 데이터는 정렬되어서 나온다.

힙(Heap)메모리도 혹시?
힙 메모리의 힙은 자료 구조 힙과 관련이 없다.