[자료구조] 자바스크립트로 우선순위 큐(Priority Queue) 구현하기

우선순위 큐란?

- 일반적인 큐는 선입선출 (FIFO)원칙에 따라 데이터가 처리된다.

- 우선순위 큐는 각 데이터들이 우선순위가 있어서, 큐에 들어온 순서는 차순위가 되고 정해진 우선순위에 따라 데이터가 큐에서 나가게 된다.

 

Heap 자료구조

- Heap 자료구조는 완전 이진트리의 일종이다. 

- 완전이진트리란 루트 노드부터 시작하여 왼쪽 자식, 오른쪽 자식 순서대로 데이터가 삽입되는 트리를 말한다.

- Heap은 항상 루트 노드를 제거하는 식으로 동작한다.

- 자바스크립트로 우선순위 큐를 구현하는데 있어서 이 Min Heap (최소 힙) 자료구조를 사용한다.

- 최소 힙은 부모 노드가 항상 자식 노드보다 값이 작다는 특징을 갖고 있다. 

출처 : https://www.geeksforgeeks.org/difference-between-min-heap-and-max-heap/

 

일반 배열을 사용하지 않는 이유는 무엇일까? 

- 데이터를 조회하기 위해 배열을 순회하게 되면 O(n)의 시간 복잡도가 걸린다. 

- 힙을 사용하게 되면 O(1)의 시간복잡도까지 낮출 수 있다. 

- 자료를 추가로 삽입하거나 삭제하는 경우에도 O(logn)의 시간복잡도로, 굉장히 높은 효율성을 가진다.

---

최소 힙 기반의 우선순위 큐를 직접 구현해보자.

2차원 트리를 선형적인 배열로 구현할 수 있다.

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

생성자 함수로는 우선 빈 배열을 만든다.

 

 

 size() {
  	return this.heap.length
  }
  
  isEmpty() {
  	return this.heap.length === 0
  }

우선순위 큐의 사이즈와 비어있는지 여부를 확인하는 메서드들을 추가한다.

 

데이터 삽입 기능을 구현해보자

 enqueue(value) {
  	this.heap.push(value);
    this.heapifyUp();
  }

 

enqueue라는 메서드를 추가하여 힙 배열에 추가하려는 값을 push하였다.

이후 최소 힙 원칙에 따라 정렬하는 heapifyUp메서드를 실행한다.

heapifyUp 메서드에 대한 상세 구현은 아래에서 살펴보자.

 

 heapifyUp() {
  	let i = this.size() - 1;
    const lastNode = this.heap[i];
    
    while (i > 0) {
      const parentIndex = Math.floor((i - 1) / 2);
      
      if (this.heap[parentIndex] > lastNode) {
        this.heap[i] = this.heap[parentIndex];
        i = parentIndex;
      } else {
        break;
      }
    }
    
    this.heap[i] = lastNode;
  }

부모노드의 인덱스를 계산하여 크기 비교를 하고, 더 작다면 위치를 바꿔주는 반복문을 통해 맨끝에 새로 삽입된 노드를 정렬해주는 코드이다. 

 

삽입을 구현했으니, 노드를 삭제하는 것도 구현해보자.

dequeue() {
    if (this.isEmpty()) return null;
    
    const rootNode = this.heap[0];
    const lastNode = this.heap.pop();
    this.heap[0] = lastNode;
    this.heapifyDown();
    
    return rootNode;
  }

앞서 말했다시피 힙에서의 삭제는 항상 루트노드에서만 일어난다. 루트 노드 자리를 제일 마지막 노드로 가져오고 heapifyDown 메서드로 정렬해주면 자연스레 기존의 루트 노드는 참조를 잃고 큐에서 사라지게 된다.

 

  heapifyDown() {
  	let i = 0;
    const rootNode = this.heap[i];
 	const heapSize = this.size();
    let swapIndex;
    
    while (true){
    	let leftChildIndex = i * 2 + 1;
    	let rightChildIndex = (i * 2) + 2;
        
        if (leftChildIndex < heapSize) {
            if (this.heap[leftChildIndex] < this.heap[i]) {
                swapIndex = leftChildIndex
        	}
        }
        
        if (rightChildIndex < heapSize) {
        	f (
                (swapIndex === null && this.heap[rightChildIndex] < this.heap[i]) ||
                (swapIndex !== null && this.heap[rightChildIndex] < this.heap[leftChildIndex])
            ) {
                swapIndex = rightChildIndex;
            }
        }
        if (swapIndex === null) break;
        
        [this.heap[i], this.heap[swapIndex]] = [this.heap[swapIndex], this.heap[i]];
        i = swapIndex;
    }
  }

