Priority Queue(우선 순위 큐)에서 Heap을 선호하는 이유

앞서 Priority Queue를 구현할 때, BST보다 heap이 선호되는 이유에 대해서 알아보겠다.

컴퓨터 구조를 간단한 예시로, CPU에는 코어, L1, L2, L3캐시가 있고, 또 메모리가 존재한다.

L1에서 L3로 갈수록 속도는 느려지고, 용량은 커진다. 메모리는 L3보다 훨씬 느리지만, 용량은 매우 크다.

CPU에서 데이터를 처리하기 위해서 가장 먼저 해야할 작업은 메모리에 있는 데이터를 우선 캐시로 가져와서 코어가 작업할 수 있게끔 하는 것이다.

메모리에서의 속도는 상대적으로 매우 느리다. 만약 메모리 곳곳에 분산되어있는 4군데(linked list)에서 작업을 가져와서 처리해야한다고 친다면, 4번 메모리에서 링크를 타고 이동하며 이동하면서 속도가 굉장히 느릴 것이다. 하지만 만약 한 곳에 몰려있다면 어떨까?(Array) 그럼 한꺼번에 모든 데이터를 가져와서 처리할 수 있기 때문에 훨씬 빠르게 작업을 수행할 수 있을 것이다.

그렇기 때문에 Linked list로 구현하게 되면 배열보다 기본적으로 느릴 수 밖에 없다. 따라서 배열을 사용해서 구현하는 것을 더 선호한다. Heap은 추가적인 메모리 사용을 하지 않고 배열로 만들 수 있기 때문에 Priority Queue를 구현하는 데 Heap을 사용한다. 또한 buildHeap()과정이 O(n)에 처리된다. (BST는 insert를 매번 해야하기 때문에 O(n log n)의 시간복잡도를 가진다) 마지막으로, BST는 트리의 balance가 항상 맞는다는 보장이 없기 때문에 search할 때 log N이 보장이 되지 않는다.