2023. 12. 31. 09:17ㆍ프로그래밍 공부/Data Structure
8.1 우선순위 큐 추상 데이터 타입
우선순위 큐(priority queue):
임의의 요소 삽입은 지원하지만
우선순위의 순서대로 요소를 제거할 수 있는
우선순위의 요소 모음을 저장하기 위한 추상 데이터 타입
이 ADT는 스택, 큐, 데크, 리스트, 심지어 트리와 같은
이전 장에서 논의했던 위치 기반 자료 구조와는 근본적으로 다르다.
이러한 다른 자료 구조는 요소를 특정 위치에 저장하고 있으며,
이는 종종 삽입 및 삭제 작업에 의해 결정되는 요소의 선형 배열로 위치한다.
우선순위 큐 ADT는 우선순위에 따라 요소를 저장하고
사용자에게 "위치"라는 개념을 노출하지 않는다.
8.1.1 키, 우선순위, 전체 순서 관계
응용 프로그램은 일반적으로 집합의 각 개체에 할당된
"키"라는 매개 변수 또는 속성에 따라 개체를 비교해야 한다.
키(key):
어떤 요소에 할당된 객체가
그 요소를 식별하거나 무게를 측정하는 데 사용될 수 있는 특정 속성
키는 일반적으로 사용자 또는 응용 프로그램에 의해 요소에 할당되므로
키는 요소가 원래 가지고 있지 않은 속성을 나타낼 수 있다.
그러나 응용 프로그램이 요소에 할당하는 키는 반드시 고유한 것은 아니며,
응용 프로그램이 필요한 경우 요소의 키를 변경할 수도 있다.
예를 들어,
우리는 수입을 기준으로 또는 직원 수를 기준으로 회사를 비교할 수 있으므로,
추출하려는 정보에 따라 이러한 매개 변수 중 하나를 회사의 키로 사용할 수 있다.
마찬가지로,
우리는 비평가의 음식 품질 평가 또는 평균 진입 가격을 기준으로
레스토랑을 비교할 수 있다.
그 때 가장 일반적인 것을 얻기 위해,
우리는 특정 응용 프로그램에 적합한 모든 타입의 키를 허용한다.
공항의 위 예제들처럼 비교를 위해 사용된 키는
종종 가격, 길이, 무게 또는 속도와 같은 단일 수치 이상이다.
즉, 키는 때때로 하나의 숫자로 정량화될 수 없는 더 복잡한 속성일 수 있다.
예를 들어,
대기 승객의 우선 순위는
일반적으로 상용 고객의 상태, 지불된 요금 및 체크인 시간을 포함한
다양한 요소를 고려하여 결정된다.
일부 응용 프로그램에서 객체의 키는 객체 자체의 일부이다
(예를 들어, 책의 정가를 저장하는 인스턴스 변수이거나 자동차의 무게일 수 있다).
다른 응용 프로그램에서
키는 객체의 일부가 아니라
객체가 응용 프로그램에서 키를 할당받는다
(예를 들어, 재무 분석가가 주식에 부여한 품질 등급 또는
게이트 에이전트가 대기 승객에게 할당한 우선 순위).
키와 전체 순서 비교하기
우선 순위 큐에는 절대 모순되지 않는 비교 규칙이 필요하다.
≤로 표시되는 비교 규칙이 이러한 방식으로 강력하려면
전체 순서(total order) 관계를 정의해야 한다.
즉, 비교 규칙은 모든 키 쌍에 대해 정의되며 다음 속성을 만족해야 한다:
• 반사성(Reflexive property): k ≤ k.
• 반대칭성(Antisymmetric property): k1 ≤ k2이고 k2 ≤ k1이면, k1 = k2이다.
• 추이성(Transitive property): k1 ≤ k2이고 k2 ≤ k3이면, k1 ≤ k3이다.
이 세 가지 특성을 만족하는 어떤 비교 규칙 ≤는 결코 비교 모순을 초래하지 않는다.
사실, 이러한 규칙은 키 집합 사이의 선형 순서 관계를 정의한다.
따라서 (유한) 요소의 컬렉션이 정의된 총 순서를 가진다면,
가장 작은(smallest) 키인 kmin의 개념은
컬렉션의 다른 키 k에 대해 kmin ≤ k인 키로 잘 정의된다.
우선 순위 큐(priority queue):
값(value)이라고 불리는 요소들의 컬렉션이며,
각 요소가 삽입될 때 제공되는 연관된 키를 갖는다.
우선 순위 큐의 엔트리(entry): 우선 순위 큐에 삽입되는 키-값 쌍
"우선 순위 큐"이라는 이름은
제거할 항목을 선택하는 데 사용되는 "우선 순위"를
키가 결정한다는 사실에서 비롯되었다.
우선 순위 큐 P의 두 가지 기본 방법은 다음과 같다:
• insert(k,x): 키가 k인 값 x를 P에 삽입한다.
• removeMin():
키가 가장 작은 엔트리,
즉 키가 P의 다른 모든 엔트리보다 작거나 같은 엔트리를
P에서 반환 및 제거한다.
그런데, 어떤 사람들은 removeMin 메소드를 extractMin 메소드라고 하는데,
이 방법이 엔트리 P를 동시에 제거하고 반환하는 것을 강조하기 위해서이다.
insert와 removeMin 연산이 중요한 역할을 하는 많은 응용 프로그램이 있다.
우리는 다음 예제에서 그러한 응용 프로그램을 고려한다.
예 8.1: 출발 한 시간 전에 특정 항공편이 예약이 다 찼다고 가정해 보겠다.
취소 가능성 때문에 항공사는 다음과 같은 조건을 유지한다
좌석을 희망하는 대기 승객의 우선 순위 대기 줄.
각 대기 승객의 우선 순위는 항공사가 지불한 요금,
비행사의 빈번한 상태 및 승객이
우선 순위 대기 줄에 삽입되는 시간을 고려하여 결정된다.
대기 승객 참조는 대기 비행을 요청하는 즉시
삽입 작업과 함께 우선 순위 대기 줄에 삽입된다.
항공사는 비행 출발 직전에 좌석이 확보되면
(예를 들어, 미표시 또는 막판 취소로 인해),
removeMin 연산을 사용하여
우선 순위 대기 승객을 우선 순위 대기 줄에서 제거하고
이 사람이 탑승하도록 한다.
그런 다음 모든 가능한 좌석이 채워지거나
우선 순위 대기 줄이 비어있을 때까지 이 과정을 반복한다.
8.1.2 엔트리 및 비교기
지금까지 아직도 우리가 결정하지 못한 두 가지 중요한 문제가 남아 있다:
• 키와 값 사이의 연관성을 어떻게 추적할까?
• 가장 작은 키를 결정하기 위해 키를 어떻게 비교할까?
이러한 질문에 답하려면 두 가지 흥미로운 디자인 패턴을 사용해야 한다.
우선 순위 큐의 정의는 위의 질문에 대답하는 두 가지 특별한 종류의 객체,
즉 엔트리와 comparator를 암시적으로 사용하며, 이는 이 하위 섹션에서 논의한다.
엔트리
엔트리(entry): 키 k와 값 x 사이의 연관 관계, 키-값 쌍
Q가 키와 그에 대응하는 값을 연결하는 방식을 추적하기 위해
우선순위 큐 Q의 엔트리를 사용한다.
엔트리는 실제로 보다 일반적인 객체 지향 설계 패턴인 합성 패턴의 한 예로,
다른 객체로 구성된 단일 객체를 정의한다.
우선 순위 큐에 저장되는 엔트리를 키 k와 값 x로 구성된 쌍으로 정의할 때
이 패턴을 우선 순위 큐에 사용한다.
쌍은 두 개의 객체를 하나의 쌍 객체로 결합하기 때문에 가장 간단한 구성이다.
이 개념을 구현하기 위해 두 개의 객체를
각각 첫 번째와 두 번째 인스턴스 변수에 저장하는 클래스를 정의하고
이러한 변수에 액세스하고 업데이트하는 메소드를 제공한다.
코드 조각 8.1에서 우선 순위 큐에 키-값 쌍을 저장하는
엔트리에 대한 합성 패턴의 구현을 보여준다.
Entry라는 인터페이스로 이 구성을 실현한다
(그런데 java.util 패키지에는 유사한 Entry 인터페이스가 포함된다).
다른 종류의 구성에는 세 개의 객체를 저장하는 triple,
네 개의 객체를 저장하는 quadraple 등이 있다.
코드 조각 8.1:
우선순위 큐에 키-값 쌍을 저장하는 엔트리를 위한 자바 인터페이스.
/** Interface for a key-value pair entry **/
public interface Entry<K,V> {
/** Returns the key stored in this entry. */
public K getKey();
/** Returns the value stored in this entry. */
public V getValue();
}
Comparator
우선순위 큐 ADT에서 우리가 정의해야 할 또 다른 중요한 문제는
키를 비교하기 위한 전체 순서 관계를 어떻게 지정하느냐 하는 것이다.
이 시점에서 키를 비교할 수 있는 방법은 여러 가지 디자인 선택 사항이 있다.
한 가지 가능성, 그리고 가장 구체적인 것은
우리가 사용하고자 하는 각 키 타입과
그러한 타입의 키를 비교하는 각 가능한 방법에 대해
다른 우선 순위 큐을 구현하는 것이다.
이 접근법의 문제점은
그것이 그다지 일반적이지 않고
우리가 많은 유사한 코드를 만들어야 한다는 것이다.
대안적인 전략은 키들이 서로 비교할 수 있도록 요구하는 것이다.
이 솔루션을 사용하면 일종의 Comparable 인터페이스를 구현하고
모든 일반적인 비교 메소드를 캡슐화한 키 클래스의 인스턴스를 저장할 수 있는
일반 우선 순위 큐 클래스를 작성할 수 있다.
이 솔루션은 다양한 종류의 키를 처리할 수 있는
단일 우선 순위 큐 클래스를 작성할 수 있기 때문에
특수화된 접근 방식보다 개선된 것이다.
그러나 키들이 비교 방법을 "잘 알지" 못하는 경우가 종종 있기 때문에
이 솔루션이 키에 대해 너무 많은 것을 요구하는 맥락이 있다.
다음 두 가지 예가 있다.
예 8.2: 키 4와 11이 주어졌을 때
키가 (일반적인 방법으로 비교할) 정수 개체일 경우 4≤11,
키가 (사전적으로 비교할) 문자열 개체일 경우 11≤4이다.
예 8.3: 기하학 알고리즘은
평면상의 점 p와 q를 x좌표(즉, x(p) ≤ x(q)일 때 p ≤ q)로 비교하여
왼쪽에서 오른쪽으로 정렬하고,
다른 알고리즘은 y좌표(즉, y(p) ≤ y(q)일 때 p ≤ q)로 비교하여
아래에서 위로 정렬할 수 있다.
원칙적으로 점을 x좌표로 비교할 것인지 y좌표로 비교할 것인지를
나타내는 점의 개념과 관련된 것은 없다.
또한 점을 비교하는 많은 다른 방법을 정의할 수 있다
(예를 들어, 원점에서 p와 q의 거리를 비교할 수 있다).
따라서 가장 일반적이고 재사용 가능한 형태의 우선순위 큐를 사용하기 위해서는
키를 사용하여 비교 규칙을 제공하지 말아야 한다.
대신 키 외부에 있는 특수 comparator 객체를 사용하여 비교 규칙을 제공한다.
comparator는 두 키를 비교하는 객체이다.
P가 구성될 때 우선순위 큐 P가 comparator에 주어진다고 가정하고,
이전 키가 "오래된" 경우에는
우선순위 큐 P에 새로운 comparator가 주어진다고 가정할 수도 있다.
P가 두 키를 비교해야 할 때는 주어진 comparator를 사용하여 비교를 수행한다.
따라서 프로그래머는 다양한 컨텍스트에서 올바르게 작동하는
일반적인 우선순위 큐 구현을 작성할 수 있다.
Comparator ADT
형식적으로 comparator ADT는
두 개의 키를 가져다가 비교하는 단일 방법을 기반으로 하여
간소화된 비교 메커니즘을 제공한다
(또는 키가 비교할 수 없는 경우 오류를 보고한다):
compare(a,b):
a < b이면 i < 0,
a = b이면 i = 0,
a > b이면 i > 0이 되도록
정수 i를 반환한다.
a와 b를 비교할 수 없는 경우 오류가 발생한다.
표준 Java 인터페이스 java.util.Comparator는
위의 comparator ADT에 해당하며
객체를 비교하는 일반적이고 동적이며 재사용 가능한 방법을 제공한다.
또한 comparator를 다른 comparator와 비교하기 위한
equals() 방법도 포함하고 있다.
코드 조각 8.2에서는 2차원 점(코드 조각 8.3)에 대한 comparator의 예를 제공한다.
이는 comparator의 구성 패턴의 예이기도 하다.
코드 조각 8.2: 사전 순서에 기초한 2차원 점에 대한 comparator.
/** Comparator for 2D points under the standard lexicographic order. */
public class Lexicographic<E extends Point2D>
implements java.util.Comparator<E> {
/** Compare two points. */
public int compare(E a, E b) {
if (a.getX() != b.getX())
return b.getX() - a.getX();
else
return b.getY() - a.getY();
}
} // Lexicographic automatically inherits an equals() method from Object
코드 조각 8.3: 평면에서 점을 정수 좌표로 나타내는 클래스.
/** Class representing a point in the plane with integer coordinates */
public class Point2D {
protected int xc, yc; // coordinates
public Point2D(int x, int y) {
xc = x;
yc = y;
}
public int getX() { return xc; }
public int getY() { return yc; }
}
8.1.3 우선순위 큐 ADT
구성 및 comparator 패턴을 설명했으므로
우선 순위 큐 ADT를 정의하여
우선 순위 큐 P에 대해 다음과 같은 방법을 지원한다:
size ():
P의 엔트리 수를 반환한다.
is Empty():
P가 비어 있는지 테스트한다.
min():
키가 가장 작은 P의 엔트리를 반환한다
(그러나 제거하지 않음).
P가 비어 있으면 오류 조건이 발생한다.
insert(k,x):
값 x를 가진 P 키 k에 삽입하고 저장된 엔트리를 반환한다.
k가 유효하지 않으면 오류 조건이 발생한다
(즉, k는 다른 키와 비교할 수 없다).
removeMin():
P에서 제거하고 가장 작은 키로 엔트리를 반환한다.
P가 비어 있으면 오류 상태가 발생한다.
위에서 언급한 바와 같이
우선순위 큐 ADT의 주요 메소드는 insert 및 removeMin 연산이다.
다른 메소드는 쿼리 연산 min과 일반 컬렉션 연산 size와 isEmpty이다.
우선 순위 큐에는 동일한 키를 가진 엔트리가 여러 개 포함될 수 있다.
자바 우선순위 큐 인터페이스
우선순위 큐 ADT에 대한 PriorityQueue라는
Java 인터페이스는 코드 조각 8.4에 나와 있다.
코드 조각 8.4: 우선순위 큐 ADT를 위한 자바 인터페이스.
/** Interface for the priority queue ADT **/
public interface PriorityQueue<K,V> {
/** Returns the number of items in the priority queue. */
public int size();
/** Returns whether the priority queue is empty. */
public boolean isEmpty();
/** Returns but does not remove an entry with minimum key. */
public Entry<K,V> min() throws EmptyPriorityQueueException;
/** Inserts a key-value pair and return the entry created. */
public Entry<K,V> insert(K key, V value) throws InvalidKeyException;
/** Removes and returns an entry with minimum key. */
public Entry<K,V> removeMin() throws EmptyPriorityQueueException;
}
이제 우선순위 큐 ADT가 시퀀스 ADT보다 훨씬 더 간단하다는 것은 분명할 것이다.
우선순위 큐의 요소는 전적으로 키에 따라 삽입되고 제거되지만,
시퀀스의 요소는 위치와 인덱스에 따라 순차적으로 삽입되고 제거되기 때문이다.
예제 8.4: 다음 표는 일련의 연산과 초기에 비어있는 우선순위 큐 P에 대한 영향을 보여준다.
메소드 삽입을 통해 반환된 ei 엔트리 개체로 표시한다.
"Priority Queue" 열은 키별로 정렬된 항목을 보여주기 때문에 다소 속는다.
이는 우선순위 큐에 필요한 것 이상이다.
| 연산 | 출력 | 우선 순위 큐 |
| insert(5,A) | e1[=(5,A)] | {(5,A)} |
| insert(9,C) | e2[=(9,C)] | {(5,A),(9,C)} |
| insert(3,B) | e3[=(3,B)] | {(3,B),(5,A),(9,C)} |
| insert(7,D) | e4[=(7,D)] | {(3,B),(5,A),(7,D),(9,C)} |
| min() | e3 | {(3,B),(5,A),(7,D),(9,C)} |
| removeMin() | e3 | {(5,A),(7,D),(9,C)} |
| size() | e3 | {(5,A),(7,D),(9,C)} |
| removeMin() | e1 | {(7,D),(9,C)} |
| removeMin() | e4 | {(9,C)} |
| removeMin() | e2 | {} |
java.util.PriorityQueue 클래스
Java에 내장된 우선순위 큐 인터페이스는 없지만
Java에는 java.util.PriorityQueue라는 클래스가 포함되어 있다.
그러나 표준 큐 정책인 FIFO 정책에 따라 요소를 추가 및 제거하는 대신
java.util.PriorityQueue 클래스는 우선순위에 따라 해당 항목을 처리한다.
이 우선순위는 생성자의 큐에 전달되는 지정된 comparator 개체에 의해 정의되거나
큐에 저장된 요소의 자연스러운 순서에 의해 정의된다.
java.util.PriorityQueue가 java.util.Queue 인터페이스를 기반으로 하지만
표 8.1과 같이 Entry 인터페이스를 구현하는 클래스 PQEntry가 있다고 가정하면
이 클래스의 메소드와 우선순위 큐 ADT 간의 간단한 대응 관계를 정의할 수 있다.
표 8.1: 우선순위 큐 ADT의 메소드 및 클래스 java.util.PriorityQueue의 해당 메소드이다.
PQEntry 개체에 대한 comparator는
기본적으로 우선순위 큐의 키에 대한 comparator와 동일하다고 가정한다.
java.util.PriorityQueue에는 주요 작업을 위한 한 쌍의 메소드가 있다.
두 메소드는 경계 조건을 처리하는 방법에 약간의 차이가 있지만
유사한 기능을 가지고 있다
(예: 빈 우선 순위 큐에서 제거하려는 메소드).
| 우선 순위 큐 ADT | 클래스 java.util.PriorityQueue |
| size() | size() |
| isEmpty() | isEmpty() |
| insert(k,v) | offer(new PQEntry(k,v)) or add(new PQEntry(k,v)) |
| min() | peek() or element() |
| removeMin() | poll() or remove() |
8.1.4 우선순위 큐를 사용한 정렬
우선 순위 큐의 또 다른 중요한 응용은 정렬이다.
전체 순서 관계에 따라 비교할 수 있는 n개 원소의 집합 S를 부여하고,
증가하는 순서로 정렬하려고 한다.
우선 순위 큐 Q로 S를 정렬하는 알고리즘인
PriorityQueueSort는 매우 간단하며 다음 두 단계로 구성된다:
1. 첫 번째 단계에서 S의 요소를 각 요소에 대해
하나씩 일련의 n개의 insert 연산을 통해
초기 빈 우선 순위 큐 P에 넣는다.
2. 두 번째 단계에서는 일련의 n개의 removeMin 연산을 통해
P에서 원소를 감소하지 않는 순서로 추출하여 다시 S에 넣는다.
코드 조각 8.5에서는
S가 시퀀스라고 가정하고
이 알고리즘에 대한 의사 코드를 제공한다.
시퀀스: 배열 리스트나 노드 리스트와 같은 다른 타입의 컬렉션에 대한 유사 코드
알고리즘은 P를 구현하는 방법에 관계없이
모든 우선 순위 큐 P에 대해 올바르게 작동한다.
그러나 알고리즘의 실행 시간은 insert 및 removeMin 연산의 실행 시간에 의해 결정되며,
이 연산은 P를 구현하는 방법에 따라 달라진다.
실제로 PriorityQueueSort는 우선 순위 큐 P가 구현되는 방법을 지정하지 않으므로
정렬 "알고리즘"보다는 정렬 "체계"로 간주되어야 한다.
PriorityQueueSort 방식은 선택 정렬, 삽입 정렬, 힙 정렬을 포함한
여러 일반적인 정렬 알고리즘의 패러다임이다.
코드 조각 8.5:
알고리즘 PriorityQueueSort 입력 시퀀스 S의 요소는
우선순위 큐 P의 키 역할을 힌다.
Algorithm PriorityQueueSort(S, P):
Input: A sequence S storing n elements, on which a total order relation is
defined, and a priority queue, P, that compares keys using the same total
order relation
Output: The sequence S sorted by the total order relation
while !S.isEmpty() do
e ← S.removeFirst()
P.insert(e, 0) {a null value is used}
while !S.isEmpty() do
e ← P.removeMin().getKey()
S.addLast(e) {the smallest key in P is added to the end of S}
8.2 리스트를 통한 우선순위 큐 구현
이 절에서는 우선순위 큐의 항목을 리스트 S에 저장하여 구현하는 방법을 보여준다.
(6.2장 참조) S의 항목을 키별로 정렬하여 유지하는지 여부에 따라 두 가지 구현을 제공한다.
리스트와 함께 구현된 우선순위 큐의 메소드의 실행 시간을 분석할 때
두 키를 비교하는 데 O(1) 시간이 걸린다고 가정한다.
8.2.1 분류되지 않은 리스트의 구현
우선순위 큐 P의 첫 번째 구현으로서,
리스트 S에 P의 엔트리를 저장하는 것을 고려해 보겠다.
따라서 S의 원소는 엔트리 (k,x)이며, 여기서 k는 키이고 x는 값이다.
빠른 삽입 및 느린 제거
P에 대해 insert(k,x)를 수행하는 간단한 방법은
S에 메소드 addLast(e)를 실행하여
새로운 엔트리 객체 e=(k,x)를 생성하고
리스트 S의 끝에 추가하는 것이다.
이러한 메소드 insert 구현은 O(1) 시간이 걸린다.
위의 삽입 알고리즘은 S가 정렬되지 않을 것임을 암시하는데,
S의 끝에 항상 항목을 삽입하는 것은 키의 순서를 고려하지 않기 때문이다.
따라서 P에 대해 min이나 removeMin 연산을 수행하려면
리스트 S의 모든 요소를 검사하여 최소 k인 S의 엔트리 (k, x)를 찾아야 한다.
따라서 메소드 min과 removeMin은 각각 O(n) 시간이 소요되며,
여기서 n은 메소드를 실행할 때 P의 엔트리 수이다.
또한 이러한 메소드는 각각 최소 키 엔트리를 찾기 위해
전체 리스트를 검색해야 하기 때문에
최상의 경우에도 n에 비례하는 시간으로 실행된다.
즉 섹션 4.2.3의 표기법을 사용하여
이러한 메소드는 θ(n) 시간에서 실행된다고 말할 수 있다.
마지막으로 리스트 S에서 해당 메소드의 출력을 반환하는 것에 의해
메소드 size와 isEmpty를 실행한다.
따라서 정렬되지 않은 리스트를 사용하여 우선순위 큐를 구현함으로써
일정한 시간 삽입을 달성하지만 선형 시간 검색 및 제거를 달성한다.
8.2.2 정렬된 리스트를 통한 구현
우선순위 큐 P의 대안적인 구현은 또한 리스트 S를 사용하지만,
이번에는 키 별로 정렬된 항목을 저장할 수 있다.
특히, 우리는 감소하지 않은 키로 정렬된 항목의 리스트 S를 사용하여
우선순위 큐 P를 표현하는데,
이는 S의 첫 번째 요소가 가장 작은 키를 가진 항목이라는 것을 의미한다.
빠른 제거 및 느린 삽입
이 경우 S의 첫 번째 메소드로 리스트의 첫 번째 요소에 액세스하여
메소드 min을 구현할 수 있다.
마찬가지로 P의 removeMin 메소드를 S.remove(S.first())로 구현할 수 있다.
S가 이중 연결 리스트으로 구현되었다고 가정하면
P의 min 및 removeMin 연산은 O(1) 시간이 걸린다.
따라서 정렬된 리스트을 사용하면
우선 순위 큐 액세스 및 제거 메소드는 간단하고 빠르게 구현할 수 있다.
하지만 지금은 P의 메소드 삽입을 위해서는
리스트 S를 스캔하여 새 엔트리를 삽입할 적절한 위치를 찾아야 한다.
따라서 이제 P의 삽입 메소드를 구현하는 데 O(n) 시간이 걸린다.
요약하면 정렬된 리스트을 사용하여 우선 순위 큐를 구현할 때
최소값을 찾고 제거하는 작업은 일정한 시간에 수행할 수 있지만
삽입은 선형 시간에 실행된다.
두 개의 리스트 기반 구현 비교
표 8.2는 정렬된 리스트과 정렬되지 않은 리스트를 통해
실현된 우선순위 큐 메소드의 실행 시간을 각각 비교한다.
리스트를 사용하여 우선순위 큐 ADT를 구현할 때
흥미로운 상충 관계를 볼 수 있다.
정렬되지 않은 리스트는 빠른 삽입을 허용하지만
쿼리 및 삭제는 느리게 하는 반면
정렬된 리스트는 빠른 쿼리 및 삭제를 허용하지만 삽입은 느리게 한다.
표 8.2: 크기가 n인 우선순위 큐의 메소드 중 최악의 실행 시간으로,
각각 정렬되지 않거나 정렬된 리스트로 실현된다.
리스트가 이중 연결 리스트로 구현된다고 가정한다.
공간 요구 사항은 O(n)이다.
| 메소드 | 정렬되지 않은 리스트 | 정렬된 리스트 |
| size, isEmpty | O(1) | O(1) |
| insert | O(1) | O(n) |
| min, removeMin | O(n) | O(1) |
자바 구현
코드 조각 8.6 및 8.8에서는 정렬된 노드 리스트를 기반으로
우선 순위 큐를 자바로 구현한 것을 보여준다.
이 구현은 MyEntry라는 중첩 클래스를 사용하여
Entry 인터페이스를 구현한다(섹션 6.5.1 참조).
키 k를 우선순위 큐의 comparator과 비교할 수 없는 경우
InvalidKeyException을 던지는 보조 메소드 checkKey(k)를 보여주지 않는다.
자연스러운 순서를 사용하여 comparator를 구현하는 클래스 DefaultComparator는
코드 조각 8.7에 나와 있다.
코드 조각 8.6: PriorityQueue 인터페이스를 구현하는
Java 클래스 SortedListPriorityQueue의 일부이다.
중첩된 클래스 MyEntry는 Entry 인터페이스를 구현한다.
(코드 조각 8.8에서 계속된다.)
import java.util.Comparator;
/** Implementation of a priority queue by means of a sorted node list. */
public class SortedListPriorityQueue<K,V> implements PriorityQueue<K, V> {
protected PositionList<Entry<K,V>> entries;
protected Comparator<K> c;
protected Position<Entry<K,V>> actionPos; // variable used by subclasses
/** Inner class for entries */
protected static class MyEntry<K,V> implements Entry<K,V> {
protected K k; // key
protected V v; // value
public MyEntry(K key, V value) {
k = key;
v = value;
}
// methods of the Entry interface
public K getKey() { return k; }
public V getValue() { return v; }
}
/** Creates the priority queue with the defualt comparator. */
public SortedListPriorityQueue() {
entries = new NodePositionList<Entry<K,V>>();
c = new DefaultComparator<K>();
}
/** Creates the priority queue with the given comparator. */
public SortedListPriorityQueue(Comparator<K> comp) {
entries = new NodePositionList<Entry<K,V>>();
c = comp;
}
코드 조각 8.7: 자연스러운 순서를 사용하여 comparator를 구현하고
클래스 SortedListPriorityQueue의 기본 comparator인
Java 클래스 DefaultComparator.
/** Comparator based on the natural ordering
*/
public class DefaultComparator<E> implements Comparator<E> {
/** Compares two given elements
*/
public int compare(E a, E b) throws ClassCastException {
return ((Comparable<E> a).compareTo(b);
}
}
코드 조각 8.8: PriorityQueue 인터페이스를 구현하는
Java 클래스 SortedListPriorityQueue의 일부.
(코드 조각 8.6부터 계속)
/** Returns but does not remove an entry with minimum key. */
public Entry<K,V> min() throws EmptyPriorityQueueException {
if (entries.isEmpty())
throw new EmptyPriorityQueueException("priority queue is empty");
else
return entries.first().element();
}
/** Inserts a key-value pair and return the entry created. */
public Entry<K,V> insert (K k, V v) throws InvalidKeyException {
checkKey(k); // auxiliary key-checking method (could throw exception)
Entry<K,V> entry = new MyEntry<K,V>(k, v);
insertEntry(entry); // auxiliary insertion method
return entry;
}
/** Auxiliary method used for insertion. */
protected void insertEntry(Entry<K,V> e) {
if (entries.isEmpty()) {
entries.addFirst(e); // insert into empty list
actionPos = entries.first() // insertion position
}
else if (c.compare(e.getKey(), entries.last().element().getKey()) > 0) {
entries.addLast(e);
actionPos = entries.last()
}
else {
Position<Entry<K,V>> curr = entries.first();
while (c.compare(e.getKey(), curr.element().getKey()) > 0) {
curr = entries.next(curr); // advance toward insertion position
}
entries.addBefore(curr,e);
actionPos = entries.prev(curr); // insertion position
}
}
/** Removes and returns an entry with minimum key. */
public Entry<K,V> removeMin() throws InvalidKeyException {
if (entries.isEmpty()) {
throw new EmptyPriorityQueueException("priority queue is empty");
else
return entries.remove(entries.first());
}
8.2.3 선택 정렬 및 삽입 정렬
8.1.4절에서 소개한 PriorityQueSort 기법을 참조하자.
n개의 원소를 포함하는 정렬되지 않은 수열 S가 주어지는데,
이 수열은 두 단계에서 우선순위 큐 P를 사용하여 정렬한다.
단계 1: 모든 원소를 P에 삽입한다.
단계 2: removeMin() 메소드를 사용하여 P에서 원소를 반복적으로 제거한다.
선택 정렬
정렬되지 않은 리스트로 P를 구현하면
PriorityQueueSort의 단계 1에서
각 요소를 O(1) 시간에 삽입할 수 있으므로 O(n) 시간이 걸린다.
단계 2에서 각 removeMin 연산의 실행 시간은 P의 크기에 비례한다.
따라서 병목 계산은 단계 2에서 최소 요소의 반복되는 "선택"이다.
이러한 이유로 이 알고리즘은 선택 정렬이라고 더 잘 알려져 있다.
(그림 8.1 참조)
위에서 언급한 바와 같이, 병목 현상은 우선순위 큐 P에서
키가 가장 작은 엔트리를 반복적으로 제거하는 단계 2에 있다.
P의 크기는 n에서 시작하여
각 removeMin이 0이 될 때까지 점진적으로 감소한다.
따라서 첫 번째 removeMin 연산은 O(n) 시간이 걸리고,
두 번째 연산은 O(n - 1) 시간이 걸리는 등
마지막 (n)번째 연산은 O(1) 시간까지 소요된다.
따라서 단계 2에 필요한 총 시간은
.
명제 4.3에 의해, 다음과 같다.
따라서, 전체 선택 정렬 알고리즘과 마찬가지로
단계 2는 O(n^2) 시간이 걸린다.
그림 8.1: 시퀀스 S = (7,4,8,2,5,3,9)에 대한 선택 정렬의 실행.
삽입 정렬
정렬된 리스트를 사용하여 우선 순위 큐 P를 구현하면
단계 2에서 O(n)까지의 실행 시간이 향상되는데,
P에서 각 연산에 대해 removeMin는 이제 O(1) 시간이 걸린다.
불행히도 최악의 경우
각 삽입 연산은 P의 크기에 비례하는 시간이 걸리기 때문에
단계 1은 실행 시간에 대한 병목 현상이 된다.
따라서 이 정렬 알고리즘의 병목 현상은
정렬된 리스트의 적절한 위치에
새로운 요소를 반복적으로 "삽입"하는 것을 포함하므로
이 정렬 알고리즘은 삽입 정렬이라고 더 잘 알려져 있다(그림 8.2 참조).
그림 8.2: 시퀀스 S = (7,4,8,2,5,3,9)에서 삽입-sort의 실행.
단계 1에서 우리는 P를 구현하는 리스트를 스캔하여
S의 첫 번째 요소를 제거하고
이 요소에 맞는 위치를 찾을 때까지 반복적으로 P에 삽입한다.
단계 2에서 우리는 P를 구현하는 리스트의 첫 번째 요소를 반환하는 P에 대해
removeMin 연산을 반복적으로 수행하고
S의 끝에 요소를 추가한다.
삽입 정렬 단계 1의 실행 시간을 분석하면 다음과 같다
삽입 정렬 단계 1의 실행 시간을 분석하면,
우리는 그것이
다시, 제안 4.3을 호출함으로써,
단계 1은 O(n^2) 시간에 실행되며,
따라서 전체 삽입 정렬 알고리즘도 마찬가지이다.
또는 삽입 정렬의 정의를 변경하여 단계 1에서
우선순위 큐 리스트의 끝에서 시작하는 요소를 삽입할 수 있다.
이 경우에는 이미 정렬된 순서에 대해
삽입 정렬을 수행하는 것이 O(n) 시간에 실행된다.
실제로 삽입 정렬의 실행 시간은 O(n + I)이며,
여기서 I는 순서의 반전 수,
즉 잘못된 상대 순서로 입력 순서에서 시작하는 요소 쌍의 수이다.
8.3 힙
앞 절에서 제시한 PriorityQueueSort 방식의 두 가지 구현은
우선순위 큐 정렬을 위한 실행 시간을 향상시킬 수 있는 가능한 방법을 제시한다.
한 알고리즘(선택 정렬)의 경우
단계 1의 경우 빠른 실행 시간을 달성하지만 단계 2가 느린 반면,
다른 알고리즘(삽입 정렬)의 경우
단계 1이 느리지만 단계 2의 경우 빠른 실행 시간을 달성한다.
두 단계의 실행 시간을 어떻게든 균형 있게 조정할 수 있다면
정렬을 위한 전체 실행 시간을 크게 단축할 수 있을 것이다.
사실 이는 이 절에서 설명한 우선순위 큐 구현을 사용하여 정확히 달성할 수 있는 것이다.
우선순위 큐를 효율적으로 구현하기 위해서는 힙(heap)이라는 자료 구조를 사용해야 한다.
이 자료 구조를 통해 로그 시간으로 삽입과 제거를 모두 수행할 수 있으며,
이는 앞서 8.2절에서 설명한 리스트 기반 구현에 비해 상당히 개선된 것이다.
힙이 이러한 개선을 달성하는 근본적인 방법은
엔트리를 리스트에 저장한다는 생각을 버리고
대신 이진 트리에 엔트리를 저장하는 방식을 택하는 것이다.
8.3.1 힙 자료 구조
힙(heap):
(그림 8.3 참고)
노드들에 엔트리들의 집합을 저장하는 이진 트리 T로서,
두 가지 추가적인 속성을 만족한다.
1. 관계적 속성 - T에 키들이 저장되는 방식으로 정의된다.
2. 구조적 속성 - T 자체의 노드들로 정의된다.
키가 저장되는 방식으로 정의되는 T의 관계적 속성은 다음과 같다:
힙 순서 속성(Heap-Order Property):
힙 T에서 루트를 제외한 모든 노드 v에 대해
v에 저장된 키가 v의 상위에 저장된 키보다 크거나 같다.
힙 순서 속성의 결과로 루트에서 T의 외부 노드로의 경로에서 발견되는 키는
감소하지 않는 순서로 되어 있다.
또한 T의 루트에는 항상 최소 키가 저장된다.
이 키는 가장 중요한 키로서 비공식적으로 "힙의 맨 위에 있다"고 하므로
자료 구조를 "힙"라고 이름 붙인다.
그런데 여기서 정의되는 힙 자료 구조는
자바와 같은 프로그래밍 언어를 지원하는
런타임 환경에서 사용되는 메모리 힙(14.1.2절)와는
아무런 관련이 없다.
만약 우리가 키들 간의 표준 총 차수 관계의 반대를 나타내도록 comparator를 정의한다면
(예를 들어, 비교 (3,2) > 0), 힙의 루트는 가장 큰 키를 준다.
이러한 범용성은 기본적으로 comparator 패턴을 사용함으로써 "무료로" 얻어진다.
comparator에 최소 키를 정의함으로써
"역" comparator가 있는 "최소" 키가 실제로 가장 크다.
그림 8.3: 정수 키로 13개의 엔트리를 저장하는 힙의 예.
마지막 노드는 엔트리(8, W)를 저장하는 노드이다.
따라서 일반성을 잃지 않고 항상 힙의 루트에 있는 최소 키에 관심이 있다고 가정한다.
나중에 명확해질 효율성을 위해,
우리는 힙 T가 가능한 작은 높이를 가지기를 원한다.
우리는 힙 T가 추가적인 구조적 성질:
완전(complete)해야 한다고 주장함으로써 이 요구사항을 시행한다.
이 구조적 성질을 정의하기 전에 몇 가지 정의가 필요하다.
7.3.3절에서 이진 트리 T의 레벨 i는 깊이 i를 갖는 T의 노드 집합임을 기억한다.
T의 같은 레벨에 있는 노드 v와 w가 주어졌을 때,
T의 차수별 순회에서 w보다 v가 먼저 접하면
v는 w의 왼쪽에 있다고 말한다.
즉, v가 u의 왼쪽 부분 트리에 있고
w가 u의 오른쪽 부분 트리에 있는
T의 노드 u가 있다.
예를 들어, 그림 8.3의 이진 트리에서,
노드 저장 엔트리 (15,K)는 노드 저장 엔트리 (7, Q)의 왼쪽에 있다.
이진 트리의 표준 도면에서 "좌측에" 관계는
노드들의 상대적인 수평 배치에 의해 시각화된다.
완전 이진 트리 속성:
1) T의 레벨 0,1,2,...,h - 1이 가능한 최대 노드 수를 가지고 있다.
(즉, 레벨 i에는 0≤i≤h-1의 경우 2^i개의 노드가 있다.)
2) 레벨 h - 1에서는 모든 내부 노드가 외부 노드의 왼쪽에 있다.
3) 자식이 하나인 노드가 많아야 하나이며 이 노드는 왼쪽 자식이어야 한다.
1),2), 3)을 모두 만족한다면
높이 h를 가진 힙 T는 완전 이진 트리(complete binary tree)이다.
힙 T가 완성되어야 한다고 주장함으로써,
우리는 힙 T에서 루트 이외의 또 다른 중요한 노드,
즉 T의 마지막 노드를 찾아내고,
이것을 T의 가장 오른쪽이고 가장 깊은 외부 노드라고 정의한다(그림 8.3 참조).
힙의 높이
T의 높이를 h라고 하자.
T의 마지막 마디를 정의하는 다른 방법은
T의 왼쪽에 있는 모든 다른 마디 h가 있는 h의 마디라는 것이다.
T가 완전하다고 주장하는 것도
명제 8.5에 나타난 것처럼 중요한 결과를 가져온다.
명제 8.5: n개의 항목을 저장하는 힙 T의 높이는 h = logn 이다.
정당화 : T가 완전하다는 사실로부터, T의 노드 수는 적어도
1+2+4+...+2^(h−1) +1=2^h − 1 + 1
= 2^h.
이 하한은 레벨 h에 단 하나의 노드가 있을 때 달성된다.
또한, T가 완전한 것을 따라서, T의 노드 수는 많아야 한다
1+2+4+...+2^h =2^(h+1) −1.
이 상한은 레벨 h가 2h개의 노드를 가질 때 달성된다.
노드의 수는 엔트리의 수 n과 같으므로
2^h ≤ n 그리고 n≤2^(h+1) -1
을 얻는다.
따라서, 이 두 부등식의 양변에 로그를 취하면,
h ≤ log n 그리고 log(n + 1) − 1 ≤ h
임을 알 수 있다.
그는 정수이므로 위의 두 부등식은 h=log n임을 의미한다.
명제 8.5는 중요한 결과를 가져오는데,
왜냐하면 우리가 힙의 높이에 비례하는 시간에 맞추어
업데이트 연산을 수행할 수 있다면
그 연산들은 로그 타임으로 실행된다는 것을 의미하기 때문이다.
그러므로 힙을 사용하여
다양한 우선순위 큐 메소드를
효율적으로 수행하는 방법에 대한 문제로 넘어가겠다.
8.3.2 완전 이진 트리와 그 표현
완전 이진 트리와 그 트리가 어떻게 표현되는지에 대해 더 자세히 설명하겠다.
완전 이진 트리 ADT
완전 이진 트리 ADT는 추상 데이터 타입으로서
이진 트리 ADT의 모든 메소드와 다음 두 가지 메소드를 지원한다(섹션 7.3.1):
add(o): T에 추가하고 새로운 외부 노드 v 저장 요소 o를 반환하여
결과 트리가 마지막 노드 v를 갖는 완전한 이진 트리가 되도록 한다.
remove(): T의 마지막 노드를 제거하고 요소를 반환한다.
이러한 업데이트 연산만을 사용하는 것은
항상 완전한 이진 트리를 갖게 된다는 것을 보장한다.
그림 8.4에서 보는 바와 같이, add 또는 remove의 효과에는 두 가지 경우가 있다.
구체적으로, add에 대해서는 다음과 같다(remove도 이와 유사하다).
• T의 맨 아래 레벨이 가득 차 있지 않은 경우
add는 T의 맨 아래 레벨의 가장 오른쪽 노드(즉, 마지막 노드) 바로 뒤에 새 노드를 삽입한다.
따라서 T의 높이는 그대로 유지된다.
• 맨 아래 레벨이 꽉 차면
T 맨 아래 레벨의 가장 왼쪽 노드의 왼쪽 자식으로 새 노드를 추가한다.
따라서 T의 높이가 1씩 증가한다.
그림 8.4: 완전한 이진 트리에 대한 덧셈과 제거 연산의 예 w는
덧셈에 의해 삽입된 노드 또는 제거에 의해 삭제된 노드이다.
(b)와 (d)에 표시된 트리는
각각 (a)와 (c)에 있는 트리에 대해 덧셈 연산을 수행한 결과이다.
마찬가지로 (a)와 (c)에 표시된 트리도
각각 (b)와 (d)에 있는 트리에 대해 제거 연산을 수행한 결과이다.
완전한 이진 트리의 배열 리스트 표현
배열 리스트 이진 트리 표현(섹션 7.3.5)은 완전한 이진 트리 T에 특히 적합하다.
이 구현에서 T의 노드는 배열 리스트 A에 저장되므로
T의 노드 v는 다음과 같이 정의되는
v의 레벨 수 p(v)와 같은 인덱스를 가진 A의 원소이다:
• v가 T의 근이면 p(v) = 1이다.
• v가 노드 u의 왼쪽 자식이면 p(v) = 2p(u)이다.
• v가 노드 u의 오른쪽 자식이면 p(v) = 2p(u) + 1이다.
이 구현을 통해 T의 노드는 [1,n] 범위의 연속 인덱스를 가지며,
T의 마지막 노드는 항상 인덱스 n에 있으며,
여기서 n은 T의 노드 수이다.
그림 8.5는 마지막 노드의 이러한 특성을 보여주는 두 가지 예를 보여준다.
그림 8.5: n개의 노드가 있는 힙의 마지막 노드 w가 레벨 번호 n임을 보여주는 두 가지 예:
(a) 하단 레벨에 둘 이상의 노드가 있는 힙 T1;
(b) 하단 레벨에 하나의 노드가 있는 힙 T2;
(c) T1의 배열 리스트 표현;
(d) T2의 배열 리스트 표현.
완전한 이진 트리 T를 배열 리스트로 표현함으로써 얻을 수 있는 단순화는
메소드 add 및 remove에 도움이 된다.
메소드 add 및 remove는
단순히 배열 리스트의 마지막 요소를 추가하거나 제거하는 것이기 때문에
배열 확장이 필요 없다고 가정하면 O(1) 시간 내에 수행할 수 있다.
또한 T와 관련된 배열 리스트에는 n + 1개의 요소가 있다
(인덱스 0의 요소는 자리 표시자).
배열 리스트 구현을 위해 성장 및 축소되는 확장 가능한 배열을 사용하면
(섹션 6.1.4 및 연습 C-6.2),
노드가 n개인 완전한 이진 트리의 배열 리스트 표현에 사용되는 공간은 O(n)이며,
O(1) 분할 시간이 소요된다.
완전한 이진 트리의 Java 구현
저희는 코드 조각 8.9에 표시된
CompleteBinaryTree 인터페이스에서 완전 이진 트리 ADT를 나타낸다.
저희는 배열 리스트과 함께 CompleteBinaryTree 인터페이스를 구현하는
Java 클래스 ArrayListCompleteBinaryTree를 제공하며
코드 조각 8.10-8.12에서
O(1) 시간 내에 add 및 remove 메소드를 지원한다.
코드 조각 8.9: 완전 이진 트리를 위한 인터페이스 CompleteBinaryTree.
public interface CompleteBinaryTree<E> extends BinaryTree<E> {
public Position<E> add(E element);
public E remove();
}
코드 조각 8.10:
java.util.ArrayList를 이용한
인터페이스 CompleteBinaryTree를 구현하는
클래스 ArrayListCompleteBinaryTree
(코드 조각 8.11에서 계속됨)
public class ArrayListCompleteBinaryTree<E>
implements CompleteBinaryTree<E> {
protected ArrayList<BTPos<E>> T; // indexed list of tree positions
/** Nested class for a index list-based complete binary tree node. */
protected static class BTPos<E> implements Position<E>;
E element; // element stored at this position
int index; // index of this position in the array list
public BTPos(E elt, int i) {
element = elt;
index = i;
}
public E element() { return element; }
public int index() { return index; }
public E setElement(E elt) {
E temp = element;
element = elt;
return temp;
}
}
/** default constructor */
public ArrayListCompleteBinaryTree() {
T = new ArrayList<BTPos<E>>();
T.add(0,null); // the location at rank 0 is deliberately empty
}
/** Returns the number of (internal and external) nodes. */
public int size() { return T.size() - 1; }
/** Returns whether the tree is empty. */
public boolean isEmpty() { return (size() == 0); }
코드 조각 8.11: 완전한 이진 트리 ADT를 구현하는
클래스 ArrayListCompleteBinaryTree.
(코드 조각 8.12에서 계속)
/** Returns whether v is an internal node. */
public boolean isInternal(Position<E> v) throws InvalidPositionException {
return hasLeft(v); // if v has a right child it will have a left child
}
/** Returns whether v is an external node. */
public boolean isExternal(Position<E> v) throws InvalidPositionException {
return !isInternal(v);
}
/** Returns whether v is the root node. */
public boolean isRoot(Position<E> v) throws InvalidPositionException {
BTPos<E> vv = checkPosition(v);
return vv.index() == 1;
}
/** Returns whether v has a left child. */
public boolean hasLeft(Position<E> v) throws InvalidPositionException {
BTPos<E> vv = checkPosition(v);
return 2*vv.index() <= size();
}
/** Returns whether v has a right child. */
public boolean hasRight(Position<E> v) throws InvalidPositionException {
BTPos<E> vv = checkPosition(v);
return 2*vv.index() + 1 <= size();
}
/** Returns the root of tree. */
public Position<E> root() throws EmptyTreeException {
if (isEmpty()) throw new EmptyTreeException("Tree is empty");
return T.get(1);
}
/** Returns the left child of v. */
public Position<E> left(Position<E> v)
throws InvalidPositionException, BoundaryViolationException {
if (!hasLeft(v)) throw new BoundaryViolationException("No left child");
BTPos<E> vv = checkPosition(v);
return T.get(2*vv.index());
}
/** Returns the right child of v. */
public Position<E> right(Position<E> v)
throws InvalidPositionException, BoundaryViolationException {
if (!hasRight(v)) throw new BoundaryViolationException("No right child");
BTPos<E> vv = checkPosition(v);
return T.get(2*vv.index() + 1);
}
코드 조각 8.12: 클래스 ArrayListComplete BinaryTree
완전한 이진 트리 ADT를 구현한다.
메소드 children 및 positions는 생략된다.
(코드 조각 8.11부터 계속)
/** Returns the parent of v. */
public Position<E> parent(Position<E> v)
throws InvalidPositionException, BoundaryViolationException {
if (isRoot(v)) throw new BoundaryViolationException("No parent");
BTPos<E> vv = checkPosition(v);
return T.get(vv.index()/2);
}
/** Replaces the element at v. */
public E replace(Position<E> v, E o) throws InvalidPositionException {
BTPos<E> vv = checkPosition(v);
return vv.setElement(o);
}
/** Adds an element just after the last node (in a level numbering). */
public Position<E> add(E e) {
int i = size() + 1;
BTPos<E> p = new BTPos<E>(e, i);
T.add(i, p);
return p;
}
/** Removes and returns the element at the last node. */
public E remove() throws EmptyTreeException {
if (isEmpty()) throw new EmptyTreeException("Tree is empty");
return T.remove(size()).element();
}
/** Determines whether the given position is a valid node. */
protected BTPos<E> checkPosition(Position<E> v)
throws InvalidPositionException
{
if (v == null || !(v instanceof BTPos))
throw new InvalidPositionException("Position is invalid");
return (BTPos<E>) v;
}
/** Returns an iterator of the elements stored at all nodes in the tree. */
public Iterator<E> iterator() {
ArrayList<E> list = new ArrayList<E>();
Iterator<BTPos<E>> iter = T.iterator();
iter.next(); // skip the first element
while (iter.hasNext())
list.add(iter.next().element());
return list.iterator();
}
}
8.3.3 힙으로 우선순위 큐 구현
이제 힙을 사용하여 우선순위 큐를 구현하는 방법에 대해 설명한다.
우선순위 큐 P에 대한 힙 기반 표현은 다음과 같다(그림 8.6 참조):
• 힙(heap), 내부 노드들이 힙 순서 속성이 만족되도록 엔트리들을 저장하는 완전 이진 트리 T.
T가 8.3.2절에 기술된 바와 같이 배열 리스트를 사용하여 구현된다고 가정한다.
T의 각 내부 노드 v에 대하여 v에 저장된 엔트리의 키를 k(v)로 표시한다.
• comp, 키 간의 전체 순서 관계를 정의하는 comparator이다.
이 자료 구조를 사용하면
메소드 size 및 isEmpty가 평소와 같이 O(1) 시간이 걸린다.
또한, 메소드 min은 배열 리스트의 인덱스 1에 있는
힙의 루트에 저장된 엔트리에 액세스하여
O(1) 시간으로 쉽게 수행할 수 있다.
삽입
힙 T로 구현된 우선순위 큐에 insert를 수행하는 방법을 고려해 보겠다.
T에 새로운 엔트리(k,x)를 저장하려면
연산 add와 함께 새로운 노드 z를 T에 추가하여
이 새로운 노드가 T의 마지막 노드가 되도록 하고 엔트리 (k,x)를 저장한다.
이 작업이 끝나면 트리 T는 완료되지만 힙 순서 속성을 위반할 수 있다.
따라서 노드 z가 T의 루트가 아닌 이상
(즉, 삽입 전에 우선순위 큐가 비어 있었다),
키 k(z)를 z의 부모 u에 저장된 키 k(u)와 비교한다.
k(z) ≥ k(u)이면 힙 순서 속성이 만족되고 알고리즘이 종료된다.
대신 k(z) < k(u)이면 힙 순서 속성을 복원해야 하며,
z와 u에 저장된 엔트리를 교환하여 지역적으로 얻을 수 있다.
(그림 8.7c와 d 참조) 이 교환으로 인해
새로운 엔트리 (k,e)가 한 단계 위로 이동한다.
다시 힙 순서 속성이 위반될 수 있으며,
힙 순서 속성을 위반하지 않을 때까지 T에서 계속 교환한다.
(그림 8.7e와 h 참조)
그림 8.6: 우선 순위 큐의 힙 기반 구현 예시.
그림 8.7: 키가 2인 새 엔트리를 그림 8.6의 힙에 삽입:
(a) 초기 힙;
(b) add 연산을 수행한 후;
(c 및 d) 부분 순서 속성을 지역적으로 복원하도록 교환한다;
(e 및 f) 또 다른 교환;
(g와 h) 최종 교환.
up-heap bubbling: 교환(swap)을 통해 새로 삽입된 엔트리를 위로 이동하는 것
스왑은 힙-오더 속성의 위반을 해결하거나 힙에서 한 단계 위로 전파한다.
최악의 경우 up-heap bubbling으로 인해
새로운 엔트리가 힙 T의 루트까지 이동하게 된다(그림 8.7 참조).
따라서 최악의 경우 메소드 insert 실행 시 수행되는 교환 수는 T의 높이와 같으며,
즉 명제 8.5에 의해 log n이 된다.
제거
이제 우선순위 큐(ADT)의 메소드 removeMin을 알아보겠다.
힙 T를 이용하여 메소드 removeMin을 수행하는 알고리즘은 그림 8.8과 같다.
키가 가장 작은 엔트리는 (키가 가장 작은 엔트리가 두 개 이상 있더라도)
T의 루트 r에 저장된다는 것을 알고 있다.
그러나 R이 T의 유일한 내부 노드가 아닌 이상,
이진 트리 구조를 방해하기 때문에 단순히 노드 r을 삭제할 수는 없다.
대신 T의 마지막 노드 w에 접근하여 해당 엔트리를 루트 r에 복사한 다음,
완전한 이진 트리 ADT의 연산 remove를 수행하여 마지막 노드를 삭제한다.
(그림 8.8a와 b 참조)
제거 후 Down-Heap Bubbling
그러나 T가 이제 완료되었다고 하더라도
T가 힙 순서 속성을 위반할 수 있기 때문에
반드시 완료되는 것은 아니다.
T에 노드가 하나만 있으면
힙 순서 속성은 사소한 것으로 만족되고 알고리즘은 종료된다.
그렇지 않으면 두 경우를 구별하는데, r은 T의 루트를 나타낸다:
• r에게 오른쪽 자식이 없다면 r의 왼쪽 자식이 되라.
• 그렇지 않은 경우(r은 두 자식을 모두 갖는다),
키가 가장 작은 r의 자식이라고 가정하자.
k(r) ≤ k(s)이면 힙 순서 속성이 만족되고 알고리즘이 종료된다.
대신 k(r) > k(s)이면 r과 s에 저장된 엔트리를 교환하여
로컬로 얻을 수 있는 힙 순서 속성을 복원해야 한다.
(그림 8.8c와 d 참조) (s의 형제와 r을 교환하면 안 된다.)
수행하는 교환은 노드 r과 그 자식에 대한 힙 순서 속성을 복원하지만
s에서 이 속성을 위반할 수 있으므로
힙 순서 속성을 위반하지 않을 때까지
T를 계속 교환해야 할 수도 있다.
(그림 8.8e와 h 참조)
down-heap bubbling: 하향식 교환 과정
교환은 힙 순서 속성의 위반을 해결하거나 힙에서 한 단계 아래로 전파한다.
최악의 경우 엔트리가 맨 아래 레벨까지 이동한다. (그림 8.8 참조)
따라서 메소드 removeMin 실행 시 수행되는 교환 수는
최악의 경우 힙 T의 높이와 같으며,
즉 명제 8.5에 의해 log n된다.
그림 8.8: 힙에서 가장 작은 키를 가진 엔트리의 제거:
(a와 b) 마지막 노드 삭제,
(c와 d) 힙 순서 속성을 로컬로 복원하는 교환,
(e와 f) 또 다른 교환,
(g와 h) 최종 교환.
분석
표 8.3은 우선순위 큐의 힙 구현을 위한
우선순위 큐 ADT 메소드의 실행 시간을 나타낸 것으로,
두 개의 키를 O(1) 시간으로 비교할 수 있고
힙 T가 배열 리스트 또는 연결 구조로 구현되어 있다고 가정한다.
표 8.3: 힙을 통해 구현되는 우선순위 큐의 성능으로
배열 리스트 또는 연결 구조로 구현된다.
메소드를 실행할 때 우선순위 큐의 엔트리 수를 n으로 표시한다.
공간 요구 사항은 O(n)이다.
힙의 배열 리스트 구현 시
insert와 removeMin 연산의 실행 시간은 최악의 경우이며
연결된 표현을 위해 분할 상환된다.
| 연산 | 시간 |
| size, isEmpty | O(1) |
| min | O(1) |
| insert | O(logn) |
| removeMin | O(logn) |
간단히 말해서, 각 우선순위 큐 ADT 메소드는
O(1) 또는 O(logn) 시간으로 수행할 수 있다.
n: 메소드를 실행할 때의 엔트리 수
메소드의 실행 시간 분석은 다음을 기반으로 한다:
• 힙 T는 n개의 노드를 가지며, 각각은 엔트리에 대한 참조를 저장한다.
• T에 대한 add 및 remove 연산은 O(1) 분할 상환 시간(배열 리스트 표현) 또는 O(logn) 최악의 경우 시간이 소요된다.
• 최악의 경우, up-heap 및 down-heap bubbling은 T의 높이와 동일한 수의 교환을 수행한다.
• 힙 T의 높이는 O(logn)이며, 이는 T가 완료되었기 때문이다(명제 8.5).
힙 자료 구조가 우선 순위 큐 ADT의 매우 효율적인 실현이며,
힙이 연결 구조로 구현되었는지 배열 리스트로 구현되었는지 여부와는 무관하다고 결론지었다.
힙 기반 구현은 리스트 기반 우선 순위 큐 구현과 달리
삽입 및 제거 모두에서 빠른 실행 시간을 달성한다.
실제로 힙 기반 구현의 효율성의 중요한 결과는
우선 순위 큐 정렬을 리스트 기반 삽입 정렬 및 선택 정렬 알고리즘보다
훨씬 빠르게 할 수 있다는 것이다.
8.3.4 자바 힙 구현
힙 기반 우선순위 큐의 자바 구현은 코드 조각 8.13-8.15에 나와 있다.
모듈화를 돕기 위해 힙 자체의 구조 유지 보수를 완전 이진 트리에 위임한다.
코드 조각 8.13:
클래스 HeapPriorityQueue 이며, 이는 힙으로 우선순위 큐를 구현한다.
중첩 클래스 MyEntry는 힙 트리의 요소를 구성하는 우선순위 큐의 엔트리에 사용된다.
(코드 조각 8.14에서 계속된다.)
/**
* Realization of a priority queue by means of a heap. A complete
* binary tree realized by means of an array list is used to
* represent the heap.
*/
public class HeapPriorityQueue<K,V> implements PriorityQueue<K,V> {
protected CompleteBinaryTree<Entry<K,V>> heap; // underlying heap
protected Comparator<K> comp; // comparator for the keys
/** Inner class for heap entries. */
protected static class MyEntry<K,V> implements Entry<K,V> {
protected K key;
protected V value;
public MyEntry(K k, V v) { key = k; value = v; }
public K getKey() { return key; }
public V getValue() { return value; }
public String toString() { return "(" + key + "," + value + ")"; }
}
/** Creates an empty heap with the default comparator */
public HeapPriorityQueue() {
heap = new ArrayListCompleteBinaryTree<Entry<K,V>>(); // use an array list
comp = new DefaultComparator<K>(); // use the default comparator
}
/** Creates an empty heap with the given comparator */
public HeapPriorityQueue(Comparator<K> c) {
heap = new ArrayListCompleteBinaryTree<Entry<K,V>>();
comp = c;
}
/** Returns the size of the heap */
public int size() { return heap.size(); }
/** Returns whether the heap is empty */
public boolean isEmpty() { return heap.size() == 0; }
코드 조각 8.14:
HeapPriorityQueue 클래스의
메소드 min, insert와 removeMin과 일부 보조 메소드.
(코드 조각 8.15에서 계속)
/** Returns does not remove an entry with minimum key */
public Entry<K,V> min() throws EmptyPriorityQueueException {
if (isEmpty())
throw new EmptyPriorityQueueException("Priority queue is empty");
return heap.root().element();
}
/** Inserts a key-value pairs and returns the entry created */
public Entry<K,V> insert(K k, V x) throws InvalidKeyException {
checkKey(k); // may throw an InvalidKeyException
Entry<K,V> entry = new MyEntry<K,V>(k,x);
upHeap(heap.add(entry));
return entry;
}
/** Removes and returns an entry with minimum key */
public Entry<K,V> removeMin() throws EmptyPriorityQueueException {
if (isEmpty())
throw new EmptyPriorityQueueException("Priority queue is empty");
Entry<K,V> min = heap.root().element();
if (size() == 1)
heap.remove();
else {
heap.replace(heap.root(), heap.remove());
downHeap(heap.root());
}
return min;
}
/** Determines whether a given key is valid */
protected void checkKey(K key) throws InvalidKeyException {
try {
comp.compare(key,key);
}
catch(Exception e) {
throw new InvalidKeyException("Invalid key");
}
}
코드 조각 8.15: HeapPriorityQueue 클래스의 나머지 보조 메소드.
(코드 조각 8.14부터 계속)
/** Performs up-heap bubbling */
protected void upHeap(Position<Entry<K,V>> v) {
Position<Entry<K,V>> u;
while (!heap.isRoot(v)) {
u = heap.parent(v);
if (comp.compare(u.element().getKey(),v.element().getKey()) <= 0) break;
swap(u, v);
v = u;
}
}
/** Performs down-heap bubbling */
protected void downHeap(Position<Entry<K,V>> r) {
while (!heap.isInternal(r)) {
Position<Entry<K,V>> s; // the position of the smaller child
if (!heap.hasRight(r))
s = heap.left(r);
else if (comp.compare(heap.left(r).element().getKey(),
heap.right(r).element().getKey()) <= 0)
s = heap.left(r);
else
s = heap.right(r);
if (comp.compare(s.element().getKey(),r.element().getKey()) < 0) {
swap(u, v);
r = s;
}
else
break;
}
}
/** Swap the entries of the two given positions */
protected void swap(Position<Entry<K,V>> x, Position<Entry<K,V>> y) {
Entry<K,V> temp = x.element();
heap.replace(x, y.element());
heap.replace(y, temp);
}
/** Text visualization for debugging purposes */
public String toString() {
return heap.toString();
}
8.3.5 힙 정렬
앞에서 살펴본 바와 같이 힙으로 우선순위 큐를 구현하는 것은
우선순위 큐 ADT의 모든 메소드가 로그 시간 이상으로 실행된다는 장점이 있다.
따라서 이러한 실현은 모든 우선순위 큐 메소드에 대해
빠른 실행 시간이 요구되는 애플리케이션에 적합하다.
따라서 8.1.4절의 PriorityQueueSort 정렬 방식을 다시 고려해 보겠다.
PriorityQueueSort 정렬 방식은
우선순위 큐 P를 사용하여 n개의 원소로 시퀀스 S를 정렬한다.
단계 1: i번째 insert 연산(1 ≤ i ≤ n)은 O(1 + log i) 시간에 실행된다.
연산 수행 후 힙에 i개의 엔트리가 있기 때문이다.
단계 2: j번째 removeMin 연산(1 ≤ j ≤ n)은 O(1 + log(n - j + 1)) 시간에 실행된다.
연산 수행 시 힙에 n - j + 1개의 엔트리가 있기 때문이다.
따라서 각 단계는 O(n logn) 시간이 걸리므로
우선 순위 큐를 구현하기 위해 힙을 사용할 때
전체 우선 순위 큐 정렬 알고리즘이 O(n logn) 시간에 실행된다.
이 정렬 알고리즘은 힙 정렬(heap-sort)로 더 잘 알려져 있으며
그 성능은 다음 명제로 요약된다.
제안 8.6: 힙 정렬 알고리즘은
두 개의 S 요소를 O(1) 시간에 비교할 수 있다고 가정하고
n개의 요소를 O(n logn) 시간에 정렬한다.
힙 정렬의 O(n logn) 실행 시간이
선택 정렬 및 삽입 정렬의 O(n^2) 실행 시간보다
훨씬 낫다는 것을 강조한다(섹션 8.2.3).
힙 정렬 제자리 구현
정렬할 수 있는 수열 S를 배열로 구현하면,
수열 S 자체의 일부를 사용하여 힙 정렬 속도를 높이고
공간 요구량을 일정한 요인으로 줄여
외부 힙 자료 구조를 사용하지 않도록 할 수 있다.
알고리즘을 다음과 같이 수정하면 이를 수행할 수 있다:
1. 키가 가장 큰 엔트리가 맨 위에 있는 힙에 해당하는 역 comparator을 사용한다.
알고리즘을 실행하는 동안
언제든지 S의 왼쪽 부분, 특정 인덱스 i-1을 사용하여 힙의 엔트리를 저장하고
S의 오른쪽 부분, 인덱스 i부터 n-1까지 시퀀스의 요소를 저장한다.
따라서 S의 첫 번째 i 요소(인덱스 0,...,i-1에서)는
힙의 배열 리스트 표현(1이 아닌 0으로 시작하는 수정된 레벨 번호)을 제공한다.
즉, 인덱스 k의 요소는 인덱스 2k + 1 및 2k + 2에서 "자녀"보다 크거나 같다.
2. 알고리즘의 첫 단계에서는 빈 힙부터 시작하여
힙과 수열 사이의 경계를 왼쪽에서 오른쪽으로 한 번에 한 단계씩 이동한다.
단계 i (i = 1,..., n)에서 인덱스 i - 1에 원소를 추가하여 힙을 확장한다.
3. 알고리즘의 두 번째 단계에서는 빈 시퀀스로 시작하여
힙과 시퀀스 사이의 경계를 오른쪽에서 왼쪽으로 한 번에 한 단계씩 이동한다.
단계 i (i = 1,..., n)에서 힙에서 최대 요소를 제거하고 인덱스 n - i에 저장한다.
우리는 시퀀스 자체 외에 적은 공간만 사용하기 때문에
위의 힙 정렬의 변형은 제자리(in-place)에 있다고 한다.
우리는 요소들을 시퀀스 밖으로 전달했다가 다시 들어가는 대신 단순히 재배치한다.
우리는 그림 8.9에서 제자리에 있는 힙 정렬을 설명한다.
일반적으로 정렬할 대상을 저장하는 수열 외에
적은 양의 메모리만 사용하면
정렬 알고리즘이 제자리에 있다고 말한다.
그림 8.9: 제자리 힙 정렬 단계 1의 첫 번째 세 단계.
시퀀스의 힙 부분은 파란색으로 강조 표시된다.
이 트리는 실제로 제자리 알고리즘에 의해 구성되지는 않지만,
시퀀스 옆에 힙의 이진 트리 뷰를 그린다.
8.3.6 상향식 힙 시공
힙 정렬 알고리즘을 분석한 결과,
n개의 연속적인 삽입 연산을 통해
O(nlogn) 시간에 n개의 항목을 저장하는 힙을 구성한 다음,
이 힙을 사용하여 감소하지 않은 키로 항목을 순서대로 추출할 수 있음을 알 수 있다.
그러나 힙에 저장할 n개의 키-값 쌍이 모두 미리 주어지면
O(n) 시간에 실행되는 다른 상향식(bottom-up) 구성 방법이 있다.
이 절에서는 이 방법을
힙 기반 우선 순위 큐를 구현하는
클래스의 생성자 중 하나로 포함할 수 있음을 고려하여 설명한다.
설명을 쉽게 하기 위해
키의 수 n을 n = 2^(h + 1) - 1 타입의 정수라고 가정하여
이 상향식 힙 구성을 설명한다.
즉, 힙은 모든 레벨이 가득 찬 완전한 이진 트리이므로
힙의 높이는 h = log(n+ 1) - 1이다.
비 재귀적으로 볼 때,
상향식 힙 구성은 다음과 같은 h + 1 = log(n + 1) 단계로 구성된다:
1. 1 단계(그림 8.10a 참조)
각 항목을 하나씩 저장하는 (n + 1)/2개의 기본 더미를 구성한다.
2. 2 단계(그림 8.10b-c 참조)
기본 더미 쌍을 연결하고 새 항목을 추가하여
각각 3개의 항목을 저장하는 (n + 1)/4개의 더미를 구성한다.
새 항목은 루트에 배치되며
힙 순서 속성을 보존하기 위해
하위에 저장된 항목과 교환해야 할 수 있다.
3. 3 단계(그림 8.10d-e 참조)
(n + 1)/8개의 힙을 구성하며,
각각 7개의 엔트리를 저장한다.
(이전 단계에서 구성된)
3-엔트리 힙 쌍을 결합하고 새 엔트리를 추가한다.
새 엔트리는 처음에 루트에 배치되지만
힙 순서 속성을 보존하기 위해
down-heap bubbling과 함께 아래로 이동해야 할 수도 있다.
i. i 단계 (이전 단계에서 구성된)
(2^(i-1) - 1) 엔트리를 저장하는 힙 쌍을 결합하고
새로운 엔트리를 추가하여
각각 2^i - 1 엔트리를 저장하는 (n+1)/2^i 힙을 형성한다.
새로운 엔트리는 처음에 루트에 배치되지만
힙 순서 속성을 유지하기 위해
down-heap bubbling과 함께 아래로 이동해야 할 수 있다.
h + 1. 마지막 단계(그림 8.10f -g 참조)
(n - 1)/2개의 엔트리를 저장하는 두 개의 힙을 결합하고
(이전 단계에서 구성된) 새로운 엔트리를 추가하여
n개의 엔트리를 모두 저장하는 최종 힙을 구성한다.
새로운 엔트리는 처음에 루트에 배치되지만
힙 순서 속성을 유지하기 위해
down-heap bubbling과 함께 아래로 이동해야 할 수도 있다.
그림 8.10에서 h = 3에 대한 상향식 힙 구성을 설명한다.
그림 8.10: 15개의 항목으로 구성된 힙의 상향식 구성:
(a) 하단 레벨에 1-엔트리 힙을 구성하는 것으로 시작한다.
(b와 c) 이 힙을 3-엔트리 힙으로 결합한 다음
(d와 e) 7-엔트리 힙을
(f와 g) 최종 힙을 생성할 때까지 결합한다.
다운-엔트리 버블의 경로는 파란색으로 강조 표시된다.
단순화를 위해 전체 항목 대신 각 노드 내의 키만 표시한다.
재귀적 상향식 힙 구성
또한 코드 조각 8.16에서 볼 수 있는 바와 같이
상향식 힙 구성을 재귀적 알고리즘으로 설명할 수 있으며,
이는 힙을 구축하고자 하는 키-값 쌍을 저장하는 리스트를 전달하여 호출한다.
코드 조각 8.16: 재귀적 상향식 힙 구성.
Algorithm BottomUpHeap(S):
Input: A list L storing n = 2 entries
Output: A heap T storing the entries in L.
if S.isEmpty() then
return an empty heap
e ← L.remove(L.First())
Split L into two lists, L1 and L2, each of size (n - 1)/2
T1 ← BottomUpHeap(L1)
T2 ← BottomUpHeap(L2)
Create binary tree T with root r storing e, left subtree T1 and right subtree T2
Perform a down-heap bubbling from the root r of T, if necessary
return T
상향식 힙 구성은 다음 명제에서 알 수 있듯이
초기 빈 힙에 n개의 키를 점진적으로 삽입하는 것보다 점근적으로 빠르다.
제안 8.7: 두 개의 키를 O(1) 시간에 비교할 수 있다고 가정할 때,
n개의 엔트리를 가진 힙의 상향식 구축은 O(n) 시간이 걸린다.
정당성: 그림 8.11에 표시된 "시각적" 접근 방식을 사용하여
상향식 힙 구성을 분석한다.
T를 최종 힙이라 하고,
v를 T의 노드라 하고,
T(v)를 v에 뿌리를 둔 T의 부분 트리라고 한다.
최악의 경우,
v의 자식에 뿌리를 둔 두 개의 재귀적으로 형성된 부분 트리로부터
T(v)를 형성하는 시간은 T(v)의 높이에 비례한다.
최악의 경우는
v에서 아래쪽 가장 노드인 T(v)까지의 경로를
v로부터 통과할 때 발생한다.
이제 노드 v에서 후속 외부 노드로 가는 T의 경로 p(v),
즉 v에서 시작하여 v의 오른쪽 자식으로 갔다가 외부 노드에 도달할 때까지
왼쪽으로 내려가는 경로를 생각해 보겠다.
우리는 경로 p(v)가 노드 v와 연관되어 있다고 말한다.
T(v)를 형성할 때 p(v)가 반드시 다운 힙 버블이 뒤따르는 경로는 아니라는 점에 유의하자.
분명히 p(v)의 크기(노드 수)는 T(v)의 높이에 1을 더한 값이다.
따라서 T(v)를 형성하는 것은
최악의 경우 p(v)의 크기에 비례하는 시간이 소요된다.
따라서 상향식 힙 생성의 총 실행 시간은
T의 노드와 연관된 경로 크기의 합에 비례한다.
루트와 구별되는 T의 각 노드 v는
v 자체와 연관된 경로 p(v)와
v의 부모 u와 연관된 경로 p(u)의 정확히 두 경로에 속함을 관찰한다.
(그림 8.11 참조) 또한 T의 루트 r은 r 자체와 연관된 경로 p(r)에만 속한다.
따라서 T의 내부 노드와 연관된 경로 크기의 합은 2n - 1이다.
힙 T의 상향식 구성은 O(n) 시간이 걸린다고 결론지었다.
그림 8.11: 상향식 힙 구축의 선형 실행 시간을 시각적으로 정당화하며,
여기서 내부 노드들과 연관된 경로들은 서로 다른 색으로 강조 표시되었다.
예를 들어, 루트와 연관된 경로는
키 4, 6, 7, 11을 저장하는 노드들로 구성된다.
또한 루트의 오른쪽 자식과 연관된 경로는
키 6, 20, 23을 저장하는 내부 노드들로 구성된다.
정리하자면, 명제 8.7은 힙 정렬의 첫 번째 단계의 실행 시간을
O(n)으로 줄일 수 있다고 말한다.
안타깝게도 힙 정렬의 두 번째 단계의 실행 시간을
O(nlogn)보다 점근적으로 더 좋게 만들 수는 없다
(즉, 최악의 경우에는 항상 Ω(nlogn)이 된다).
하지만 11장까지는 이 하한을 정당화하지는 않을 것이다.
대신 우선 순위 큐 ADT를 확장하여
추가적인 기능을 갖도록 하는 설계 패턴에 대해 논의하면서
이 장을 마무리하고자 한다.
8.4 적응 가능한 우선순위 큐
8.1.3절에서 제시한 우선순위 큐 ADT의 메소드들은
정렬과 같은 우선순위 큐의 대부분의 기본적인 적용에 충분하다.
그러나 대기 항공사 승객 애플리케이션을 참조하는
아래 시나리오와 같이 추가적인 방법이 유용할 수 있는 상황이 있다.
• 비관적인 태도를 보이는 대기 승객은 기다리다 지쳐서
탑승 시간보다 앞서 출발하기로 결정하여
대기자 명단에서 삭제를 요청할 수 있다.
따라서, 우리는 이 승객과 관련된 항목을
우선 순위 큐에서 제거하고자 한다.
출발 승객이 우선 순위를 가질 가능성이 낮기 때문에
연산 removeMin은 이 목적에 적합하지 않다.
대신에, 우리는 임의의 항목 e를 제거하는
새로운 연산 remove(e)를 원한다.
• 다른 대기 승객이 그녀의 금색 자주 비행기 카드를 찾아 에이전트에게 보여준다.
따라서 그녀의 우선 순위는 그에 따라 수정되어야 한다.
이러한 우선순위 변경을 달성하기 위해
우선순위 큐에서 입력 e의 k키로 대체하는
새로운 연산 replaceKey(e,k)를 수행하고자 한다.
• 마지막으로, 세 번째 대기 승객이
그녀의 이름이 항공권에 잘못 표기된 것을 발견하고 수정을 요청한다.
변경을 수행하려면 승객의 기록을 업데이트해야 한다.
따라서, 우리는 우선순위 큐에서 입력 e의 x 값으로 대체하는
새로운 연산 replaceValue(e,x)를 수행하고자 한다.
8.4.1 적응 가능한 우선순위 큐 ADT의 메소드
위와 같은 시나리오는
메소드 remove, replaceKey 및 replaceValue로
우선순위 큐 ADT를 확장하는 새로운 ADT의 정의에 동기를 부여한다.
즉, 적응 가능한 우선순위 큐(adaptable priarity queue) P는
우선순위 큐 ADT 이외에 다음 메소드를 지원한다:
remove(e): P에서 제거하고 엔트리 e를 반환한다.
replaceKey(e,k): k로 교체하고 P의 입력 e 키를 반환한다.
k가 유효하지 않으면 오류 조건이 발생한다
(즉, k는 다른 키와 비교할 수 없다).
replaceValue(e,x): x로 대체하고 P의 엔트리 e의 값을 반환한다.
예제 8.8:
다음 표는 일련의 연산과 초기 빈 적응 우선 순위 큐 P에 대한 영향을 보여준다.
| 연산 | 출력 | P |
| insert(5,A) | e1 | {(5,A)} |
| insert(3,B) | e2 | {(3,B), (5,A)} |
| insert(7,C) | e3 | {(3,B),(5,A),(7,C)} |
| min() | e2 | {(3,B),(5,A),(7,C)} |
| getKey(e2) | 3 | {(3,B),(5,A),(7,C)} |
| remove(e1) | e1 | {(3,B), (7,C)} |
| replaceKey(e2,9) | 3 | {(7,C),(9,B)} |
| replaceValue(e3,D) | C | {(7,D),(9,B)} |
| remove(e2) | e2 | {(7,D)} |
8.4.2 위치 인식 엔트리
메소드 remove, replaceKey, replaceValue가
적응 가능한 우선순위 큐 P를 구현하기 위해서는
P의 엔트리 위치를 찾기 위한 메커니즘이 필요하다.
즉, 위 메소드 중 하나에 인수로 전달된 P의 엔트리 e가 주어졌을 때,
P를 구현하는 자료 구조(예를 들어, 이중 연결 리스트 또는 힙)에서
위치 저장 e를 찾아야 한다.
이 위치를 엔트리의 위치라고 한다.
주어진 엔트리 e의 위치를 찾는 대신
해당 위치를 저장하는 Position 타입의 인스턴스 변수로 엔트리 개체를 확장한다.
위치를 추적하는 엔트리를 이러한 방식으로 구현한 것을 위치 인식 엔트리(location-aware entry)라고 한다.
아래는 적응 가능한 우선 순위 큐의 정렬된 리스트 및
힙 구현을 위한 위치 인식 엔트리 사용에 대한 요약 설명이다.
연산 수행 시 우선 순위 큐의 엔트리 수를 n으로 나타낸다.
• 정렬된 리스트 구현.
이 구현에서는 엔트리가 삽입된 후,
엔트리가 포함된 리스트의 위치를 참조하도록 엔트리의 위치를 설정한다.
또한, 엔트리가 리스트에서 위치를 변경할 때마다 업데이트한다.
엔트리와 함께 저장된 위치 참조를 따라
O(1) 시간에 엔트리 e의 위치 p를 얻을 수 있기 때문에,
연산 remove(e) 및 replaceValue(e,x)는 O(1) 시간이 걸린다.
대신, 연산 replaceKey(e, k)는 O(n) 시간에 실행되는데,
왜냐하면 엔트리 e의 키 수정은 키의 순서를 보존하기 위해
엔트리를 리스트의 다른 위치로 이동시켜야 할 수 있기 때문이다.
위치 인식 엔트리를 사용하면
표준 우선 순위 큐 연산의 실행 시간이 일정한 비율로 증가한다.
• 힙 구현.
이 구현에서는 엔트리가 삽입된 후
엔트리가 포함된 힙의 노드를 참조하도록
엔트리의 위치를 설정한다.
또한 힙에서 노드가 변경될 때마다
(예를 들어 down-heap 또는 up-heap bubbling의 swap 때문에)
엔트리의 위치를 업데이트한다.
연산 replaceValue(e,x)은
엔트리와 함께 저장된 위치 참조 다음
O(1) 시간에 엔트리 e의 위치 p를 얻을 수 있기 때문에
O(1) 시간이 걸린다.
O(logn)에서 연산 remove(e) 및 replaceKey(e,k)를 대신 실행한다
위치 인식 엔트리를 사용하면
일정한 요소 오버헤드만큼
insert 및 removeMin 연산의 실행 시간이 증가한다.
적응 가능한 우선순위 큐 구현의 성능
위치 인식 항목이 있는 다양한 자료 구조를 통해
구현되는 적응 가능한 우선 순위 큐의 성능은
표 8.4에 요약되어 있다.
표 8.4: n 크기의 적응 가능한 우선순위 큐 메소드의 실행 시간.
정렬되지 않은 리스트, 정렬된 리스트, 힙으로 각각 실현.
공간 요구 사항은 O(n)이다.
| 메소드 | 정렬되지 않은 리스트 | 정렬된 리스트 | 힙 |
| size, isEmpty | O(1) | O(1) | O(1) |
| insert | O(1) | O(n) | O(logn) |
| min | O(n) | O(1) | O(1) |
| removeMin | O(n) | O(1) | O(logn) |
| remove | O(1) | O(1) | O(logn) |
| replaceKey | O(1) | O(n) | O(logn) |
| replaceValue | O(1) | O(1) | O(1) |
8.4.3 적응 우선순위 큐 구현
코드 조각 8.17 및 8.18에서는 정렬된 리스트를 기반으로
적응 가능한 우선 순위 큐의 Java 구현을 보여준다.
이 구현은 코드 조각 8.6에 표시된
클래스 SortedListPriorityQueue를 확장하여 가져온다.
특히 코드 조각 8.18에서는 일반 엔트리를 확장하여
Java에서 위치 인식 엔트리를 구현하는 방법을 보여준다.
코드 조각 8.17:
위치 인식 항목을 저장하는 정렬된 리스트를 통해
적응 가능한 우선 순위 큐를 자바로 구현한다.
클래스 SortedListAdaptablePriorityQueue는
클래스 SortedListPriorityQueue(코드 조각 8.6)를 확장하고
인터페이스 AdaptablePriorityQueue를 구현한다.
(코드 조각 8.18에서 계속됨)
/** Implementation of an adaptable priority queue by means of a sorted list. */
public class SortedListAdaptablePriorityQueue<K,V>
extends SortedListPriorityQueue<K,V>
implements AdaptablePriorityQueue<K,V> {
/** Creates the priority queue with the default comparator */
public SortedListAdaptablePriorityQueue() {
super();
}
/** Creates the priority queue with the given comparator */
public SortedListAdaptablePriorityQueue(Comparator<k> comp) {
super(comp);
}
/** Inserts a key-value pair and returns the entry created */
public Entry<K,V> insert (K k, V v) throws InvalidKeyExceptions {
checkKey(k);
LocationAwareEntry<K,V> entry = new LocationAwareEntry<K,V>(k,v);
insertEntry(entry);
entry.setLocation(actionPos); // position of the new entry
return entry;
}
/** Removes and returns the given entry */
public Entry<K,V> remove(Entry<K,V> entry) {
checkKey(entry);
LocationAwareEntry<K,V> e = (LocationAwareEntry<K,V>) entry;
Postion<Entry<K,V>> p = e.location();
entry.remove(p);
e.setLocation(null);
return e;
}
/** Replaces the key of the given entry */
public K replaceKey(Entry<K,V> entry, K k) {
checkKey(k);
checkKey(entry);
LocationAwareEntry<K,V> e = (LocationAwareEntry<K,V>) remove(entry);
K oldKey = e.setKey(k);
insertEntry(e);
entry.setLocation(actionPos); // position of new entry
return oldKey;
}
코드 조각 8.18:
위치 인식 항목을 저장하는 정렬된 리스트로
구현된 적응 가능한 우선 순위 큐이다.
(코드 조각 8.17에서 계속됨)
중첩 클래스 LocationAwareEntry는 위치 인식 항목을 실현하고
코드 조각 8.6에 표시된
SortedListPriorityQueue의 중첩 클래스 MyEntry를 확장한다.
/** Replaces the value of the given entry */
public K replaceValue(Entry<K,V> entry, V value) {
checkEntry(e);
V oldValue = ((LocationAwareEntry<K,V>) e).setValue(value);
return oldValue;
}
/** Determines whether a given entry is valid */
protected void checkEntry(Entry ent) throws InvalidKeyException {
if(ent == null || !(ent instanceof LocationAwareEntry))
throw new InvalidKeyException("invalid entry");
}
/** Inner class for a location-aware entry */
protected static class LocationAwareEntry<K,V>
extends MyEntry<K,V> implements Entry<K,V> {
/** Position where the entry is stored. */
private Position<Entry<K,V>> loc;
public LocationAwareEntry(K key, V value) {
super(key, value);
}
public LocationAwareEntry(K key, V value, Position<Entry<K,V>> pos) {
super(key, value);
loc = pos;
}
protected Position<Entry<K,V>> location() {
return loc;
}
protected Position<Entry<K,V>> setLocation(Position<Entry<K,V>> pos) {
Position<Entry<K,V>> oldPosition = location();
loc = pos;
return oldPosition;
}
protected K setKey(K key) {
K oldKey = getKey();
k = key;
return oldKey;
}
protected K setValue(V value) {
V oldValue = getValue();
v = value;
return oldValue;
}
}'프로그래밍 공부 > Data Structure' 카테고리의 다른 글
| 9장 맵과 딕셔너리(2) (1) | 2024.01.01 |
|---|---|
| 9장 맵과 딕셔너리(1) (1) | 2023.12.31 |
| 7장 트리(2) (1) | 2023.12.30 |
| 7장 트리(1) (2) | 2023.12.29 |
| 6장 리스트와 반복자 (1) | 2023.12.22 |