이전 포스팅에서는 큐의 기본 개념과 가장 기본적인 형태인 선형 큐에 대해 다루었습니다. 오늘은 선형 큐외에 우선순위 큐에 대해 공부한 내용을 공유하려고 합니다.

선형큐는 가장 처음으로 들어간 요소가 가장 처음으로 나오는 자료구조형니다(FIFO). 하지만, 특정 요소가 우선순위에 따라서 먼저 처리되어야 하는 상황이 있을 때는 어떻게 할까요? 이러한 필요에의해서 우선순위 큐가 만들어졌습니다. 이번 글에서는 우선순위 큐의 개념과 JS로 구현하는 방법 을 공부해보겠습니다.

또한, 리액트 18부터 도입된 Concurrent Mode에서 우선순위 큐가 렌더링 최적화에 어떻게 활용되는지, 실제 React코드를 통해 알아보겠습니다.

우선순위 큐

우선순위 큐는 말그대로 "우선 순위가 높은"요소를 먼저 제거 할 수 있도록 하는 큐의 확장형 자료 구조 형입니다. 이를 위해 각 요소에는 우선순위를 나타내는 값이 필요합니다. 동일한 우선순위를 가진 요소들 간에는 일반적인 큐의 특성에 따라, 먼저 삽입된 요소가 먼저 처리됩니다.

우선 순위 큐는 배열, 링크드 리스트, 힙 등 다양한 방법으로 구현할 수 있으며, 구현 방식에 따라 효율성과 특성이 달라집니다.

Array를 이용한 우선순위 큐

class PriorityArrayQueue {
  constructor() {
    this.queue = [];
  }

  get get_queue() {
    return this.queue;
  }

  enQueue(value, priority) {
    const element = { value, priority };
    let added = false;

    for (let i = 0; i < this.queue.length; i++) {
      if (this.queue[i].priority > priority) {
        this.queue.splice(i, 0, element);
        added = true;
        break;
      }
    }

    if (!added) {
      this.queue.push(element);
    }
  }

  deQueue() {
    this.queue.shift();
  }
}

PriorityArrayQueue는 요소를 삽입할 때마다 요소를 우선순위에 맞는 위치에 배치하는 방식을 사용합니다. 이때 Array의 정렬된 위치에 요소를 삽입해야 하기 때문에, 삽입 연산은 O(n)의 시간 복잡도를 가집니다.
또한, 요소 제거는 가장 앞에 있는 요소를 제거하는데, 배열의 첫 요소를 제거하면 나머지 요소들을 한칸씩 앞으로 이동시켜야 하므로 이역시 O(n)이라는 시간 복잡도를 가집니다.

시간 복잡도 요약

• 삽입 : for문을 통해 적절한 위치를 찾아 splice로 삽입하기 때문에 O(n)
• 삭제 : 삭제 또한 splice로 첫번째 요소를 제거한 후, 모든 요소를 앞으로 한칸씩 밀어야 하기 때문에 O(n)이라는 시간복잡도를 갖습니다.
• 요소 찾기 : 특정 요소를 찾는 연산 또한 배열 전체를 순회 하며 찾아야 하기 때문에 O(n) 시간복잡도를 갖습니다.

이와 같은 배열 기반 우선순위 큐는 데이터 크기가 작을때는 구현하기 좋지만, 요소 삽입과 삭제 시 이동이 발생해 큰 데이터를 처리할 때는 성능이 떨어질 수 있습니다.

LinkedList를 이용한 우선순위 큐

Array기반 우선순위 큐의 단점을 극복하기 위해 LinkedList를 사용하여 구현할 수도 있습니다. 다음은 LinkedList로 구현한 우선순위 큐의 예제 코드입니다.

class NewNode {
  constructor(value, priority) {
    this.value = value;
    this.priority = priority;
    this.next = null;
  }
}

class PriorityLinkedListQueue {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  printQueue() {
    let current = this.head;
    while (current) {
      current = current.next;
    }
  }

