우선순위 큐

우선순위 큐 (Priority Queue)

특징

• 우선 순위를 가진 데이터를 저장하는 큐
• 데이터 추출 시 우선순위가 높은 데이터가 추출된다.
• OS의 스케줄링, 정렬, 네트워크 관리 등에 이용된다.

비교

큐 (Queue)

• 선형구조 및 FIFO 구조를 가진다.

우선순위 큐 (Priority Queue)

• 트리 구조와 유사하며, 최대 힙으로 구현한다.

최대힙 구조

• 힙은 항상 완전 이진 트리 구조여야 한다.
• 부모 노드가 항상 자식노드보다 큰 값을 가진 구조
• root가 최대 값을 가진다.

데이터 삽입

• 전체 트리가 최대힙 구조를 유지하도록 코딩할 수 있다.
• 삽입하는 원소는 완전 이진 트리를 유지하는 형태로 삽입한다.
• 삽입 후에 자식 노드보다 크고, 부모 노드보다 작을 때 까지 상향식 이동을 한다.

데이터 삭제

• 데이터를 삭제할 때는 root를 삭제해준다.
• 마지막에 위치하던 노드를 root로 이동시킨다.
• 삭제 후에 부모 노드보다 작고, 자식 노드보다 클 때 까지 하향식으로 이동한다.