덱 (Deque : Double Ended Queue)
덱은 특수한 형태의 큐로서 삽입, 삭제가 front와 rear 양 끝에서 가해질 수 있도록 허용한 자료구조다. 허용되는 작업을 이렇게 정의하면 이 구조는 사실상 큐로 작동할 수도 있고, 스택으로 작동할 수도 있다.
주요 함수
- AddLast()
- AddFirst()
- RemoveLast()
- RemoveFirst()
시간 복잡도
- 삽입 : O(1)
- 삭제 : O(1)
- 검색 : O(1), index를 통해 random access가 가능하다.
구현
양 끝에서 삽입 삭제가 일어난다는 점을 감안하면 덱 구조에서는 포인터 두 개를 유지하는 것이 유리하다. 연결 리스트라면 헤드 포인터와 테일 포인터 두 개를 가져야 함을 의미한다. 또, 테일이 가리키는 마지막 노드에서 삭제가 일어나면, 테일은 바로 그 이전 노드를 가리켜야 한다는 점을 감안하면 그 구조는 이중연결 리스트가 가장 적당하다.
(연결 리스트 덱 구현)
https://leejinseop.tistory.com/39
[자료구조] 덱(Deque, Double-ended Queue) 설명 및 구현
1. 덱(Deque, Double-ended Queue) 덱은 큐의 양쪽 끝에서 데이터의 삽입과 삭제가 모두 가능하게 만든 큐로서, 스택과 큐의 성질을 모두 가지고 있는 자료구조입니다. 2. 덱의 연산 덱은 양쪽 끝에서 데
leejinseop.tistory.com
배열로 구현할 때도 마찬가지로 프런트와 리어 인덱스 두 개가 필요하다. 고정된 한 쪽 끝에서 add나 remove가 이루어지면 이동(shift)에 따른 시간이 소요되는데, 앞 쪽에서 데이터 삽입이 이루어질 경우 오른쪽의 모든 데이터가 오른쪽으로 이동해야 하기 때문이다. 이러한 시간적 부담을 줄이기 위해서는 원형 배열을 사용하면 된다. 물론 이 경우 프런트와 리어가 앞뒤로 자유자재로 움직일 수 있어야 한다.
우선순위 큐 (Priority Queue)
우선순위 큐는 큐와 스택 개념을 확장하여 일반화한 것이다. 먼저 들어온 레코드를 먼저 처리하는 것이 큐고, 나중에 들어온 아이템을 먼저 처리하는 것이 스택이다. 이처럼 시간을 기준으로 우선순위를 결정하는 대신 아이템 자체의 우선순위에 따라 먼저 처리할 것을 결정한느 것이 우선순위 큐다. 큐나 스택의 우선순위는 삽입 위치에 의해 자동적으로 표시되지만 우선순위 큐는 그렇지 않으므로 태그(Tag, 꼬리표)를 필요로 한다. 우선순위 값(Priority Value)에 해당하는 이 태그를 우선순위 큐의 키(Key) 값으로 정의한다.
추상 자료형으로서의 우선순위 큐는 다음과 같이 몇 가지 작업으로 정의할 수 있다.
- Create : 새로운 우선순위 큐를 만들기
- Destroy : 사용되던 우선순위 큐를 파기하기
- Add : 현재 우선순위 큐에 새로운 레코드를 삽입하기
- Remove : 가장 우선순위가 높은 레코드를 삭제하기
- IsEmpty : 현재 우선순위 큐가 비어있는지 확인하기
우선순위 큐는 배열, 연결 리스트, 트리로 구현할 수 있다. 그러나 거의 대부분의 경우에 힙에 의해 구현되므로 이에 대해서만 알아보도록 하겠다. 힙은 기술 면접에도 자주 나오는 주제이므로 잘 알아두면 좋다.
힙(Heap)에 의한 우선순위 큐 구현
키 값이 클수록 우선순위가 높다고 가정할 때(Max heap), 힙(Heap)의 정의는 다음 두 가지 조건을 모두 만족해야 한다.
- 항상 완전 이진트리의 모습을 지닌다.
- A. 빈 트리이거나, B. 루트의 키가 왼쪽 자식, 오른쪽 자식의 키보다 크거나 같다. 왼쪽 자식과 오른쪽 자식 사이에는 어느 쪽 키가 크든지 상관 없다. 단 왼쪽 자식, 오른쪽 자식을 루트로 하는 하위트리는 힙이어야 한다.
- Max Heap : 키 값이 큰 레코드가 우선순위가 높은 것으로 간주되어 루트노드의 키가 가장 크다.
- Min Heap : 키 값이 작을수록 우선순위가 높다고 간주되어 가장 작은 키를 가진 레코드가 루트노드에 존재한다.
이진 탐색트리가 약한 의미로 정렬되어 있다면 힙은 더 약한 의미로 정렬되어 있다고 할 수 있다. 이진 탐색트리의 경우 루트노드를 중심으로 작은 것은 왼쪽 하위트리, 큰 것은 오른쪽 하위트리로 파티션 되어 있고, 또 트리에 중위순회를 가하면 완전히 정렬된 결과를 얻을 수도 있다. 그러나 힙은 큰 것이 상위 노드에, 작은 것이 하위 노드에 있다는 정도의 정렬 개념으로서, 아무 미약한 정렬이라 할 수 있다. 그러나 힙에서 요구되는 작업을 고려하면 이 정도의 정렬만으로도 충분하다. 힙을 구성하는 주 목적인 삭제에 있어서는 가장 우선순위가 높은 것만 찾을 수 있으면 되기 때문이다. 따라서 나머지 데이터가 굳이 정렬될 필요는 없다.
힙의 가장 큰 특징은 완전 이진트리 모습이라는 데 있다 (마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있는 트리). 완전 이진트리는 배열로 표시하는 것이 가장 효율적이므로 힙은 항상 배열로 구현된다. 완전 이진트리를 배열로 나타내면 루트부터 시작해서 위에서 아래로, 왼쪽에서 오른쪽으로 진행하며 배열에 집어넣으면 된다. 이렇게 되면 트리의 루트 노드는 배열 인덱스 0번에 위치하게 되고, 다음과 같은 부모 자식 관계 간의 인덱스 연산이 나오게 된다.
인덱스 K에 있는 노드의 왼쪽 자식 : 2K + 1
인덱스 K에 있는 노드의 오른쪽 자식 : 2K + 2
인덱스 K에 있는 노드의 부모 노드 : (K - 1) / 2
힙의 삭제
힙에 삭제를 가하면 우선순위가 가장 큰 노드, 즉 루트노드가 삭제되어야 한다. 루트노드를 삭제한 자리에는 배열의 제일 마지막 요소가 오게 되는데, 이 노드가 알맞은 자리를 찾아 힙의 모습을 되찾기 위해서는 왼쪽 자식과 오른쪽 자식 모두를 비교해서 가장 큰 것과 루트를 스와핑(Swap, Exchange)해야 한다. (Max Heap이라 가정) 이처럼 힙 모습을 되찾으려면 루트로부터 시작해서 제자리를 찾기까지 굴러 떨어져야 한다 (Down Heap / Demotion). 물론 내려오는 도중 자신이 자식들보다 크다면 더 이상 내려가지 말아야 한다. 이렇게 함으로써 완전한 힙 모습이 복원된다. (Heap Rebuilding) 물론 힙은 배열로 구현되므로 실제로 이러한 모든 작업은 배열 내부에서 이루어진다.
루트 노드 제거. 루트 노드의 자리에는 우선순위 큐 배열의 가장 마지막에 있는 요소를 올린다.
Max Heap 임에도 부모 노드의 값이 자식 노드의 값보다 작다. 힙의 규칙에 어긋나므로 제대로 된 힙의 모습을 갖출 때까지 3의 값을 갖고 있는 노드를 아래로 끌어내린다.
Max Heap 이므로 자식 노드 중 더 큰 값을 갖고 있는 자식 노드와 스와핑 한다. 현재의 노드가 자식 노드들보다 더 클 때까지 스와핑을 반복한다. 자식 노드인 2보다 현재 노드인 3이 더 크므로 스와핑을 멈춘다.
힙의 삽입
힙의 삽입은 삽입될 레코드를 일단 배열의 마지막에 이어 붙임으로써 시작된다. 이 레코드는 부모 노드의 키와 비교되며 만약 자신이 더 크다면 부모와 스와핑 된다. (Max Heap) 그렇게 부모의 키가 자신보다 클 때까지 스와핑이 일어나게 되며 이를 Up Heap / Promotion이라고 한다.
새로운 노드가 추가되었다. 배열의 마지막에 붙이고 보니 부모인 3보다 값이 크다.
부모와 스와핑 한다. 부모인 25가 현재 노드인 27보다 작으므로 다시 스와핑 한다. 이를 루트 노드에 도달하거나 부모 노드가 더 클 때까지 반복한다.
부모 노드인 30이 현재 노드인 27보다 크므로 멈춘다.
효율
힙의 삽입과 삭제의 시간 복잡도는 O(log N)이 보장된다. 최악의 경우 루트부터 리프까지 이동하게 되므로 트리 높이에 해당하는 log N의 노드를 모두 지나야 하기 때문이다.
힙이 이진 탐색트리보다 유리하다는 것은 트리의 높이 때문이다. 이진 탐색트리는 트리의 모양에 따라 최악의 경우 연결 리스트와 유사한 모습이 되며 O(N)의 효율을 보이게 된다. 반면 힙은 완전 이진트리의 모습을 지니므로 반드시 균형트리(Balanced Tree) 상태를 유지한다. 균형트리의 높이는 항상 log(N)에 가깝다. 따라서 힙은 트리와 달리 최악의 경우에도 삽입, 삭제에 걸리는 시간 O(log N)이 완전히 보장된다는(Guaranteed) 점이 최대 장점이다. 단 힙은 배열로 표시되므로 최대 레코드 수를 미리 결정해야 하는 부담을 안고 있다. 검색은 항상 루트 노드를 리턴하게 되므로 O(1)이 된다.
| add (삽입) | peak (탐색) | remove (삭제) | |
| 이진 탐색트리 (BST) | O(n) | O(n) | O(n) |
| 힙 (Heap) | O(log n) | O(log n) | O(1) |
구현
public class MaxIntHeap {
private int capacity = 10; // 총 용량
private int size = 0; // 현재 크기
int items[] = new int[capacity]; // 힙 배열
private int getLeftChildIndex(int parentIndex) { return 2 * parentIndex + 1; } // 왼쪽 자식 인덱스 반환
private int getRightChildIndex(int parentIndex) { return 2 * parentIndex + 2; } // 오른쪽 자식 인덱스 반환
private int getParentIndex(int childIndex) { return (childIndex - 1) / 2; } // 부모 인덱스 반환
private boolean hasLeftChild(int index) { return getLeftChildIndex(index) < size; } // 왼쪽 자식 존재 여부 반환
private boolean hasRightChild(int index) { return getRightChildIndex(index) < size; } // 오른쪽 자식 존재 여부 반환
private boolean hasParent(int index) { return getParentIndex(index) < size; } // 부모 여부 반환
private int leftChild(int index) { return items[getLeftChildIndex(index)]; } // 왼쪽 자식 값 반환
private int rightChild(int index) { return items[getRightChildIndex(index)]; } // 오른쪽 자식 값 반환
private int parent(int index) { return items[getParentIndex(index)]; } // 부모 값 반환
private void swap(int index1, int index2) { // 스와핑 함수
int tmp = items[index1];
items[index1] = items[index2];
items[index2] = tmp;
}
private void ensureExtraCapacity() { // 배열이 꽉 찼는지 검사, 찼을 경우 용량 2배로 증가
if(size == capacity) {
items = Arrays.copyOf(items, capacity * 2);
capacity *= 2;
}
}
/* 루트노드 반환 */
public int peek() {
if(size == 0) throw new IllegalStateException(); // 빈 배열일 경우 오류
else return items[0]; // 빈 배열이 아니라면 루트 노드 값 반환
}
/* 힙의 삭제 */
public int poll() {
if(size == 0) throw new IllegalStateException(); // 빈 배열일 경우 오류
int item = items[0]; // 루트 노드 값 저장
items[0] = items[--size]; // 루트 노드 자리에 배열의 마지막 값 이동, 총 사이즈 줄이기
heapifyDown(); // Demotion. 알맞은 자리 찾을 때까지 내려가기
return item;
}
/* 힙의 삽입 */
public void add(int item) {
ensureExtraCapacity(); // 꽉 찬 배열 아닌지 검사, 맞다면 용량 증가
items[size++] = item; // 배열 마지막 자리에 삽입, 전체 사이즈 하나 증가
heapifyUP(); // Promotion. 알맞은 자리 찾을 때까지 올라가기
}
/* Down Heap / Demotion */
private void heapifyDown() {
int index = 0; // 루트 위치부터 내려가기 시작
while(hasLeftChild(index)) { // 비교할 자식이 있다면 계속 반복 (왼쪽 있다면 오른쪽 당연히 있으므로 왼쪽만 검사해도 됨)
int biggerChildIndex = getLeftChildIndex(index); // 더 큰 자식 저장 (우선 왼쪽 자식)
if(hasRightChild(index) && rightChild(index) > leftChild(index)) // 만약 오른쪽에 자식이 있고 오른쪽 자식이 왼쪽 자식보다 더 크다면
biggerChildIndex = getRightChildIndex(index); // 더 큰 자식에 오른쪽 자식을 저장
if(items[index] > items[biggerChildIndex]) { // 만약 더 큰 자식이 나보다 작다면
break; // 올바른 힙. Demotion 종료
}
else { // 아니라면
swap(index, biggerChildIndex); // 더 큰 자식과 나 스와핑
index = biggerChildIndex; // 현재 인덱스 업데이트 (더 큰 자식 인덱스로 내려감)
}
}
}
/* Up Heap / Promotion */
private void heapifyUP() {
int index = size - 1; // 현재 인덱스 (배열의 가장 마지막)
while(hasParent(index) && parent(index) < items[index]) { // 부모가 있고, 내가 부모보다 크다면 (잘못된 힙) 계속 반복
swap(index, getParentIndex(index)); // 부모와 나의 위치 스와핑
index = getParentIndex(index); // 현재 인덱스 부모 인덱스로 업데이트
}
}
}
힙 정렬 (Heap Sort)
힙 정렬은 힙 구조를 정렬 목적으로 사용한 것이다. 힙 구조에서 remove를 가하면 키 값이 제일 큰 레코드가 빠져 나오기 때문에 빈 트리가 될 때까지 계속적으로 remove를 가하여 빠져나온 레코드 순으로 적어나가면 그것이 바로 정렬 결과가 된다.
힙 정렬을 위해 가장 먼저 해야 할 것은 힙 구성(Heap Building)이다. 힙을 구성하는 방법은 두 가지로, 하향식(탑 다운, Top Down)과 상향식(바텀 업, Bottom Up)이 있다.
하향식 힙 구성이란 키를 지닌 레코드들이 있을 때 힙을 만들기 위해 반복적으로 삽입을 가하며 Up Heap / Promotion 동작을 반복하여 바로 바로 힙 구조를 복원하는 방식이다. 힙 구성 단계에서 노드 하나가 삽입될 때마다 log N의 경로를 걸쳐 위로 올라가므로 전체 데이터 N개가 삽입된다면 NlogN의 효율이 된다. 정렬 단계에서 삭제를 가할 때도 하나씩 빠져나가며 조정을 위해 루트로 복사된 레코드가 log N 경로를 타고 내려와야 하므로 NlogN에 해당된다. 따라서 하향식 힙 구성에 의한 정렬의 효율은 O(NlogN) + O(NlogN) = O(NlogN)이 된다고 할 수 있다.
상향식 힙 구성 방식은 들어오는 키 값 순서대로 일단 트리를 구성한 후 힙 구조가 되도록 재조정하는 방식이다. 일단 트리를 구성한 후에 가장 아래쪽의 리프 노드를 오른쪽에서 왼쪽으로 검사한다. 검사 시에는 해당 노드와 그 아래쪽 노드의 키만 비교한다. 이때 주의해야 할 점은 스왑되어 올라간 노드는 자신의 위는 쳐다볼 필요가 없다는 점이다. 항상 현재 것과 아래 것만 비교하기로 했기 때문이다. 다만 떨어질 때는 계속적으로 아래 것과 비교해야 한다. 이 또한 O(NlogN)의 효율을 가진다.
상향식 힙 구성 결과와 하향식 힙 구성 결과는 동일하지 않을 수도 있다. 그러나 둘 다 힙의 모습을 갖추고 있다. 여기서 하향식이라는 말은 새로운 레코드가 점차 아래쪽에 삽입된다는 의미이다. 상향식 또한 아래에서 위로 올라가며 검사 대상 레코드 선택된다는 뜻이다.
쾌속정렬은 일반적으로 O(NlogN)이지만 이를 보장하지는 못한다. 합병 정렬이 O(NlogN)을 보장하지만 추가의 메모리가 필요하다. 힙 정렬은 O(NlogN)을 보장하면서 추가의 메모리도 불필요하다. 이런 의미에서 보면 힙 정렬이 최적이지만 내부 루프 처리시간이 쾌속 정렬보다 길기 때문에 일반적으로는 쾌속 정렬보다 느리다.
[참고 자료]
C/C++로 배우는 자료구조론
