알고리즘 복습/힙&우선순위 큐2

• 

  알고리즘 복습)우선순위 큐/힙 우선순위 큐 우선순위 큐는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 우선순위 큐는 일반적으로 힙트리를 이용하여 구현한다. 기본적으로 내림차순(less)으로 설정되어 있지만, Predicate를 설정하여 오름차순(greater)으로 변경할수 있다. 힙트리 힙트리는 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조이다. 힙트리 구조 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있다.(완전 이진 트리) 마지막 레벨에 노드가 있을 때는, 항상 왼쪽부터 순서대로 채워야한다. i번 노드의 왼쪽 자식/오른쪽 자식/부모는 각 각 [(2*i)+1]/[2*i+2]/[(i-1)/2]이다. 힙 트리 특징 부모 노드가 가진 값은.. 알고리즘 복습/힙&우선순위 큐 2022. 2. 10.

• 

  알고리즘 복습)트리 기초 트리 트리란 계층적 구조를 갖는 데이터를 표현하기 위한 자료구조이다. 그래프와 동일하게 노드와 간선을 가지고 있으나, 계층이 있다는 점에서 그래프와 차별점을 갖는다. 트리의 특징 트리는 다음과 같은 특징을 갖는다. 1.오직 하나의 루트 노드를 갖는다. 2.루트노드와 자식노드들은 0개 이상의 자식을 갖는다. 3.모든 자식노드는 하나의 부모노드만을 갖는다. 4.N개의 노드가 있을경우 항상 N-1개의간선을 갖는다. 트리 용어 루트 노드(root node) : 최상위 노드이며, 트리는 하나의 루트 노드만을 가진다. 단말 노드(leaf node) : 자식이 없는 노드, leaf 노드라고도 부른다. 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름) 형제(sibling): 같은 부모를 가지.. 알고리즘 복습/힙&우선순위 큐 2022. 2. 6.