データ構造07優先キュー|JS

優先順位キュー|優先順位-キュー

優先キューは、通常のキューまたはスタックデータ構造と似ていますが、抽象データ型は

で、各要素に「優先度」があります.

優先キューは、優先度の高い要素を優先度の低い要素の前に配置します.2つの要素の優先度が同じである場合、

はキュー順に提供される.

優先キューは、一般にhip実装を用いるが、hip

とは概念的に異なる.

優先キューはlistまたはmapのような抽象概念

である.

リストが接続リストまたは配列によって実現できるように、優先順位キューは、hipまたは並べ替えられていない配列

のような様々な異なる方法によって実現することもできる.

最小HIPによる優先順位キュー

の最小HIPについては、要素の値を比較することによってこの手順を実行します.
優先度キューは、プロセス

を実行するためにマッピング形式で優先度を決定する.

最小臀部
:

優先キュー
:

優先度の高い(数値の低い)要素を上に移動
Github | javascript-algorithms | trekhleb
メソッド(changePriorityなど)については、上のリンクを参照してください.

export default class PriorityQueue {
  constructor() {
    if (new.target === Heap) {
      throw new TypeError('Cannot construct Heap instance directly');
    }
    // 힙을 배열로 표현함
    this.heapContainer = [];
    this.priorities = new Map();
  }

  // 왼쪽 자식의 인덱스 = 부모의 인덱스 *2 + 1
  getLeftChildIndex(parentIndex) {
    return (2 * parentIndex) + 1;
  }
  // 오른쪽 자식의 인덱스 = 부모의 인덱스 *2 + 2
  getRightChildIndex(parentIndex) {
    return (2 * parentIndex) + 2;
  }
  // 부모의 인덱스 = ((자식의 인덱스 -1) / 2 ))의 내림값
  getParentIndex(childIndex) {
    return Math.floor((childIndex - 1) / 2);
  }

  hasParent(childIndex) {
    return this.getParentIndex(childIndex) >= 0;
  }
  hasLeftChild(parentIndex) {
    return this.getLeftChildIndex(parentIndex) < this.heapContainer.length;
  }
  hasRightChild(parentIndex) {
    return this.getRightChildIndex(parentIndex) < this.heapContainer.length;
  }

  leftChild(parentIndex) {
    return this.heapContainer[this.getLeftChildIndex(parentIndex)];
  }
  rightChild(parentIndex) {
    return this.heapContainer[this.getRightChildIndex(parentIndex)];
  }
  parent(childIndex) {
    return this.heapContainer[this.getParentIndex(childIndex)];
  }

  swap(indexOne, indexTwo) {
    const tmp = this.heapContainer[indexTwo];
    this.heapContainer[indexTwo] = this.heapContainer[indexOne];
    this.heapContainer[indexOne] = tmp;
  }

  peek() {
    if (this.heapContainer.length === 0) {
      return null;
    }
    return this.heapContainer[0];
  }

  poll() {
    if (this.heapContainer.length === 0) {
      return null;
    }

    if (this.heapContainer.length === 1) {
      return this.heapContainer.pop();
    }

    const item = this.heapContainer[0];

    // 마지막 요소를 끝에서 맨 위로 올림
    this.heapContainer[0] = this.heapContainer.pop();
    this.heapifyDown();

    return item;
  }

  add(item, priority = 0) {
    this.priorities.set(item, priority);
    this.heapContainer.push(item);
    this.heapifyUp();
    return this;
  }

  remove(item) {
    // 삭제해야할 아이템의 갯수를 파악
    const numberOfItemsToRemove = this.find(item).length;

    for (let iteration = 0; iteration < numberOfItemsToRemove; iteration += 1) {
      // heapify 프로세스 후 인덱스가 변경되기 때문에
      // 삭제 후 매번 삭제할 요소의 인덱스를 찾아야함
      const indexToRemove = this.find(item).pop();

      // 마지막 요소를 삭제해야할 경우 heapify가 필요하지 않음
      if (indexToRemove === (this.heapContainer.length - 1)) {
        this.heapContainer.pop();
      } else {
        // Move last element in heap to the vacant (removed) position.
        // 마지막 요소를 삭제하는 것이 아닌 경우
        // 삭제하려는 요소의 자리에 마지막 요소의 값을 할당함
        this.heapContainer[indexToRemove] = this.heapContainer.pop();
        
        // 부모 요소를 찾음
        const parentItem = this.parent(indexToRemove);

        // Max heap의 경우
        // 부모 요소가 없거나 부모 요소가 현재 요소값보다 크면 heapify down
        // 그 외의 경우 heapify up
        if (
          this.hasLeftChild(indexToRemove)
          && (
            !parentItem
            || this.pairIsInCorrectOrder(parentItem, this.heapContainer[indexToRemove])
          )
        ) {
          this.heapifyDown(indexToRemove);
        } else {
          this.heapifyUp(indexToRemove);
        }
      }
    }
 
    this.priorities.delete(item);
    return this;
  }

