우선순위 큐(Priority Queue) & 힙(Heap)

우선순위 큐란?

  -> 우선순위를 근거로 데이터를 뽑는 구조

우선순위 큐의 특징

- 들어간 순서와 나가는 순서가 아무런 상관이 없다.

- 데이터를 뽑을 때 우선순위를 근거로 뽑는다.

- 우선순위를 판단하고 결정하는 건 프로그래머이다.

- 같은 우선순위를 가진다면 먼저 들어온 원소를 처리한다.

- 보통 힙을 통해 우선순위 큐를 구현한다. (배열이나 링크드리스트는 best와 worst의 편차가 크기 때문)

 

힙이란?

- 완전 이진 트리(Complete Binary Tree)이다.

- 부모 노드의 값이 항상 자식 노드들의 값보다 크거나(Max Heap) 작아야(Min Heap)한다.

- 힙으로 우선순위 큐를 구현할 때는 노드에 저장된 값을 우선순위로 본다.

- 힙은 루트 노드에 우선순위가 높은(숫자가 큰-Max Heap/숫자가 작은-Min Heap) 데이터를 위치시키는 자료구조이다.

힙의 삽입

1. 새 노드를 맨 끝 위치에 저장한다. (우선순위가 가장 낮다는 가정) 이 때 완전 이진트리를 만족하는 틀 안에서 이루어져야 한다. 보통 가장 왼쪽에 들어간다.

2. 새 노드와 부모 노드의 우선 순위를 비교해 바꿔야한다면 바꾼다. (위로갈수록 우선 순위가 높다)

3. 바꿀 필요가 없거나 부모 노드가 존재하지 않을 때까지 2번을 반복한다.

힙의 삭제

1. 루트 노드를 비우고 마지막 노드의 값을 루트 노드 자리로 옮긴다.

2. 루트 노드의 자식 노드들과 비교해 우선 순위를 보고 바꿔야한다면 바꾼다. (우선 순위가 더 높은 친구와 바꾼다)

3. 최소 힙의 구조가 나올 때까지 반복한다.