[우선순위 큐와 heap] - 중요한 거 먼저!!

우선순위 큐

우선순위 큐는 각 요소가 우선순위를 가지며 우선순위에 따라 요소가 처리되는 데이터 구조

 

 

주요 연산

 

• Insert: 새로운 요소를 큐에 추가합니다.
• Remove: 가장 높은 우선순위를 가진 요소를 제거하고 반환합니다.
• peek: 가장 높은 우선 순위를 가진 요소를 제거하지 않고 반환합니다.

 

 

구현 방법

리스트를 이용한 구현과 힙을 이용한 구현이 있다

힙을 이용한 구현이 더 효율성이 좋은데

 

리스트 이용한 구현은 삽입 시 정렬된 위치를 찾아야 하기 때문에 O(n)

삭제 시는 최대  or 최소 값을 삭제하면 되기 때문에 O(1)의 시작 복잡도를 가진다

하지만

힙을 이용한 구현은 이진 트리 구조로 탐색할 때마다 탐색할 범위가 줄어들기 때문에

삽입과 삭제 모두 시간 복잡도가 O(log n)가 된다

---

 

힙

완전 이진 트리 자료구조 일종

 

* 이진트리 : 자녀가 최대 2개인 트리

* 완전 이진 트리 : 루트 노드부터 시작하여 왼쪽 노드 자식, 오른쪽 노드 자식 순서대로 데이터가 차례대로 삽입되는 트리

 

완전 이진 트리

힙 속성

 

• 최소 힙 (Min Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같은 루트 노드가 최솟값
• 최대 힙 (Max Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같은  루트 노드는 최댓값

최대힙

 

 

---

 

최대힙 문제 풀어보기

https://www.acmicpc.net/problem/11279

 

해당 문제는 최대 힙의 속성을 이용하여

0이면 출력 아니면 인서트 하여 총 출력시키면 되는 문제이다

 

최적화 전

const input = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');

const cmd = input.slice(1).map(Number);

const solution = cmd => {
  let result = [];
  let tmp = [];

  cmd.map(v => {
    if (v === 0 && tmp.length > 0) {
      tmp.sort((a, b) => b - a);
      result.push(tmp[0]);
      tmp.shift();
    } else if (v === 0 && tmp.length == 0) {
      result.push(0);
    } else if (v !== 0) {
      tmp.push(v);
      tmp.sort((a, b) => b - a);
    }
  });
  return result.join('\n');
};

console.log(solution(cmd));

 

시간 초과가 나온 코드이다.

최대 힙 속성을 유지하기 위해 매번 sort()를 사용하여 성능과 효율이 좋지 못했다.

 

최적화 후

const input = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');

const cmd = input.slice(1).map(Number);

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

  insert(v) {
    this.items.push(v);
    this.up();
  }

  up() {
    let idx = this.items.length - 1;
    while (idx > 0) {
      const parent_idx = Math.floor((idx - 1) / 2);
      if (this.items[idx] <= this.items[parent_idx]) break;
      [this.items[idx], this.items[parent_idx]] = [
        this.items[parent_idx],
        this.items[idx],
      ];
      idx = parent_idx;
    }
  }
  peek() {
    if (this.items.length === 0) return 0;
    const max = this.items[0];
    const end = this.items.pop();

    if (this.items.length > 0) {
      this.items[0] = end;
      this.down();
    }
    return max;
  }

  down() {
    let idx = 0;
    while (true) {
      let max = idx;
      const left = 2 * idx + 1;
      const right = 2 * idx + 2;

      if (left < this.items.length && this.items[left] > this.items[max]) {
        max = left;
      }

      if (right < this.items.length && this.items[right] > this.items[max]) {
        max = right;
      }

      if (max === idx) break;
        [this.items[idx], this.items[max]] = [this.items[max], this.items[idx]];
      idx = max;
    }
  }
}

const solution = cmd => {
  let result = [];
  const Heap = new heap();

  cmd.map(v => {
    if (v === 0) {
      result.push(Heap.peek());
    } else {
      Heap.insert(v);
    }
  });

  return result.join('\n');
};

console.log(solution(cmd));

 

코드가 길어지긴 했지만 최대 힙을 구현하는 class를 적용하여 문제를 풀 수 있었다

아직은 최대 힙을 구현하는 부분이 익숙하지 않지만 익숙해지게 연습해야겠다