c++ priority_queue vs heap

<queue> 라이브러리에 들어있다.

 

-> que인데 우선순위가 있는 (정렬되어 있는) 큐라고 생각하면 된다.

 

사용하는 함수들은 기본 queue와 같다

(push, pop... 등등)

=> 근데 제일 끝 원소를 가져올 때 그냥 queue는 front로 했던것같은데

priority_queue는 top으로 가져온다.

---

이 글의 목적은... heap을 사용했을 때 통과못한 효율성테스트가, 우선순위큐를 사용하니까 통과해서 정리해본다.

 

https://learn.microsoft.com/en-us/cpp/standard-library/priority-queue-class?view=msvc-170

priority_queue Class

위 글에 따르면

priority_queue에 원소를 추가하고 삭제하는건 log 시간복잡도가 소요되다고 되어있다.

 

근데!! heap은?? (make_heap을 할 때)

https://en.cppreference.com/w/cpp/algorithm/make_heap

std::make_heap - cppreference.com

시간복잡도가 n이다!!

 

결론

heap이랑 queue랑 계속 구분된 무언가로,, 생각했다;;;ㅋㅋ;;;;;;;

어우 바보같아

 

queue를 구현하는 방법 -> heap!

시간복잡도에서의 차이는?

=> push_heap을 사용하면, logn이 된다

https://en.cppreference.com/w/cpp/algorithm/push_heap

std::push_heap - cppreference.com

 

아무튼,,,, 자료구조 공부를 다시해야할판이다 다까먹었어;;