우선순위 큐라는걸 어떻게 만드냐

먼저 들어간게 먼저 나오는게 큐 잖아

아이템들에 우선순위가있는거 우선순위대로 아이템이 나오게되는거로

지금은 제일 간단한거로 사용할게요

우선순위가 변하지 않고(변할수도있고 다차원일수도있음) 그냥 값 하나고 큐에서 우선순위가 가장 같은게 큐에 남아있는거중에 가장 높은게 나온다 라고 할게요

그러면 큨에 인서트하고 딜리트하는거잖아요

우선순위 높은게 먼저 나온다고요

그럼 어레이로 구현하는시도해볼수있죠

큐 안에 우선순위 대로 sorting을 하는거에요

꺼내는건 쉬운데 중간에 들어가게되면 밀수밖에 없죠 효율이 떨어져요

그러니까 인서트가 O(N)이 될수있어요 안좋죠

소팅을 안해도요? 그럼 꺼낼때 찾아야죠 별 방법이 없죠

배열가지고는 큐는 구현되는데 priority queue는 구현이 안되는거같아요

살짝 다른얘기

우선순위 큐는 배열로 구현이 잘 안된다는거

이걸그냥 외우는 사람들이 있어요

면접같은데서 물어보는데 그런식으로 하는거보다 좋은방법은 아니죠

이유를 알아야합니다

배열로 우선순위큐를 구현하기 난감한 이유