[자료구조] 우선순위 큐의 이해(1)

[자료구조] 우선순위 큐의 이해(1)

1. 큐 (queue)

큐는 대표적인 자료구조 중 하나이고 선입 선출(FIFO)의 동작을 한다.

즉, 들어간 순서대로 하나씩 빠져나오는 동작 구조이다.

때문에 큐는 선형 구조로 이루어져 있다.

2. 우선순위 큐 (priority queue)

이름이 똑같다고 해서 큐의 연장선에 있다고 생각할 수 없다.

우선순위 큐는 들어가는 순서와 나오는 순서가 상관이 없다.

들어가는 순서에 상관없이 우선순위가 가장 높은 놈이 가장 먼저 나오게 되어있다.

때문에 우선순위 큐는 비선형 자료구조로 이루어져있으며, 큐가 아닌 트리의 연장선상에 있다고 생각해야 한다.

3. 큐의 두 가지 연산

enqueue : 큐에 데이터를 삽입한다.

dequque : 큐에서 데이터를 꺼낸다.

4. 우선순위 큐의 두 가지 연산

enqueue : 우선순위 큐에 데이터를 삽입한다.

dequeue : 우선순위 큐에서 데이터를 꺼낸다. (우선순위를 근거로 deququq 연산이 진행된다.)

어떤 근거로?? --> 프로그래머가 결정할 수 있어야 한다.

5. 우선순위 큐의 구현 방법

1. 배열 기반                --> 구현이 간편하다. 데이터가 많아질 수록 이동과 비교에 대한 부담이 커진다.

2. 연결 리스트 기반    --> 구현이 간편하다. 이동에 대한 부담은 없으나 비교에 대한 부담은 여전하다.

3. 힙(heap) 기반        --> 이동과 비교에 대한 부담이 없다.

6. 그렇다면 힙(heap)이란?

완전 이진 트리이다.

--> 위에서 아래로 왼쪽에서 오른쪽으로 차곡차곡 저장해나가는 이진 트리..

(1) 최대 힙 - 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다.

(2) 최소 힙 - 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 작거나 같아야 한다.

오로지 루트 노드와 자식 노드간의 값만 비교해서 저장해주면 된다.

같은 레벨의 노드에는 어떠한 정렬 기준이 없다.

우선순위 큐가 무엇인지 간단하게 알아보는 시간을 가졌다.

다음 포스팅에는 우선순위 큐를 직접 구현해보도록 하겠다.