알고리즘 강좌: 쌓기와 우선순위 대기열 실현 안내

이번 알고리즘 강좌 시리즈에서 우리는 Heap data structure와 우선순위 대기열을 실현하는 과정에서의 응용을 상세하게 소개할 것이다.

컨텐트

Background

Heap Structure

Implementation

Initialization

Inserting Values

Extracting Values

As a Priority Queue

Full Code

배경.

상상해 보아라. 너는 반드시 조작해야 할 값 목록이 있는데, 최대치에서 최소치까지의 값을 사용해야 한다. 반대로도 마찬가지다.간단한 방법은 목록을 정렬한 다음 필요한 순서에 따라 진행하는 것이다.그러나 목록에 새 값을 계속 추가하면 더 복잡해질 수 있습니다. 계속하기 전에 목록을 다시 정렬해야 합니다.목록을 다시 정렬하려면 새로운 값을 목록의 모든 다른 항목 요소와 비교해야 하기 때문에 목록이 증가함에 따라 느린 과정이 될 수 있습니다.
그 다음으로 응급실 대기구역을 상상해 보세요.신규 환자가 들어오면서 단순히 줄을 서서 의사를 기다리는 대열에 합류할 수 있지만, 이는 환자 증상의 심각성을 설명할 수 없다.심장병이 발작하는 환자는 발가락 골절 환자보다 분명히 더 중요하다. 마지막에 줄을 서더라도 먼저 도움을 받아야 한다.언제 추가되었든지 간에 우선 순위를 고려하기 위해 목록/대기열을 어떻게 조정합니까?

퇴적 구조

간단하게 목록을 반복적으로 사용하는 것보다 더미가 더 빠르고 효율적인 것은 더미 속성(max 또는min)에 따라 구축된 트리 기반 구조에 있다.가장 많은 무더기에서 나무의 뿌리는 시종 비교에 사용되는 최대 값의 요소이다. 나무의 각 노드에 대해 노드의 하위 노드는 반드시 노드의 값보다 작거나 같아야 한다.

위에서 우리는 2진법 더미, 특히 최대 더미라고 불리는 유니버설 더미를 보았다.만약 우리가 새 값 200을 대기열의 끝 (나무의 밑부분) 에 추가하고, 그룹을 정렬할 때처럼 다른 모든 값과 비교하지 않으려면, 그 값을 부모급과 비교해서 대기열의 위치가 더 높은지, 변하지 않는지 확인하십시오.이 점을 이용하면 무더기의 정확한 위치에 새 값을 삽입하는 것이 더욱 효율적이다.대O 표현법에 따르면 이 삽입 과정은 O (logn) 로 모델링될 것이다. 왜냐하면 우리는 나무의 각 층에서 가장 많은 비교를 해야 하기 때문이다. 만약에 우리가 정렬된 목록에 삽입한다면 모든 항목의 O (n) 를 비교할 수 있기 때문이다.
사용더미의 경우 과정은 언어에 따라 다르다.예를 들어 Python은 heapq library 있는데, 즉시 가져오고 사용할 수 있지만, 자바스크립트에는 본 컴퓨터의 데이터 구조가 없기 때문에 수동으로 실행해야 한다.Javascript로 이 점을 어떻게 실현하는지 봅시다.

구현

초기화

자바스크립트에서 2진법의 최대 무더기를 실현하기 위해서, 우리는 우선 새로운 클래스 MaxHeap 를 정의할 것입니다. 이 클래스의 값 속성은 빈 그룹입니다.우리는 선택적으로 size 속성을 초기화하여 무더기의 값 수량을 통계하여 미래 코드의 가독성을 높일 수 있으며 매번 쓸 필요가 없다this.values.length.

class MaxHeap {
  constructor(){
    this.values = []
    this.size = 0
  }
}

If a heap is a tree structure, why are we initializing the heap with an empty array?

모든 단일 노드의 인덱스와 두 하위 노드 간의 관계로 인해, 두 갈래 트리 구조는 트리 종류를 만드는 것이 아니라 수조로 저장될 수 있다.

모든 노드n에 대해 다음을 계산할 수 있습니다.

왼쪽 자 = 2 * n + 1

오른쪽 자 = 2 * n + 2

