CafeM0ca

heap의 응용 '우선순위 큐는 힙을 응용하여 구현한다' 라는 오류를 갖지 않도록 조심하자. 스택을 배열이나 링크드 리스트로 구현하듯이 우선순위 큐를 heap으로 구현하는 것은 여러 구현체 중 한가지일 뿐이다. 힙과 마찬가지로 (1)최대 우선순위 큐 와 (2)최소 우선순위 큐 2종류가 있다. 우선순위 큐에서는 2가지 연산을 지원한다. insert(x): 새로운 원소 x를 삽입 O(log n) extract_max(): 최대(또는 최소)값을 삭제 O(log n) 이거 한번 해본 것 같은데? 최대 힙 이 문제를 풀면서 heap을 작살나게 정복했다. 구현 template class max_priority_queue{ public: max_priority_queue() { data[0] = 0; }; void ..