  enQueue(value, priority) {
    const newNode = new NewNode(value, priority);
    // 리스트가 비어있을 경우
    if (!this.head && !this.tail) {
      this.head = newNode;
      this.tail = newNode;
      return;
    }
    // 새 노드가 head보다 우선순위가 높을 경우
    if (this.head.priority < newNode.priority) {
      newNode.next = this.head;
      this.head = newNode;
      return;
    }

    let current = this.head;
    let previous = null;

    while (current) {
      if (current.priority <= newNode.priority) {
        previous = current;
        current = current.next;
      }
    }

    if (!current) {
      this.tail.next = newNode;
      this.tail = newNode;
    } else {
      previous.next = newNode;
      newNode.next = current;
    }
  }

  deQueue() {
    this.head = this.head.next;

    if (!this.head.next) {
      this.tail = null;
    }
  }
}

시간 복잡도

• 삽입 : 새 요소를 추가할 때는 현재 요소들을 순회하며 적절한 위치를 찾아 삽입합니다. 이 과정에서 O(n)의 시간이 소요됩니다.

• 삭제 : 가장 첫 요소(우선순위가 가장 높은 요소)를 제거하기 때문에 O(1)의 시간이 소요됩니다.

• 장점 : 요소를 제거할 때는 head를 삭제하면 되기 때문에 빠르게 처리할 수 있습니다.

• 단점 : 배열과 달리 인덱스를 통해서 접근할 수 없기 때문에 특정 요소에 접근해야 하는경우 효율적이지 않습니다.

LinkedList를 사용한 우선순위 큐는 삽입과 삭제가 빈번한 상황에서는 효율적이지만, 특정 인덱스에 접근하거나 요소를 빠르게 찾는 경우에는 적합하지 않습니다.

힙을 이용한 우선순위 큐

Heap은 특정 조건을 만족하는 이진 트리 기반의 자료구조입니다. 주로 최소힙과 최대힙 으로 나뉘는데요. 루트의 노드가 최소값이냐 최대값이냐에 따라 구분됩니다.

힙은 배열을 이용해서 구현하는 경우가 많습니다. 아래는 자바스크립트로 구현한 최소 힙의 예제 코드입니다.

class MinHeap {
  constructor() {
    this.heap = [];
  }

  insert(value) {
    this.heap.push(value);
    this.bubbleUp();
  }
  remove() {
    if (this.heap.length === 0) {
      return null;
    }

    if (this.heap.length === 1) {
      return this.heap.pop();
    }
    this.heap[0] = this.heap.pop();

    this.bubbleDown();
  }

  parentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  leftChildIndex(index) {
    return index * 2 + 1;
  }
  rightChildIndex(index) {
    return index * 2 + 2;
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      // 부모랑 비교 한다.
      const parentIndex = this.parentIndex(index);
      const parent = this.heap[parentIndex];
      const current = this.heap[index];

      if (parent <= current) {
        break;
      }
      this.heap[parentIndex] = current;
      this.heap[index] = parent;
      index = parentIndex;
    }
  }

  bubbleDown() {
    let index = 0;
    const length = this.heap.length;
    const element = this.heap[0];

    while (true) {
      const leftChildIndex = this.leftChildIndex(index);
      const rightChildIndex = this.rightChildIndex(index);

      let swap = null;
      let leftChild, rightChild;

      if (leftChildIndex < length) {
        leftChild = this.heap[leftChildIndex];
        if (leftChild < element) {
          swap = leftChildIndex;
        }
      }

      if (rightChildIndex < length) {
        rightChild = this.heap[rightChildIndex];
        if (
          (!swap && rightChild < element) ||
          (swap && rightChild < leftChild)
        ) {
          swap = rightChildIndex;
        }
      }

      if (!swap) {
        break;
      }
      this.heap[index] = this.heap[swap];
      this.heap[swap] = element;
      index = swap;
    }
  }

  display() {
    console.log(this.heap);
  }
}

