반응형 HeapSort1 [자료구조] 힙 정렬(Heap Sort) 먼저, 힙이란 - 완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 이 힙을 사용하여 정렬하는 알고리즘이 힙 정렬이다. - 힙의 루트노드에 저장된 값이 가장 커야한다. - 힙의 루트 노드에 저장된 값이 정렬 순서상 가장 앞선다. - 마지막 노드의 값을 부모와 비교하여 자식 노드의 값이 우선순위가 더 높다면 부모노드와 자리를 바꾸는 방식으로 정렬을 진행한다. - 삽입 : 새로운 노드를 힙의 마지막 노드에 삽입한 후 부모 노드들과 비교하여 정렬한다. - 삭제 : 힙의 최대값인 루트노드가 삭제되고 마지막 노드가 루트노드로 옮겨진다. 이후 루트노드를 자식노드와 비교하며 정렬한다. - 시간 복잡도 : O(nlog2n) private void solve() { int[] array = { 230.. 2024. 1. 15. 이전 1 다음 반응형