[ Data Structure ] Priority Queue 우선순위 큐

우선순위 큐 

- 들어온 순서 상관 없이 우선순위가 높은 순으로 나가는 자료구조

- Queue와 차이점 : Queue는 First-In-First-Out 들어온 순서대로 나간다.

 

구현

- Heap 자료구조를 사용하여 구현한다. ( Max Heap )

- 새로운 요소를 삽입하는 push

- 가장 큰 값을 반환하는 pop 

class Heap {
  constructor() {
    this.heap = [];
  }
  
  push(newValue){}
  
  pop()
}

 

 

push

push(newValue) {
    const heap = this.heap;
    heap.push(newValue);
    let crnt_idx = heap.length - 1;
    let parent_idx = Math.floor((crnt_idx - 1) / 2);
    // 현재노드와 부모노드를 비교한다. 부모 노드가 더 클 경우 while문 break
    while (crnt_idx > 0 && heap[crnt_idx] > heap[parent_idx]) {
      [heap[crnt_idx], heap[parent_idx]] = [heap[parent_idx], heap[crnt_idx]];
      crnt_idx = parent_idx;
      parent_idx = Math.floor((crnt_idx - 1) / 2);
    }
  }

 

pop

pop() {
    const heap = this.heap;
    const MaxValue = heap[0];
    if (heap.length <= 1) return heap.pop();
    // 가장 마지막 노드를 루트 노드에 올린 뒤, while문을 통해서 자식 노드와 값 비교하며 스위칭.
    heap[0] = heap.pop();
    let crnt_idx = 0;
    
    while (true) {
      let left_idx = crnt_idx * 2 + 1;
      let right_idx = crnt_idx * 2 + 2;
      let temp_idx = crnt_idx;
      // heap은 완전이진트리이다. 왼쪽 노드가 없다면 오른쪽 노드는 당연 없다. 확인할 노드가 없기에 break.
      if (left_idx >= heap.length) break;
      if (heap[temp_idx] < heap[left_idx]) temp_idx = left_idx;
      if (right_idx < heap.length && heap[right_idx] > heap[temp_idx]) temp_idx = right_idx;
      // temp_idx와 crnt_idx가 같으면 crnt_idx 노드의 값이 가장 큰 경우 break.
      if (temp_idx === crnt_idx) break;
      [heap[temp_idx], heap[crnt_idx]] = [heap[crnt_idx], heap[temp_idx]];
      crnt_idx = temp_idx;
    }
    return MaxValue;
  }

 

 

 

전체 코드

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

  push(newValue) {
    const heap = this.heap;
    heap.push(newValue);
    let crnt_idx = heap.length - 1;
    let parent_idx = Math.floor((crnt_idx - 1) / 2);
    while (crnt_idx > 0 && heap[crnt_idx] > heap[parent_idx]) {
      [heap[crnt_idx], heap[parent_idx]] = [heap[parent_idx], heap[crnt_idx]];
      crnt_idx = parent_idx;
      parent_idx = Math.floor((crnt_idx - 1) / 2);
    }
  }

  pop() {
    const heap = this.heap;
    const MaxValue = heap[0];
    if (heap.length <= 1) return heap.pop();
    heap[0] = heap.pop();
    let crnt_idx = 0;

    while (true) {
      let left_idx = crnt_idx * 2 + 1;
      let right_idx = crnt_idx * 2;
      let temp_idx = crnt_idx;
      if (left_idx >= heap.length) break;
      if (heap[temp_idx] < heap[left_idx]) temp_idx = left_idx;
      if (right_idx < heap.length && heap[right_idx] > heap[temp_idx]) temp_idx = right_idx;
      if (temp_idx === crnt_idx) break;
      [heap[temp_idx], heap[crnt_idx]] = [heap[crnt_idx], heap[temp_idx]];
      crnt_idx = temp_idx;
    }
    return MaxValue;
  }
}