ITPE * JackerLab

개요힙(Heap)은 완전 이진 트리 기반의 자료구조로, 부모 노드와 자식 노드 간의 우선순위 조건을 만족하는 구조이다. 최소 힙(Min Heap)은 부모 노드 ≤ 자식 노드, 최대 힙(Max Heap)은 부모 노드 ≥ 자식 노드의 조건을 만족한다. 주로 **우선순위 큐(Priority Queue)**로 활용되며, 삽입/삭제 모두 평균 O(log n)의 성능을 제공한다.1. 힙의 구조 및 특징 항목 설명 트리 구조완전 이진 트리(왼쪽부터 채움)힙 조건부모 노드 ≥ 자식 노드 (최대 힙), ≤ (최소 힙)저장 방식배열 인덱스 기반 표현 (root: index 0)사용 용도우선순위 큐, 정렬 알고리즘 (Heap Sort) 등2. 힙의 배열 표현노드 위치인덱스 관계부모 노드i왼쪽 자식2i + 1오른쪽 자식2i..

개요힙 정렬(Heap Sort)은 힙(Heap) 자료구조를 기반으로 하는 비교 기반 정렬 알고리즘이다. 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 이용해 최댓값(또는 최솟값)을 반복적으로 추출하고, 이를 배열의 끝에 삽입하는 방식으로 동작한다. **시간 복잡도가 항상 O(n log n)**으로 일정하며, **제자리 정렬(in-place)**이 가능하다는 장점이 있다.1. 개념 및 정의힙 정렬은 다음 두 단계로 이루어진다:배열을 힙 구조(완전 이진 트리)로 구성 (heapify)루트 노드(최댓값 또는 최솟값)를 추출한 뒤, 남은 요소로 힙 재구성 → 정렬 반복일반적으로 최대 힙을 사용해 오름차순 정렬을 수행한다.2. 동작 원리 단계 설명 1단계입력 배열을 최대 힙 구조로 변환2단계힙의 ..