[C언어] 자료구조 - 우선순위 큐 priority queue -1

우선 Queue라는 또 다른 자료구조 형태가 있다. 참 많지,, 자료구조형태가??

자료마다 용도가 다르니 다르게 저장하고 다르게 꺼낼 수 밖에 ㅠㅠㅠ 

 

 

 

근데 큐면 큐지 무슨 우선순위 큐가 있는거지...? 라고 생각할 수 있지

뭐랄까.. 비행기 탈때도 VIP들은 다른 입구로 들어가잖아??

그런 것과 같이 조금 차등을 둔다고하는거지

 

 

 

그니까 뭐 순위를 줘가지고 우선순위가 가장 높은 사람을 먼저 태우는 것처럼 자료도 우선순위가 높은 것을 출력한다 뭐 이런 비슷한 느낌을 가지면 될거야.

 

 

 

우선순위 큐가 이용되는 분야는 시뮬레이션, 네트워크 트래픽 제어, OS의 작업 스케쥴링 이런 곳?

 

 

 

아무튼 우선순위 큐는 스택으로도, 큐로도 구현할 수 있는데 그보다 제일 효율적인 구조는 heap이라는 구조인데 나중에 더 자세히 살펴보도록하자. 왜 heap을 효율적이라고 하냐면...?

 

 

 

아 표 겁나크게 만들어졌어...ㅡㅡ 아무튼 시간적으로 훨씬 효율적이란 말씀

표현   방법	삽    입	삭    제
순서없는 배열	O(1)	O(n)
순서없는 연결 리스트	O(1)	O(n)
정렬된 배열	O(n)	O(1)
정렬된 연결 리스트	O(n)	O(1)
힙	O(logn)	O(logn)

정렬되었다고 보고 왜 저런식으로 나오는지 한 번 설명해볼게

 

 

우선 스택으로 구현할 수 있고?

 

 

우선순위가 있어야한다고 했잖아?? 근데 스택에서는 어디에 내가 들어가야하는지를 조사하려면 모든 자료를 조사할 수 밖에 없어.. 하나라도 나보다 높은데 내가 먼저나가면 안되잖아. 그래서 자료가 n개일 떄 다 조사하니까 O(n)!!!

삭제는 우선순위대로 정렬되어있으니 그냥 내보내면 되겠지??

 

 

연결리스트로도 구현할 수 있고??

 

 

 

얘도 우선순위가 있어야하는데,, 삽입하려면 내가 어느 위치에 들어가야할 지 다뒤져봐야겠지. 그래서 또한 n

삭제도 또한 순서대로 정렬되어있으니 우리는 그냥 뽑기만할 뿐!! 

 

 

 

heap은 나중에 보기로 했고???

 

 

 

우선순위 큐의 특징과 필요한 연산을 우선 볼까?

 

기본적으로 삽입,삭제,탐색이 있겠네

삽입부터 보자면 데이터를 넣을 때 우선순위도 같이 집어넣어야겠지??

또한 삭제가 일어날 때는 우선순위가 높은 것부터 삭제되어야 하겠지??

탐색 또한 우선순위가 기준으로 찾아야겠지???

 

그니까 삭제, 탐색 같은 경우 어차피 우선순위를 다 비교해봐야되니까 자료의 순서가 상관 없겠다 그치 ㅎㅎㅎ

 

그냥 이런식으로 알고리즘 느낌만 알아가도 굿굿

 

코드는 내가 또 나중에 올리면서 주석도 달아야지 굿굿