[자료구조] priority queue 우선순위 큐

heap의 응용

'우선순위 큐는 힙을 응용하여 구현한다' 라는 오류를 갖지 않도록 조심하자.

스택을 배열이나 링크드 리스트로 구현하듯이 우선순위 큐를 heap으로 구현하는 것은 여러 구현체 중 한가지일 뿐이다.

힙과 마찬가지로 (1)최대 우선순위 큐 와 (2)최소 우선순위 큐 2종류가 있다.

우선순위 큐에서는 2가지 연산을 지원한다.

1. insert(x): 새로운 원소 x를 삽입 O(log n)
2. extract_max(): 최대(또는 최소)값을 삭제 O(log n)

이거 한번 해본 것 같은데?

최대 힙 이 문제를 풀면서 heap을 작살나게 정복했다.

• 구현

   

  template<typename type>
  class max_priority_queue{
  public:
    max_priority_queue() { data[0] = 0; };
    void insert(type);
    void remove(int);
    type extract_max();
    void heapify(int);
    // 생략 자세한건 https://cafemocamoca.tistory.com/252?category=975129 여기 참조
  private:
    std::array<type, 100002> data;
    size_t len = 0;
  };
  
  

// insert
template
void max_priority_queue::insert(type d) {
++this->len;
data[this->len] = d;

for(int idx = this->len; idx > 1; idx = get_parent_idx(idx)) {
    if(data[idx] < get_parent(idx)) break;
    swap(data[idx], data[get_parent_idx(idx)]);
}

}

// remove
template
void max_priority_queue::remove(int idx) {
if(len == 0) return;
swap(data[idx], data[len]);
this->len--;
heapify(idx);
}

// extract_max
template
type max_priority_queue::extract_max() {
if(this->len == 0) return 0;
type front = data[1];
remove(1);
return front;
}

template
void max_heap::heapify(int idx){
if(idx < 1) return;
// 부모보다 작을 경우

if(data[idx] >= get_left_child(idx) && data[idx] >= get_right_child(idx)) return;

int bigger_idx = get_left_child(idx) > get_right_child(idx) ? get_left_child_idx(idx) : get_right_child_idx(idx);

swap(data[idx], data[bigger_idx]);
heapify(bigger_idx);

}