우선 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은 나중에 보기로 했고???
우선순위 큐의 특징과 필요한 연산을 우선 볼까?
기본적으로 삽입,삭제,탐색이 있겠네
삽입부터 보자면 데이터를 넣을 때 우선순위도 같이 집어넣어야겠지??
또한 삭제가 일어날 때는 우선순위가 높은 것부터 삭제되어야 하겠지??
탐색 또한 우선순위가 기준으로 찾아야겠지???
그니까 삭제, 탐색 같은 경우 어차피 우선순위를 다 비교해봐야되니까 자료의 순서가 상관 없겠다 그치 ㅎㅎㅎ
그냥 이런식으로 알고리즘 느낌만 알아가도 굿굿
코드는 내가 또 나중에 올리면서 주석도 달아야지 굿굿
'컴퓨터(Computer Science) > 자료구조(Data Structure)' 카테고리의 다른 글
[C언어] 자료구조 - 우선순위 큐 heap 힙 기본연산 -3 (0) | 2019.12.18 |
---|---|
[C언어] 자료구조 - 우선순위 큐 heap 힙 -2 (0) | 2019.12.18 |
Tree 이진탐색트리 Binary Search Tree(BST) [자료구조] (0) | 2019.12.16 |
[C언어] 자료구조 - Tree 트리 순회,기본연산 -3 (0) | 2019.12.15 |
[C언어] 자료구조 - Tree 트리 구현 -2 (0) | 2019.12.15 |