목록우선순위큐 (1)

아무것도 모르는 공대생의 지식 탐험기

우선 순위큐 와 힙

우선 순위큐 란? 우선순위 큐는 말 그대로 들어간 순서와 상관없이 우선순위가 높은 것을 먼저 뽑아내기 위해 만들어진 자료구조이며, 힙(Heap)이라고도 한다. 만약 둘의 차이를 따져보자면, 우선 순위 큐는 우선 순위가 높은 데이커가 먼저 나오는 자료구조 형태라고 할 수 있고, 힙은 완전 이진 트리 형태이며 자식 노드의 값보다 부모노드의 값이 크거나 같은 자료구조의 형태이다. 2. 우선 순위 큐 (힙의 특징) : 완전 이진 트리 구조의 형태를 갖는다. 일반적으로 배열로 구현한다. 일종의 반 정렬 상태를 유지한다. (느슨한 정렬 상태) 모든 노드에 저장된 값( 우선 순위 )들은 자식 노드의 것보다 우선 순위가 크거나 같다. 직접 연결된 자식과 부모 노드 간의 크기만 비교하면 된다. 힙으로 우선 순위 큐를 구..
IT/자료구조 2022. 9. 18. 23:43
이전 Prev 1 Next 다음