[알고리즘] Priority Queue

우선순위 큐

우선순위 큐(Priority Queue)는 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리되는 자료구조이다.
큐는 선형 자료구조이고, 우선순위 큐는 비 선형 자료구조이다. 우선순위 큐는 자료가 들어온 순서와 상관 없이 미리 정한 우선순위대로 나간다.

구현방법

다른 언어와는 달리 자바스크립트에는 내장된 priority queue가 없으므로 heap을 통해 직접 구현해야 한다.

minheap 구현

class minHeap {
  constructor() {
    this.heap = [];
    this.heap.push(-Infinity); // 무한대 루트노드에 넣기
  }
  insert(val) {
    this.heap.push(val); // 배열에 일단 값 삽입
    this.upheap(this.heap.length - 1); // 배열 위치 자동변경
  }
  upheap(pos) {
    let tmp = this.heap[pos]; // 현재 값 tmp에 저장
    while (tmp < this.heap[parseInt(pos / 2)]) {
      // 부모노드와 비교하여 작은 경우 계속 루트쪽으로 올라감
      this.heap[pos] = this.heap[parseInt(pos / 2)]; // 부모노드보다 작으면 부모노드가 현재노드로 옴
      pos = parseInt(pos / 2); // 부모노드의 index 번호로 변경
    }
    this.heap[pos] = tmp; // 부모노드 보다 tmp가 큰 상태이므로 heap[pos]에 tmp값을 넣어줌
  }
  get() {
    if (this.heap.length === 2) return this.heap.pop();
    let res = this.heap[1];
    this.heap[1] = this.heap.pop(); // 맨 마지막 노드를 루트(인덱스1) 노드에 넣음  *인덱스0:INFINITy
    this.downheap(1, this.heap.length - 1);
    return res; // 제일 작은 값 반환
  }
  downheap(pos, len) {
    let tmp = this.heap[pos],
      child;
    while (pos <= parseInt(len / 2)) {
      // 마지막 부모까지만 내려간다
      child = pos * 2;
      // pos의 왼쪽자식, 오른쪽자식 비교
      if (child < len && this.heap[child] > this.heap[child + 1]) child++;
      // tmp가 자식보다 작으면 멈춤
      if (tmp <= this.heap[child]) break;
      this.heap[pos] = this.heap[child]; // 자식 값이 부모값으로 이등
      pos = child;
    }
    this.heap[pos] = tmp;
  }
  size() {
    return this.heap.length - 1;
  }
  front() {
    return this.heap[1];
  }
}

maxheap 구현

class maxHeap {
  constructor() {
    this.heap = [];
    this.heap.push(Infinity); // 무한대 루트노드에 넣기
  }
  insert(val) {
    this.heap.push(val); // 배열에 일단 값 삽입
    this.upheap(this.heap.length - 1); // 배열 위치 자동변경
  }
  upheap(pos) {
    let tmp = this.heap[pos]; // 현재 값 tmp에 저장
    while (tmp > this.heap[parseInt(pos / 2)]) {
      // 부모노드와 비교하여 큰 경우 계속 루트쪽으로 올라감
      this.heap[pos] = this.heap[parseInt(pos / 2)]; // 부모노드보다 크면 부모노드가 현재노드로 옴
      pos = parseInt(pos / 2); // 부모노드의 index 번호로 변경
    }
    this.heap[pos] = tmp; // 부모노드 보다 tmp가 작은 상태이므로 heap[pos]에 tmp값을 넣어줌
  }
  get() {
    if (this.heap.length === 2) return this.heap.pop();
    let res = this.heap[1];
    this.heap[1] = this.heap.pop(); // 맨 마지막 노드를 루트(인덱스1) 노드에 넣음  *인덱스0:INFINITy
    this.downheap(1, this.heap.length - 1);
    return res; // 제일 큰 값 반환
  }
  downheap(pos, len) {
    let tmp = this.heap[pos],
      child;
    while (pos <= parseInt(len / 2)) {
      // 마지막 부모까지만 내려간다
      child = pos * 2;
      // pos의 왼쪽자식, 오른쪽자식 비교
      if (child < len && this.heap[child] < this.heap[child + 1]) child++;
      // tmp가 자식보다 크면 멈춤
      if (tmp >= this.heap[child]) break;
      this.heap[pos] = this.heap[child]; // 자식 값이 부모값으로 이등
      pos = child;
    }
    this.heap[pos] = tmp;
  }
  size() {
    return this.heap.length - 1;
  }
  front() {
    return this.heap[1];
  }
}

사용방법

let maxQueue = new maxHeap();
let minQueue = new minHeap();

maxQueue.insert(3); // 값 삽입
maxQueue.get(); // 값 제거
maxQueue.front(); // 가장 큰 값 반환
maxQueue.front(); // 가장 작은 값 반환
maxQueue.size(); // 우선순위 큐의 길이 반환