최대힙, 최소힙 직접 구현하기

1. 힙(heap) 프로그램 실행중에 내가 사용할 수 있는 메모리 양이 변할 수 있는 경우, 그 때 사용하는 메모리 공간을 힙이라고도 하는데.. 여기서는 자료구조를 말한다. 기본적으로 "완전 이진 트리"를 이용한 자료구조이다. 특히 "완전 이진 트리"에 있는 노드 중에서 키값이 가장 큰 노드나 가장 작은 노드를 찾기 위해 특별히 만든 자료구조 완전 이진 트리니까, n개의 노드가 주어진다면 길이 n+1의 단순 배열로 저장할 수 있다 처음에 만들때, 키값이 가장 큰 노드를 찾는 자료구조를 만들 것이냐, 키값이 가장 작은 노드를 찾는 자료구조를 만들 것이냐,를 정하고 들어간다. 2. 최대힙(max heap)과 최소힙(min heap) 2-1) 최대힙(max heap) 키값이 가장 큰 노드를 찾기 위한 완전 이..

• format_list_bulleted 그래프 이론 정복기
• · 2022. 10. 2.
• textsms

트리 이론 기본편 -중위 순회의 특징 응용하기-

1. 이진 탐색 트리의 특징 이진 탐색 트리는 어떠한 경우에도 왼쪽 서브 트리의 루트 루트 > 오른쪽 서브트리 순서대로 순회를 하게 된다. 그렇다면 주어진 이진 트리의 노드를 중위순회한다면, 트리에 넣어야할 데이터의 순서가 주어지며 그러한 순서대로 데이터를 작은 값부터 넣으면 "왼쪽 서브 트리의 루트 2 > 3 > 4 > 5 > ..

• format_list_bulleted 그래프 이론 정복기
• · 2022. 9. 15.
• textsms

트리 이론 기본편2 -이진 트리 용어 + 트리의 순회 -

1. 이진트리 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리 모든 노드들이 자식 노드를 "최대" 2개까지만 가질 수 있는 트리 각 자식 노드를 왼쪽 자식 노드(left child node), 오른쪽 자식 노드(right child node) 이진 트리 예시 4가지.. 모든 노드가 자식 노드를 "최대" 2개만 가지면 이진 트리가 된다 자식 노드가 아예 없어도 된다는 소리 2. 특징 레벨 i에서(높이 i에서) 노드의 최대 개수는 $2^{i}$개 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 h+1개 최대 개수는 $2^{h+1}-1$개 3. 종류 이진트리의 종류에 따라 저장, 표현, 알고리즘 등이 달라질 수 있으므로 잘 구분해야한다 3-1) 포화 이진 트리(full binary tree..

• format_list_bulleted 그래프 이론 정복기
• · 2022. 9. 13.
• textsms