우선순위 큐와 힙

우선순위 큐 : 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.

우선순위 큐의 구현 방법

  1. 배열 기반

  2. 연결 리스트 기반

  3. 힙(heap) 이용

힙이라는 자료구조를 이용해서 구현하는 것이 일반적

 

힙 : 완전 이진 트리이다. 그리고 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다. 즉, 루트 노드에 저장된 값이 가장 커야 한다.(값은 말 그대로 값이 될수도 있고 우선순위가 될 수도 있다.)

heap : 무엇인가를 차곡차곡 쌓아올린 더미

최대 힙(max healp) : 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진 트리

최소 힙(min heap) : 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리

 

힙은 우선순위 큐의 구현에 어울리는, 완전 이진 트리의 일종이다.

 

힙에서의 데이터 저장과정

새로운 데이터는 우선 순위가 제일 낮다는 가정하에서 마지막 위치에 저장한다. 그리고 부모 노드와 우선순위를 비교해서 위치가 바뀌어야 한다면 바꾼다. 이를 반복한다.

 

힙에서의 데이터 삭제과정

우선순위 큐의 삭제 : 가장 높은 우선순위의 데이터 삭제

마지막 노드를 루트 노드의 자리로 옮긴 다음에, 자식 노드와의 비교를 통해서 제자리를 찾아가게 한다.

 

배열 기반 데이터 저장의 시간 복잡도 O(n)

배열 기반 데이터 삭제의 시간 복잡도 O(1)

 

연결 리스트 기반 데이터 저장의 시간 복잡도 O(n)

연결 리스트 기반 데이터 삭제의 시간 복잡도 O(1)

 

힙 기반 데이터 저장의 시간 복잡도 O(log2 n)

힙 기반 데이터 삭제의 시간 복잡도 O(log2 n)

 

힙은 배열을 기반으로 구현해야 한다.(연결 리스트 기반이라면 새로운 노드를 힙의 마지막 위치에 추가하는 것이 어렵)

배열을 기반으로 트리를 구성할 때는 맨 앞(0), 마지막을 비워둔다.

 

기억

힙은 완전 이진 트리이다.

힙의 구현은 배열을 기반으로 하며 인덱스가 0인 요소는 비워둔다.

따라서 힙에 저장된 노드의 개수와 마지막 노드의 고유번호는 일치한다.

노드의 고유번호가 노드가 저장되는 배열의 인덱스 값이 된다.

우선순위를 나타내는 정수 값이 작을수록 높은 우선순위를 나타낸다고 가정한다.