Heap sort 썸네일형 리스트형 Heap Sort (이진) 힙 자료 구조는 완전 이진 트리로 볼 수 있는 배열 객체다. 트리의 각 노드는 배열에서 그 노드의 값을 저장하는 원소와 대응한다. 이 트리는 가장 낮은 층을 빼고는 완전히 차 있고, 가장 낮은 층은 왼쪽부터 채운다. 힙을 나타내는 배열 A는 두 가지 인자를 갖는다. 배열 A에 있는 원소의 개수를 나타내는 length[A]와 배열 A의 원소 중 힙에 속하는 원소의 개수를 나타내는 heap-size[A]다. 그리고 heap-size[A] ≤ length[A]다. 다시 말해서 A[1..length[A]]에 있는 값들이 다 유용할 수는 있지만, A[heap-size[A]] 뒤에 있는 것들은 힙의 원소가 아니다. 트리의 루트는 A[1]이다. 그리고 노드의 인덱스 i가 주어지면 부모 Parent(i), 왼.. 더보기 이전 1 다음