간단한 코드 설명을 하자면

• BubbleUp : 요소를 추가할 때, 새로운 요소가 부모 노드보다 작으면 부모와 그 위치를 교환하며 위로 이동시킵니다.
• BubbleDown: 요소를 제거한 후, 힙의 규칙을 유지하기 위해 상위 노드와 하위 노드를 비교하며 자리를 교환해 트리 구조를 재조정합니다.

힙은 요소를 추가할때 트리의 가장 하위에 요소를 추가한 후, 힙의 규칙에 따라 필요한 경우 부모와 위치를 교환하기 때문에 O(log n)의 시간 복잡도로 조금 더 효율적인 삽입이 가능합니다. 이는 정렬된 배열이나 리스트 기반 우선순위 큐에서의 O(n) 복잡도보다 훨씬 효율적입니다.

요소를 삭제할때도 최상단 노드를 제거한 후, 마지막 노드를 최상단으로 올리고 트리의 높이 만큼 Bubble Down 시키기 때문에 O(log n)의 시간복잡도를 가집니다.

즉, 정렬된 배열이나 리스트를 우선순위 큐로 사용할 경우, 삽입시마다 요소들을 이동해야 하므로 시간이 오래 걸릴 수 있습니다. 반면, 힙은 트리의 높이만큼만 이동하기 때문에 큰 데이터를 다룰 때도 빠르게 삽입과 삭제가 가능합니다.

우선순위 큐를 사용한 리액트의 리렌더링 최적화

리액트18 이후부터 기존 렌더링을 최적화하기 위해 Concurrent Mode라는 개념이 도입되었습니다. Concurrent Mode는 여러 요소가 렌더링 되어야 할때, 각 요소의 우선순위를 판단하여 렌더링 작업을 중지하거나 실행할 수 있게 합니다.

이러한 우선순위 제어는 React의 Scheduler라이브러리가 담당하며, 내부적으로 최소힙으로 구현되어 있습니다. Scheduler는 작업의 우선순위를 효율적으로 관리하여 우선순위가 높은 작업을 먼저 실행할 수 있도록 도와줍니다.

이번에는 리액트 스케줄러가 실제로 어떤 방식으로 구현되어 있는지, 실제 코드를 통해 살펴보고자 합니다.

/**
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * This source code is licensed under the MIT license found in the
 * LICENSE file in the root directory of this source tree.
 *
 * @flow strict
 */

type Heap<T: Node> = Array<T>;
type Node = {
  id: number,
  sortIndex: number,
  ...
};

export function push<T: Node>(heap: Heap<T>, node: T): void {
  const index = heap.length;
  heap.push(node);
  siftUp(heap, node, index);
}

export function peek<T: Node>(heap: Heap<T>): T | null {
  return heap.length === 0 ? null : heap[0];
}

export function pop<T: Node>(heap: Heap<T>): T | null {
  if (heap.length === 0) {
    return null;
  }
  const first = heap[0];
  const last = heap.pop();
  if (last !== first) {
    // $FlowFixMe[incompatible-type]
    heap[0] = last;
    // $FlowFixMe[incompatible-call]
    siftDown(heap, last, 0);
  }
  return first;
}

function siftUp<T: Node>(heap: Heap<T>, node: T, i: number): void {
  let index = i;
  while (index > 0) {
    const parentIndex = (index - 1) >>> 1;
    const parent = heap[parentIndex];
    if (compare(parent, node) > 0) {
      // The parent is larger. Swap positions.
      heap[parentIndex] = node;
      heap[index] = parent;
      index = parentIndex;
    } else {
      // The parent is smaller. Exit.
      return;
    }
  }
}

