우선순위 큐랑 힙이라는 걸 이제 막 배웠는데요, 계속 드는 생각이 "이거 그냥 정렬해서 쓰면 되는 거 아냐?"라는 거예요. 우선순위 큐가 항상 제일 작은(또는 큰) 값을 먼저 꺼내주는 자료구조라던데, 그럼 그냥 배열 정렬해놓고 앞에서부터 하나씩 빼면 똑같은 거 아닌가요?
제가 아는 대략적인 복잡도는 이 정도인데요.
정렬 후 순서대로 꺼내기 : 정렬 O(n log n)
힙 : 삽입 O(log n), 최솟값 꺼내기 O(log n)
여기서 궁금한 게, 어차피 둘 다 log n이 붙는데 왜 굳이 힙이라는 별도 자료구조를 쓰는 거죠? 정렬 한 번 딱 해두면 꺼내는 건 O(1)인데 힙은 꺼낼 때마다 O(log n)이면 오히려 손해 아닌가 싶기도 하고요.
혼자 생각해보니 데이터가 중간중간 계속 새로 들어오는 경우엔 정렬을 매번 다시 해야 하니까 그때 힙이 유리한 건가 싶긴 한데, 이게 맞는 방향인지 모르겠어요. 다익스트라 같은 데서 힙 쓴다는 것도 들었는데 왜 거기서 쓰는 건지도 잘 이해가 안 가고요. 실무나 문제풀이에서 "아 이건 힙이다" 싶은 딱 떨어지는 상황을 알려주시면 감이 올 것 같아요.