목록O(n*lgn) (1)

코린이의 소소한 공부노트

Heap sort

1. Problem - 힙을 이용해 배열의 값을 오름차순으로 정렬해보자. // 완전 이진 트리(complete binary tree): 자식 노드가 왼쪽부터 채워지는 이진 트리. 같은 레벨의 중간 부분이 비어있지 않다. // 힙: 최댓값/최솟값을 빠르게 찾기 위해 완전 이진 트리를 기반으로 만들어진 트리 // 최대 힙: 부모 노드가 자식 노드보다 큰 값을 갖는 힙 // 힙 생성(heapify) 알고리즘: 특정 노드를 최대 힙에 넣는 알고리즘. 특정 노드의 두 자식 중 더 큰 자식과 자기 자신의 위치를 바꾸면서 자리를 찾아 간다. 2. Input 1) int[] heap 3. Output 1) heap을 오름차순으로 정렬한 결과 4. Example // 위쪽 그림에서의 최대 힙: 6 5 2 4 1 // 6..
Back-End/Algorithm 2023. 5. 24. 14:13
이전 Prev 1 Next 다음