1. 한쪽 끝과 양쪽 끝 우선순위 큐
우선순위 큐(priority queue) 는 각 원소가 연관된 우선순위를 갖고 있는 원소들의 모임이다.
가령 시스템의 작업 우선도를 설정해 줄 때에는 작업들을 우선 순위에 따라 분류해야 하며, 2개의 서버로 이루어진 시스템의 경우에 하나의 시스템이 사고로 인해 종료되는 경우 반대쪽 서버로 그 작업 내역들이 병합되어야 하는데 이러한 경우 우선순위 큐를 통해 두 작업 리스트를 병합해야 한다.
이러한 우선순위 큐 한쪽 끝 우선순위 큐 와 양쪽 끝 우선순위 큐 가 있으며, 한쪽 끝 우선순위 큐는 최대 우선순위 큐 와 최소 우선순위 큐 로 나뉜다.
최소 우선순위 큐 에 의해 지원되는 연산은 다음과 같다.
SP1. 최소 우선순위를 가진 원소의 반환
SP2. 임의 우선순위를 가진 원소의 삽입
SP3. 최소 우선순위를 가진 원소의 삭제
이러한 우선순위 큐를 잘 표현하기 위한 고전적인 자료 구조로써 히프(heap) 를 사용한다.
양쪽 끝 우선순위 큐는 최소 우선순위 큐와 최대 우선순위 큐가 하나로 합해진 최소-최대 우선순위 큐이다.
실제 활용도 측면에서, 양쪽 끝 우선순위 큐는 네트워크 버퍼를 구현하는 데 사용되는데 네트워크 링크를 통해 전송되기를 원하는 패킷들을 가지고 있는 경우 가장 높은 우선순위를 가진 패킷이 전송되고 삭제 되는 최대 삭제 가 행해지는 반면, 네트워크 내의 다른 곳으로 부터 새로운 패킷이 도착하였는데 버퍼가 가득 차 있다면 우선 순위가 가장 낮은 패킷을 지우는 최소 삭제 가 일어나게 된다. 이처럼 작업 큐의 양쪽에서 삽입과 삭제가 가능한 큐를 양쪽 끝 우선순위 큐라고 부른다.
좌향 트리
좌향트리는 합병성 우선순위 큐의 효율적 구현을 제공한다.
좌향 트리의 종류에는 HBLT(Height Biased Leftist Tree)와 WBLT(Weight Biased Leftist Tree)가 있는데, 일반적으로 HBLT를 좌향트리하고 부른다.
이항히프(B-Heap)
좌향 트리에서 지원되는 것과 같은 기능을 수행한다. 개별적인 연산을 수행하는 데 걸리는 시간보다 우선순위 큐의 순차를 수행하는데 걸리는 시점에 관심이 있다.
이항 히프란 최소 트리의 집합이며, 최소 트리 가운데 최소값을 갖는 트리를 가리키는 하나의 포인터가 가르키게 된다.
Comments