힙 정렬1 [알고리즘] [1] 힙 정렬 1. 힙 우선순위 큐(Priority Queue)를 위하여 만들어진 자료구조로, 완전이진트리를 사용하므로 빈 요소가 없어 배열로 구현한다. 2. 힙 정렬 힙 정렬이란 최대 힙 트리 또는 최소 힙 트리를 구성하여 정렬하는 방식이다. 최소 힙 알고리즘 1. n개의 노드에 대한 완전이진트리를 구성한다. Parent, LeftChild, RightChild로 구성된다. 완전이진트리이기 때문에 어떤 한 노드에 대한 Parent, LeftChild, RightChild의 Index를 구할 수 있다. 2. 부모 노드가 자식 노드보다 작은 최소 힙을 구성한다. 3. 루트 노드와 가장 아래의 노드와 교환하고, 교환된 가장 아래의 노드를 제외한 나머지에 대해 최소 힙을 구성한다. 4. 2와 3을 반복하여 오름차순으로 정렬.. 2023. 12. 4. 이전 1 다음
