[자료구조] 04 우선순위 큐, 힙

▶ 우선순위 큐 (Priority Queue)

: 산입 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.

: ex) 응급상황

 

 

▶ 배열 기반 우선순위 큐 (단점)

: 데이터 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야 한다.

: 삽입의 위치를 찾기 위해서 배열에 저장된 모든 데이터와 우선순위의 비교를 진행해야 할 수도 있다.

 

 

▶ 연결 리스트 기반 우선순위 큐 (단점)

: 삽입의 위치를 찾기 위해서 첫 번째 노드에서부터 시작해서 마지막 노드에 저장된 데이터와 우선순위의 비교를 진행해야 할 수도 있다.

 

 

▶힙 (Heap)을 이용하는 우선순위 큐 구현

: 위와 같은 단점들로 인해 힙을 이용한다

 

 

▶ 힙 (Heap)

: '이진 트리'이되 '완전 이진 트리'이다.

: 그리고 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다.

: 즉, 루트 노드에 저장된 값이 가장 커야 한다. (최대 힙을 구현하는 경우) (최소 힙은 반대로 구현)

 

 

▶ 배열 기반 힙

왼쪽 자식 노드의 인덱스 값	부모 노드의 인덱스 값 × 2
오른쪽 자식 노드의 인덱스 값	부모 노드의 인덱스 값 × 2 + 1
부모 노드의 인덱스 값	자식 노드의 인덱스 값 ÷ 2

 

 

▶ 연결 리스트 기반 힙 (단점)

: 새로운 노드를 힙의 '마지막 위치'에 추가하는 것이 쉽지 않다.