- 우선순위 큐
큐는 먼저 들어간 데이타가 먼저 나간다.(FIFO) 하지만 우선순위 큐는 우선 priority가 높은 데이터가 먼저 나가게 되는 것이다.
우선 순위 큐는 배열, 링크드리스트, 힙을 이용해서 구현할 수 있다.
하지만 배열은 데이터 삽입 삭제 과정에서 데이터를 한 칸씩 당기고 밀어야 하는 연산을 계속해야 한다. 또한, 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위를 비교해야 한다.
또, 링크드 리스트는 삽입의 위치를 찾기 위해 첫번째 노드에서부터 마지막 노드에 저장된 데이터와 우선순위 비교를 진행해야 한다. 데이터가 많아질 수록 노드 수에 비례하여 비교해야하기 때문에 성능이 저하된다.
힙의 특성으로 봤을 때 우선순위가 가장 높은 것을 고를 때 루트를 먼저 나가게 하면 된다.
그리고 다시 힙을 구성할 때 트리의 높이 log n이란 타임 복잡도가 걸리므로 다른 자료구조보다 우선순위큐에 효율적이라고 할 수 있겠다.
- Heap
- Delete
삭제하고자 하는 노드와 가장 끝에 있는 리프노드. 예를 들어 배열로 구성하였을 때 가장 끝 인덱스 노드와 스왑한 후에 힙을 재구성한다. 이 때 재구성할 때의 타임 복잡도는 트리의 높이만큼인 logn.
바이너리 서치 트리(BST)
모든 element는 중복되지 않는 키를 갖고 있다.
left subtree의 키 값은 루트 보다 작아야 되고 right subtree의 키 값은 루트보다 커야 된다.
Left < root < Right
key값으로 찾을 수도 있고, rank(몇번째 작은 값)로도 찾을 수 있다.
DFS로 보통 함.
- BST Deletion (자식 노드가 1개일 때)
- BST deletion (자식 노드가 2개일 때)