  // 기존 Min heap에서는 같은 값을 가진 index를 찾아 배열로 반환했지만,
  // 우선 순위 큐에서는 priority가 같은 경우를 찾아 배열로 반환함
  find(item) {
    const foundItemIndices = [];

    for (let itemIndex = 0; itemIndex < this.heapContainer.length; itemIndex += 1) {
      if (this.priorities.get(item) === this.priorities.get(this.heapContainer[itemIndex])) {
        foundItemIndices.push(itemIndex);
      }
    }

    return foundItemIndices;
  }

  isEmpty() {
    return !this.heapContainer.length;
  }

  toString() {
    return this.heapContainer.toString();
  }

  heapifyUp(customStartIndex) {
    // 힙 컨테이너의 마지막 요소를 
    // 상위 요소에 대해 올바른 순서가 될 때까지 위로 올림    
    let currentIndex = customStartIndex || this.heapContainer.length - 1;

    // 부모 요소가 존재하고
    // && 부모 요소의 값과 현재 값을 비교해서 바꿔야 하는 상황이면 Swap
    // Swap을 했을 경우 현재 인덱스를 부모 인덱스로 업데이트
    while (
      this.hasParent(currentIndex)
      && !this.pairIsInCorrectOrder(
        this.parent(currentIndex), this.heapContainer[currentIndex]
      )
    ) {
      this.swap(currentIndex, this.getParentIndex(currentIndex));
      currentIndex = this.getParentIndex(currentIndex);
    }
  }

  heapifyDown(customStartIndex = 0) {
    // head부터 시작해서 부모 요소와 자식 요소를 비교 후
    // 올바른 순서가 될 때까지 아래로 내림
    let currentIndex = customStartIndex;
    let nextIndex = null;

    while (this.hasLeftChild(currentIndex)) {
      if (
        this.hasRightChild(currentIndex)
        && this.pairIsInCorrectOrder(
          this.rightChild(currentIndex), this.leftChild(currentIndex)
        )
      ) {
        // Max heap의 경우
        // 왼쪽 자식과 오른쪽 자식 모두 있고
        // 오른쪽 자식이 왼쪽 자식보다 클 경우 
        // 다음 인덱스는 오른쪽 자식으로 설정
        nextIndex = this.getRightChildIndex(currentIndex);
      } else {
        // 왼쪽 자식이 있는 상황에서
        // 오른쪽 자식이 없거나
        // 오른쪽 자식이 있어도, 오른쪽 자식이 왼쪽 자식보다 작거나 같을 경우
        // 다음 인덱스는 왼쪽 자식으로 설정
        nextIndex = this.getLeftChildIndex(currentIndex);
      }

      // Max heap의 경우
      // 현재 인덱스의 값이 다음 인덱스의 값보다 클 경우 => break
      if (this.pairIsInCorrectOrder(
        this.heapContainer[currentIndex],
        this.heapContainer[nextIndex],
      )) {
        break;
      }

      // Max heap의 경우
      // 현재 인덱스의 값이 다음 인덱스의 값보다 작거나 같을 경우 => swap
      this.swap(currentIndex, nextIndex);
      currentIndex = nextIndex;
    }
  }

  pairIsInCorrectOrder(firstElement, secondElement) {
    // Min Heap일 경우
    // 첫번째 인자가 두번째 인자보다 크거나 같아야함.
    // 그 반대의 경우 incorrect = true
    return firstElement < secondElement
  }
}

📚 リファレンス

Github | tech-interview-for-developer
Github | Interview_Question_for_Beginner
Github | javascript-algorithms | trekhleb
Photo by Alain Pham on Unsplash