function siftDown<T: Node>(heap: Heap<T>, node: T, i: number): void {
  let index = i;
  const length = heap.length;
  const halfLength = length >>> 1;
  while (index < halfLength) {
    const leftIndex = (index + 1) * 2 - 1;
    const left = heap[leftIndex];
    const rightIndex = leftIndex + 1;
    const right = heap[rightIndex];

    // If the left or right node is smaller, swap with the smaller of those.
    if (compare(left, node) < 0) {
      if (rightIndex < length && compare(right, left) < 0) {
        heap[index] = right;
        heap[rightIndex] = node;
        index = rightIndex;
      } else {
        heap[index] = left;
        heap[leftIndex] = node;
        index = leftIndex;
      }
    } else if (rightIndex < length && compare(right, node) < 0) {
      heap[index] = right;
      heap[rightIndex] = node;
      index = rightIndex;
    } else {
      // Neither child is smaller. Exit.
      return;
    }
  }
}

function compare(a: Node, b: Node) {
  // Compare sort index first, then task id.
  const diff = a.sortIndex - b.sortIndex;
  return diff !== 0 ? diff : a.id - b.id;
}

위 코드는 실제 리액트 스케줄러의 packages/scheduler/src/SchedulerMinHeap.js 의 코드입니다.

• Node: 각 노드에는 id와 sortIndex가 있으며, sortIndex가 작은 값일수록 우선순위가 높습니다.
• push/pop: 새로운 노드를 힙에 추가하거나 삭제하는 함수로, 노드를 추가할 때는 push, 최상단 노드를 제거할 때는 pop을 이용합니다.
• ShiftUp: 새로운 노드가 추가되면, 부모 노드보다 작을 경우, 부모와 위치를 교환하여 위로 이동시킵니다.

parentIndex는 (index - 1) >>> 1 은 JavaScript의 비트 연산자 중 하나로, 부호 없는 우측 시프트 연산입니다. 이를 쉽게 설명하자면, (index - 1) >>> 1은 index - 1 값을 오른쪽으로 1비트(즉, 2로 나눈 몫)를 이동시키는 연산입니다. (Math.floor((index -1) /2 )와 동일

• shiftDown의 경우, 현재 노드와 자식 노드를 비교하며 더 작은 쪽과 자리를 바꿔 아래로 이동시킵니다. 자식 중 작은 값과 위치를 교환하는 방식으로 힙 속성을 유지하고, 두 자식이 모두 현재 노드보다 크면 종료됩니다.

여기서 주목할 부분은 shiftDown의 "helfLength"부분인데요. halfLength는 반복의 범위를 힙의 중간까지만 제한하여 불필요한 비교를 줄이기 위해서 사용됩니다.

• 힙에서 부모 노드는 인덱스가 0부터 시작하며, 자식 노드가 있는 마지막 부모 노드는 배열의 중간까지만 존재합니다.
• 힙의 배열 인덱스에서 자식 노드가 없는 마지막 부모 노드의 인덱스는 전체 길이의 절반까지입니다.

이러한 halfLength 제한을 사용해 비교 연산을 최적화하는 방식은 React의 렌더링 성능을 높일수 있습니다. 이처럼 힙 연산을 개선함으로써 React는 우선순위가 높은 작업을 더 빠르게 처리할 수 있게 됩니다. 이를 이용해서도 기존 우선순위 큐 연산을 더 개선시킬 수 있을것 같습니다.

마지막으로, React의 Concurrent Mode에서 힙을 이용한 Scheduler가 어떻게 렌더링을 최적화하는지 알아보았습니다. React의 Scheduler는 최소 힙을 이용하여 작업의 우선순위를 관리함으로써, 우선순위가 높은 작업을 먼저 처리하여 렌더링 성능을 높이는 중요한 역할을 합니다.

이런 자료구조를 공부함으로써 우리가 사용하는 프레임워크나 라이브러리의 내부 동작을 앞으로 더 깊이 이해할 수 있을것같습니다.

참조
리액트 스케줄러 최소 힙 코드

React의 Concurrent란?