[CS] 자료 구조의 분류 - 비선형 자료 구조 #2 (힙, 우선순위 큐)

Janet·2023년 9월 20일
0

CS

목록 보기
16/17
post-thumbnail

비선형 자료 구조 (Non-Linear Data Structures)


  • 비선형 자료 구조: 그래프, 트리, 해시 테이블, 힙, 맵, 셋, 우선순위 큐 등.

▼ 비선형 자료 구조 그래프와 트리에 대한 내용
[CS] 자료 구조의 분류 - 비선형 자료 구조 #1 (그래프, 트리)

1. 힙 (Heap)


  • 힙은 완전 이진 트리 기반의 자료 구조이다.
  • 최소힙과 최대힙 두 가지가 있고, 해당 힙에 따라 특정한 특징을 지킨 트리를 말한다.
  • 최소 힙의 삽입과 삭제 연산은 주로 우선순위 큐(Priority Queue)와 같이 최소값 또는 최대값을 효율적으로 관리해야 하는 경우에 사용된다.
▼ 최소힙과 최대힙

1-1. 최소 힙 (Min Heap)

  • 최소힙에서 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 한다. 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.

1-2. 최대힙 (Max Heap)

  • 루트 노드에 있는 키는 모든 자식에 있는 키 중에 최댓값이어야 한다. 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.

1-3. 동작 방식

📌 삽입

  1. 새로운 노드를 트리의 마지막 노드에 추가한다. 이 새로운 노드를 부모 노드와의 크기를 비교한다.
    • 최대 힙인 경우: 추가한 노드가 부모 노드보다 크면 자리를 바꾼다.
    • 최소 힙인 경우: 추가한 노드가 부모 노드보다 작으면 자리를 바꾼다.
  2. 크기를 비교하여 스왑(swap)하는 작업을 힙의 성질을 만족시킬 때 까지 반복한다.
▼ 최대힙의 삽입

📌 삭제

  1. 루트 노드에서 값을 제거한다.
  2. 마지막 노드를 루트 노드로 옮긴다.
  3. 자식 노드와 대소관계를 비교한다.
    • 최대 힙인 경우: 자식 노드 중 더 큰 노드와 부모 노드의 자리를 바꾼다.
    • 최소 힙인 경우: 자식 노드 중 더 작은 노드와 부모 노드의 자리를 바꾼다.
  4. 크기를 비교하여 스왑(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
profile
😸

0개의 댓글