[알고리즘] 정렬 - 힙 정렬, O(NlogN)
24.03.20 수정 - 처음에 데이터 전체를 힙 구조로 만드는 과정이 O(NlogN)이라고 상한을 과하게 잡아서 작성했는데, 실제로는 Θ(N)의 시간 안에 해결된다. 증명과정을 추가하여 작성했다. 힙 정렬은 힙(Heap)이라는 자료구조를 이용해 정렬하는 방식이므로 우선 힙에 대해 이해할 필요가 있다. 다음은 Heap의 조건이다. Heap이란? 1. 완전 이진 트리이다. 모든 경로의 가장 아래층을 제외하고는 모두 채워져있다. 2. 왼쪽부터 노드가 채워진다. 3. 부모 노드의 값이 자식 노드의 값보다 항상 작다(크다). Heap은 3번 조건에 따라 MaxHeap와 MinHeap으로 나뉜다. 부모 노드의 값이 자식 노드의 값보다 작으면 MinHeap, 크면 MaxHeap이다. 보통 MaxHeap을 사용하는 ..
알고리즘
2024. 3. 17. 11:09