heapifyDown은 상위 루트노드를 좌우의 자식노드와 비교하여 트리의 하위로 점점 내리면서 정렬시키는 메서드이다. 왼쪽 자식과 오른쪽 자식 중 바꾸어야할 인덱스를 swapIndex로 지정하여 노드 위치를 교환한다.

 

전체 코드

전체 코드는 다음과 같다.

class PriorityQueue {
  constructor() {
  	this.heap = [];
  }
  
  size() {
    return this.heap.length
  }
  
  isEmpty() {
  	return this.heap.length === 0
  }
 
  heapifyUp() {
  	let i = this.size() - 1;
    const lastNode = this.heap[i];
    
    while(i > 0) {
      const parentIndex = Math.floor((i - 1) / 2);
      
      if (this.heap[parentIndex] > lastNode) {
        this.heap[i] = this.heap[parentIndex];
        i = parentIndex;
      } else {
        break;
      }
    }
    
    this.heap[i] = lastNode
  }
 
  enqueue(value) {
   	this.heap.push(value);
    this.heapifyUp();
  }
  
  dequeue() {
    if (this.isEmpty()) return null;
    
    const rootNode = this.heap[0];
    const lastNode = this.heap.pop();
    this.heap[0] = lastNode;
    this.heapifyDown();
    
    return rootNode;
  }
  
  heapifyDown() {
  	let i = 0;
    const rootNode = this.heap[i];
 	const heapSize = this.size();
    let swapIndex;
    
    while(i > 0) {
    	let leftChildIndex = i * 2 + 1;
    	let rightChildIndex = (i * 2) + 2;
        
        // 왼쪽 자식 인덱스가 범위 안에 있고,
        if (leftChildIndex < heapSize) {
        	// 대상이 왼쪽 자식보다 크다면, 왼쪽 자식 인덱스를 바꿔야할 인덱스로 지정
            if (this.heap[leftChildIndex] < this.heap[i]) {
                swapIndex = leftChildIndex
        	}
        }
        // 오른쪽 자식 인덱스가 범위 안에 있고, 
        if (rightChildIndex < heapSize) {
        	if (
            // 바꿔야할 인덱스가 지정된 값이 없고, 대상이 오른쪽 자식보다 크거나
                (swapIndex === null && this.heap[rightChildIndex] < this.heap[i]) ||
            // 바꿔야할 인덱스가 왼쪽으로 지정되어 있지만, 왼쪽 자식이 오른쪽 자식보다 크다면
                (swapIndex !== null && this.heap[rightChildIndex] < this.heap[leftChildIndex])
            ) {
            // 바꿔야할 인덱스로 오른쪽 자식 인덱스를 지정한다.
                swapIndex = rightChildIndex;
            }
        }
        // 바꿔야할 인덱스가 없다면 반복문 종료
        if (swapIndex === null) break;
        
        // 바꿔야할 인덱스와 대상의 위치를 바꿔준다.
        [this.heap[i], this.heap[swapIndex]] = [this.heap[swapIndex], this.heap[i]];
        i = swapIndex;
    }
    
  }
}

---

글을 쓰는데 도움이 된 자료들

https://jun-choi-4928.medium.com/javascript%EB%A1%9C-heap-priority-queue-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-8bc13bf095d9

JavaScript로 Heap | Priority Queue 구현하기

https://stackoverflow.com/questions/42919469/efficient-way-to-implement-priority-queue-in-javascript

Efficient way to implement Priority Queue in Javascript?