HEAP DEFINITION
완전 이진 트리(complete binary tree) 형태의 자료구조
힙은 부모와 자식 노드 간의 대소 관계를 만족해야 한다
최대 힙(Max-Heap): 부모 노드의 값 ≥ 자식 노드의 값
(루트에 최댓값이 위치)
최소 힙(Min-Heap): 부모 노드의 값 ≤ 자식 노드의 값
(루트에 최솟값이 위치)
또다른 특징으로는 배열로 구현하기 편하다는 특징이 있다
왼쪽 자식: 2i
오른쪽 자식: 2i+1
부모: i/2
HEAP SORT
1. 알고리즘 아이디어
배열을 최대 힙(Max-Heap) 으로 변환한다. (Build Heap)
루트(최댓값)를 배열의 끝과 교환한다.
힙의 크기를 줄이고 다시 힙 성질을 만족시키도록 Heapify 수행.
위 과정을 반복하여 정렬 완료.
2. 의사코드
HEAPSORT(A)
1 BUILD-MAX-HEAP(A)
2 for i <- length[A] downto 2
3 swap A[1] <-> A[i]
4 heap_size <- heap_size - 1
5 MAX-HEAPIFY(A, 1)BUILD-MAX-HEAP(A) : 배열 전체를 힙 구조로 만드는 과정: O(n)
MAX-HEAPIFY(A, i) : 노드 i를 루트로 하는 서브트리를 힙 조건 만족하도록 재구성: O(log n)
max_heap(root가 최대값인 힙)으로 만들고 최댓값인 a[1]을 제일 끝에 있는 원소인 A[i]와 바꾼다
그후 힙의 사이즈를 -=1 을 한다
재귀 반복하면 오름차순으로 정렬이 완료됌
시간복잡도:O(nlgn)
Build-Max-Heap : O(n) -> 실행횟수 T(n) = n/2 = 부모노드 기준
Heapify : O(log n) -> 실행횟수 T(n) = logn -1 = 레벨수 -1
HeapSort 전체 : O(n log n)
(모든 원소에 대해 Heapify 수행)
특징
✅ 항상 O(n log n) 보장
✅ In-place 정렬 (추가 메모리 불필요)
❌ 안정 정렬(Stable Sort)이 아님