상위 = Math.floor( (n - 1) / 2 )

예를 들어 루트 노드의 인덱스는 0이고 왼쪽 노드는 1, 오른쪽 노드는 2이다.노드2의 하위 노드는 색인5과 6에 있습니다.

값 삽입

더미에 값을 추가하기 위해서, 우리는 그것들을 더미의 다음 빈 위치에 추가할 것이다.트리 구조에서, 이것은 이 값이 나무의 맨 밑바닥, 즉 맨 왼쪽의 빈자 위치에 있다는 것을 의미한다.수조 구조와 비교해 보면 수조의 끝에 추가할 것이다. (생각해 봐. .push()일단 값이 무더기에 있으면, 우리는 그것을 아버지 노드와 비교해야 한다. 만약 현재heap 속성을 위반한다면, 우리는 이 새 노드를 아버지 노드와 교환할 것이다.
예를 들어, 이전에 200을 가장 많은 무더기에 삽입한 예시에서, 우리는 200을 뿌리에 도달할 때까지 계속 교환해야 한다. 왜냐하면 200은 전체 무더기의 최대 값이 될 것이다.우리가 어떤 모델로 우선순위를 비교하든지 간에 우리는 비슷한 모델로 우선순위를 교환할 것이다.무더기를 통해 노드를 위로 교환하는 과정에는 많은 명칭이 있지만, 나는 그것을 '거품' 이라고 부른다.
다음은 무더기에 새 값을 삽입하는 방법입니다.무더기에 여러 개의 값이 있으면, 우리는 bubbleUp() 최신 값을 정확한 위치로 이동할 것입니다.

class MaxHeap {
  constructor(){
    this.values = []
    this.size = 0
  }

  insert(value){
    // If no value, do nothing
    if (value === undefined) return
    // Insert the value, and increment the size of the heap
    this.values.push(value)
    this.size++
    // Check to see if there is not more than 1 item in the heap
    // If there is only 1 item, there is no need to bubble up
    if (this.size > 1) this._bubbleUp()
    return this.values
  }

  _bubbleUp(){
    // Grab the most recently added value and its parent
    let currentIndex = this.size - 1
    let parentIndex = Math.floor( (currentIndex - 1) / 2 )

    // Swap the new node with its parent until the new node either
    // becomes the root, or is no longer greater than its parent
    while (parentIndex >= 0 && this.values[currentIndex] > this.values[parentIndex]){
      this._swap(currentIndex, parentIndex)
      currentIndex = parentIndex
      parentIndex = Math.floor((currentIndex - 1) / 2 )
    }
  }

  // Helper function using object destructuring to swap the elements at two indices
  _swap(index1, index2){
    [this.values[index1], this.values[index2]] = [this.values[index2], this.values[index1]]
  }
}

예:

const heap = new MaxHeap()
const values = [17,2,36,100,7,1,19,25,3,]

for (let val of values){
    heap.insert(val) 
}   
// Resulting Heap: [100, 36, 19, 25, 7, 1, 17, 2, 3]

추출값

이런 식으로 무더기를 사용하는 목적은 max/min 값(max/mix 우선순위가 있는 값)에 빠르게 접근하는 것입니다. 이것은 max를 사용하느냐min 무더기를 사용하느냐에 달려 있습니다.그것의 구조와 거품 메커니즘 때문에, 이 값은 우리가 만든 퇴적수 그룹의 첫 번째 항목이 될 것이다. 이것이 바로 우리가 추출할 값이다.
우리가 겪는 문제는, 만약 우리가 간단하게 unshift() 수조의 첫 번째 항목을 삭제한다면, 모든 수조는 색인을 다시 작성해야 한다는 것이다. 왜냐하면 모든 색인은 새로운 값을 다시 분배해야 하기 때문이다.이런 재인덱스를 피하는 유일한 방법은 목록의 마지막 항목을 삭제하는 것이다. 이것이 바로 우리가 여기서 해야 할 일이다. 더미의 첫 번째 항목과 마지막 항목을 교환하고 추출하는 것이다.
처음에 교환한 후에 컨트롤 더미의 규칙 (max/min) 을 위반할 수 있으므로, 우리는 이전의 거품처럼 그것을 회복해야 한다.이런 상황에서, 우리는 이 새로운 부적합한 값을 그것의 모든 하위 등급과 비교하고, 퇴적 규칙을 회복할 때까지 '적류' 시켜야 한다.이 과정은 때때로 선별이라고도 불린다.우리가 노드를 각 하위 노드와 비교할 때, 우리는 비교적 큰 하위 노드 (가장 많은 무더기 중) 또는 비교적 작은 하위 노드 (가장 작은 무더기 중) 를 사용하여 교환할 것이다.

class MaxHeap {
 /**
 *
 */

  extract(){
    if (this.size === 0) return
    // Swap the value to be extracted (root) with the last item in the heap
    const lastIndex = this.size - 1
    this._swap(0, lastIndex)
    // Remove the value to be extracted 
    const extractValue = this.values.pop()
    this.size--
    // If there is more than one remaining value, we must restore the heap rule
    if (this.size > 1) this._trickleDown()
    return extractValue
  }

  _trickleDown(){
    let currentIndex = 0
    /** 
    * These will be the indexes corresponding to the left and right 
    * child of the node at currentIndex
    * swapIdx will be which of the children the currentIndex will
    * actually switch with, if any
    */
    let leftIdx, rightIdx, swapIdx
    while (true) {
        leftIdx = 2 * currentIndex + 1
        rightIdx = 2 * currentIndex + 2
        swapIdx = null
        /**
        * If there is a valid left child and it is greater than the current value,
        * prepare to swap it
        */
        if (
          leftIdx < this.size &&
          this.values[currentIndex] < this.values[leftIdx]
        ) {
          swapIdx = leftIdx
        }
        /**
        * If there is a valid right child and it is greater than the current value,
        * prepare to swap it if we haven't already prepared to swap with left child.
        * If we have prepared to swap with left child, we should only choose to swapIdx
        * with the right child instead if it is greater than the left child, meaning
        * it better fits the heap rule
        */
        if (
          rightIdx < this.size &&
          ((swapIdx === null &&
            this.values[currentIndex] < this.values[rightIdx]) ||
           (swapIdx !== null && 
            this.values[rightIdx] > this.values[leftIdx]))
        ) {
          swapIdx = rightIdx
        }
        if (swapIdx === null) break // If no possible swap was ID'd, we're done
        // Swap the parent with the identified child, update the currentIndex, and repeat
        this._swap(currentIndex, swapIdx)
        currentIndex = swapIdx
    }
  }
}

이전에 생성한 무더기를 사용하여 추출한 예:

heap.extract() // 100
heap.values // [36, 25, 19, 3, 7, 1, 17, 2]
heap.extract() // 36
heap.values // [25, 7, 19, 3, 2, 1, 17]
heap.extract() // 25
heap.values // [19, 7, 17, 3, 2, 1]

우선 순위 대기열로

안내문에서 논의된 응급실 예시에서 환자가 도착한 순서만 보고 진료 순서를 기록하는 것은 현실에 맞지 않는다.따라서 우선대열을 사용하는 것은 의미가 있다. 우선대열에서 다음에 볼 환자는 가장 긴급한 수요가 있는 환자이고 그들이 언제 대열에 들어가든지 상관없다.이것은 완벽한 퇴적 용례이지만 퇴적 중의 모든 요소는 하나의 숫자가 아니기 때문에 환자 이름이나 id# 같은 다른 정보도 있을 수 있다.이런 상황에서 우리가 값을 더미에 삽입할 때, 우리는 그것을 하나의 대상으로 삽입할 수 있다. 이 대상은 환자와 우선순위의 키:value 쌍을 가지고 있다.그리고 우리는 bubbleUp()와 trickleDown() 방법을 조정하여 모든 요소의 우선순위 키의 값을 비교해야 한다.

전체 코드

위의 코드와 결합하면, 당신은 아래에서 두 개의 완전한 무더기 실현 예시를 찾을 수 있습니다.첫 번째는 요소 값 기반 maxHeap입니다.두 번째는 maxheappriorityqueue의 일종의 실현일 수 있으며 그 중의 값은 가장 높은 우선순위의 숫자에 따라 배치되며 이 숫자들은 가장 먼저 추출된다.