힙(Heap)
힙은 완전 이진트리(Complete Binary Tree)의 형태를 가지며, 부모 노드와 자식 노드 간의 특정한 순서 관계를 가지는 이진트리입니다.. 힙은 주로 최댓값이나 최솟값을 빠르게 찾기 위해 사용되는 자료구조로, 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 구분됩니다. 최대 힙은 부모 노드가 자식 노드보다 항상 큰 값을 가지고, 최소 힙은 부모 노드가 자식 노드보다 항상 작은 값을 가집니다. 힙은 우선순위 큐(Priority Queue)와 함께 사용되며, 힙 정렬(Heap Sort)에도 활용됩니다.
완전 이진트리(Complete Binary Tree)는 마지막 레벨을 제외하고는 모든 레벨이 꽉 채워진 이진트리입니다..
힙 정렬(Heap Sort)
힙 정렬은 힙(Heap) 자료구조를 기반으로 한 정렬 알고리즘입니다. 힙 정렬은 다음과 같은 단계로 이루어집니다.
1. 주어진 배열을 최대 힙(Max Heap)으로 구성합니다.
2. 최대 힙에서 최댓값(루트( 노드)을 추출하여 정렬된 배열의 가장 뒤쪽으로 이동합니다.
3. 남은 요소들로 다시 최대 힙을 구성하고, 최댓값을 추출하여 정렬된 배열에 추가합니다.
4. 위의 과정을 반복하여 배열이 정렬될 때까지 진행합니다.
힙 정렬은 안정적인 정렬 알고리즘이며, 평균적으로 시간 복잡도가 O(n log n)입니다. 힙 정렬은 다른 정렬 알고리즘과 비교하여 데이터의 이동 횟수가 상대적으로 적다는 장점이 있습니다. 그러나 추가적인 공간이 필요하며, 배열 안에서 직접 정렬하는 제자리 정렬(in-place sorting) 알고리즘이 아닙니다.
힙 정렬은 우선순위 큐와 밀접한 관련이 있으며, 힙을 구현하고 활용하는 방법을 이해하는 것은 우선순위 큐와 정렬 알고리즘에 대한 이해를 높일 수 있습니다.
트리(Tree)
트리는 계층적인 구조를 가지는 비선형 자료구조입니다. 루트(Root) 노드를 기준으로 부모-자식 관계로 구성되며, 각 노드는 0개 이상의 자식 노드를 가질 수 있습니다. 트리는 다양한 종류의 트리가 존재하며, 이진 트리이진트리(Binary Tree)는 각 노드가 최대 2개의 자식 노드를 가지는 트리입니다. 이진트리는 이진 탐색 트리(Binary Search Tree), AVL 트리, 힙 등 다른 자료구조의 기반이 되기도 합니다. 트리는 계층적인 데이터를 표현하고 탐색, 삽입, 삭제 등을 효율적으로 수행하는 데 사용됩니다.
그래프(Graph)
그래프는 노드(Node)와 그 노드를 연결하는 간선(Edge)으로 구성되는 자료구조입니다. 그래프는 네트워크, 도로망, 소셜 네트워크 등 다양한 상황을 모델링할 수 있습니다. 그래프는 방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 구분됩니다. 그래프는 깊이 우선 탐색(Depth-First Search, DFS), 너비 우선 탐색(Breadth-First Search, BFS) 등 다양한 탐색 알고리즘에 활용됩니다. 또한 그래프는 최단 경로 문제, 연결성 검사, 최소 스패닝 트리(Minimum Spanning Tree) 등에 활용됩니다.
이러한 자료구조들은 다양한 문제를 해결하는 데 사용됩니다. 각각의 자료구조는 특정한 특성과 용도를 가지고 있으며, 알고리즘과 함께 사용되어 다양한 프로그래밍 문제를 효율적으로 해결할 수 있습니다.
관심이 있으신 분들에게 유용한 정보였길 바라며
다음 주제로는 시간복잡도(Big O 표기법)에 대해 알아보도록 하겠습니다.