힙
-
[ 비선형 자료구조 ] 우선순위 큐(Priority Queue) & 힙(Heap)Computer Science/자료 구조 2023. 1. 20. 15:46
1. 우선순위 큐(priority queue) 1) 개념 FIFO 규칙을 따르는 일반적인 큐와는 다르게, 데이터간 우선순위를 할당하고 우선순위에 따른 보다 효율적인 삽입, 삭제등의 연산을 구현한 추상 자료구조를 우선순위 큐라한다. 따라서, 우선순위 큐에선 높은 우선순위를 지닌 요소가 비교적 낮은 요소보다 앞서 디큐, 접근된다. 2) 특징 우선순위 큐는 배열 운영 체제, 네트워크 라우팅 알고리즘, 데이터 압축 알고리즘 등에서 널리 사용되, 연결리스트 등을 이용해 구현 가능하지만 삽입, 삭제 연산의 시간복잡도 측면에서 힙을 사용하는 것이 효율적이기 때문에 일반적으로 힙을 사용해 구현한다. (배열이나 연결 리스트를 사용할 경우 우선순위가 중간쯤 위치한 데이터의 삽입 시 배열의 경우 대상 인덱스 이후의 모든 데..
-
[ 비선형 자료구조 ] 트리Computer Science/자료 구조 2023. 1. 18. 07:23
트리 1. 개념 트리는 그래프의 한 종류로서 각 노드가 특정 값을 저장하고 하나 이상의 자식 노드에 대한 참조값을 가지고 있는 자료구조이다. 트리를 구성하는 노드들은 계층구조로 이루어져있으며 최상위 노드를 root라 한다. 트리는 일반적으로 파일 시스템, 데이터 베이스, 의사결정 알고리즘 등에서 사용된다. 2. 용어 root : 부모 노드가 존재하지 않는 노드, 최상위 노드 (A) node : 데이터와 다음 노드에 대한 주소값을 저장한 자료구조 leaf : 자식노드가 존재하지 않는 노드, 최하위 노드 (H, I, E, J, K, L) parent : 하나 이상의 자식 노드를 가진 노드 (A, B, C, D, F, G) child : 다른 노드의 자손인 노드 (B, C, D, E, F, G, H, I, J..