CS/자료구조5 Priority Queue(우선 순위 큐)에서 Heap을 선호하는 이유 앞서 Priority Queue를 구현할 때, BST보다 heap이 선호되는 이유에 대해서 알아보겠다. 컴퓨터 구조를 간단한 예시로, CPU에는 코어, L1, L2, L3캐시가 있고, 또 메모리가 존재한다. L1에서 L3로 갈수록 속도는 느려지고, 용량은 커진다. 메모리는 L3보다 훨씬 느리지만, 용량은 매우 크다. CPU에서 데이터를 처리하기 위해서 가장 먼저 해야할 작업은 메모리에 있는 데이터를 우선 캐시로 가져와서 코어가 작업할 수 있게끔 하는 것이다. 메모리에서의 속도는 상대적으로 매우 느리다. 만약 메모리 곳곳에 분산되어있는 4군데(linked list)에서 작업을 가져와서 처리해야한다고 친다면, 4번 메모리에서 링크를 타고 이동하며 이동하면서 속도가 굉장히 느릴 것이다. 하지만 만약 한 곳에 .. 2023. 2. 2. 이전 1 2 다음