비선형 자료 구조 (Non-Linear Data Structures)
- 비선형 자료 구조: 그래프, 트리, 해시 테이블, 힙, 맵, 셋, 우선순위 큐 등.
▼ 비선형 자료 구조 그래프와 트리에 대한 내용
[CS] 자료 구조의 분류 - 비선형 자료 구조 #1 (그래프, 트리)
1. 힙 (Heap)
- 힙은 완전 이진 트리 기반의 자료 구조이다.
- 최소힙과 최대힙 두 가지가 있고, 해당 힙에 따라 특정한 특징을 지킨 트리를 말한다.
- 최소 힙의 삽입과 삭제 연산은 주로 우선순위 큐(Priority Queue)와 같이 최소값 또는 최대값을 효율적으로 관리해야 하는 경우에 사용된다.
1-1. 최소 힙 (Min Heap)
- 최소힙에서 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 한다. 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.
1-2. 최대힙 (Max Heap)
- 루트 노드에 있는 키는 모든 자식에 있는 키 중에 최댓값이어야 한다. 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.
1-3. 동작 방식
📌 삽입
- 새로운 노드를 트리의 마지막 노드에 추가한다. 이 새로운 노드를 부모 노드와의 크기를 비교한다.
- 최대 힙인 경우: 추가한 노드가 부모 노드보다 크면 자리를 바꾼다.
- 최소 힙인 경우: 추가한 노드가 부모 노드보다 작으면 자리를 바꾼다.
- 크기를 비교하여 스왑(swap)하는 작업을 힙의 성질을 만족시킬 때 까지 반복한다.
📌 삭제
- 루트 노드에서 값을 제거한다.
- 마지막 노드를 루트 노드로 옮긴다.
- 자식 노드와 대소관계를 비교한다.
- 최대 힙인 경우: 자식 노드 중 더 큰 노드와 부모 노드의 자리를 바꾼다.
- 최소 힙인 경우: 자식 노드 중 더 작은 노드와 부모 노드의 자리를 바꾼다.
- 크기를 비교하여 스왑(swap)하는 작업을 힙의 성질을 만족시킬 때 까지 반복한다.
1-4. 힙의 구현
▼ 배열을 이용하여 구현한 힙
- 왼쪽 자식노드 index = (부모 노드 index) * 2
- 오른쪽 자식노드 index = (부모 노드 index) * 2 + 1
- 부모 노드 index = (자식노드 index) / 2
2. 우선순위 큐 (Priority Queue)
- 일반적인 큐(Queue)는 먼저 집어넣은 데이터가 먼저 나오는 선입선출(FIFO, First In First Out)의 구조로 저장하는 선형 자료 구조이다.
- 하지만 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말한다.
- 우선순위 큐는 우선순위 대기열이라고도 하며, 대기열에서 각 요소에 우선순위를 할당하고, 우선순위가 가장 높은 요소를 먼저 반환하도록 설계된 자료 구조이다.
- 우선순위 큐는 힙(heap)을 기반으로 구현된다.
2-1. 동작 방식
-
enqueue(): 요소는 우선순위 큐에 삽입될 때 해당 요소의 우선순위에 따라 정확한 위치에 삽입된다. 일반적으로 우선순위가 높은 요소는 큐의 앞쪽에 위치하게 된다.
-
dequeue(): 우선순위 큐에서는 주로 우선순위가 가장 높은 요소를 삭제하고 반환하는 연산이 수행된다. 이 연산을 "최소값 추출(Min Extract)" 또는 "최대값 추출(Max Extract)"이라고도 한다.
-
peek(): Queue에서 최대 우선순위 요소를 반환한다. 최대 우선순위 값은 항상 루트에 있으므로 루트 값을 반환한다.
2-2. 시간 복잡도
| 구현 방법 | 삽입 | 삭제 |
|---|---|---|
| 배열 | O(1) | O(N) |
| 연결 리스트 | O(1) | O(N) |
| 정렬된 배열 | O(N) | O(1) |
| 정렬된 연결 리스트 | O(N) | O(1) |
| 힙 | O(logN) | O(logN) |
2-3. 우선순위 큐의 구현 (JavaScript)
- 배열(Array)을 기반으로 간단한 최소 힙(Min Heap) 구현. 최소 힙은 우선순위 큐를 구현하는 데 사용되며, 가장 작은 값을 가진 요소가 항상 루트 노드에 위치하는 특징을 가지고 있다.
class PriorityQueue {
constructor() {
this.heap = [];
}
// 요소 삽입
enqueue(value, priority) {
const element = { value, priority };
this.heap.push(element);
this.bubbleUp();
}
// 가장 우선순위가 높은 요소 추출
dequeue() {
if (this.isEmpty()) return null;
if (this.heap.length === 1) return this.heap.pop();
const min = this.heap[0];
this.heap[0] = this.heap.pop();
this.sinkDown();
return min;
}
// 우선순위 큐가 비어 있는지 확인
isEmpty() {
return this.heap.length === 0;
}
// 요소를 힙 상단으로 이동시키는 메서드 (삽입 시)
bubbleUp() {
let currentIndex = this.heap.length - 1;
const currentElement = this.heap[currentIndex];
while (currentIndex > 0) {
const parentIndex = Math.floor((currentIndex - 1) / 2);
const parentElement = this.heap[parentIndex];
if (currentElement.priority >= parentElement.priority) break;
// 부모와 자식 요소 교환
this.heap[currentIndex] = parentElement;
this.heap[parentIndex] = currentElement;
currentIndex = parentIndex;
}
}
// 요소를 힙 하단으로 이동시키는 메서드 (추출 시)
sinkDown() {
let currentIndex = 0;
const length = this.heap.length;
const currentElement = this.heap[0];
while (true) {
const leftChildIndex = 2 * currentIndex + 1;
const rightChildIndex = 2 * currentIndex + 2;
let swapIndex = null;
if (leftChildIndex < length) {
const leftChild = this.heap[leftChildIndex];
if (leftChild.priority < currentElement.priority) {
swapIndex = leftChildIndex;
}
}
if (rightChildIndex < length) {
const rightChild = this.heap[rightChildIndex];
if (
(swapIndex === null && rightChild.priority < currentElement.priority) ||
(swapIndex !== null && rightChild.priority < this.heap[swapIndex].priority)
) {
swapIndex = rightChildIndex;
}
}
if (swapIndex === null) break;
// 부모와 자식 요소 교환
this.heap[currentIndex] = this.heap[swapIndex];
this.heap[swapIndex] = currentElement;
currentIndex = swapIndex;
}
}
}
// 우선순위 큐 사용 예시
const priorityQueue = new PriorityQueue();
priorityQueue.enqueue('Task 1', 3);
priorityQueue.enqueue('Task 2', 1);
priorityQueue.enqueue('Task 3', 2);
console.log(priorityQueue.dequeue()); // { value: 'Task 2', priority: 1 }
console.log(priorityQueue.dequeue()); // { value: 'Task 3', priority: 2 }
console.log(priorityQueue.dequeue()); // { value: 'Task 1', priority: 3 }
console.log(priorityQueue.isEmpty()); // true
