알고리즘

|힢정렬 개념 | 힢정렬 알고리즘| 힢정렬 분석 |

힢 정렬 개념

■ 힢 정렬 개념

힢(heap)은 우선순위 큐(priority queue)의 일종으로 우선순위가 높은 요소를 효율적으로 관리하는 자료구조

힢은 배열 또는 연결리스트를 이용한 나무구조로 구현

힢은 부가적 메모리를 필요로 하지 않으며 매우 빠른 성능을 갖음

입력 자료에 무관하게 고른 성능을 보임

힢은 n개의 레코드로 구성된 입력 파일을 하나의 최대 힢(max heap) 즉, 각 노드에 저장되어 있는 원소의 값이 서브노드에 저장되어 있는 원소의 값보다 큰 전이진 트리 구조로 만드는 것

레벨 l 에서 노드의 수가 2^l-1< n <2^l+1을 만족하여 레벨 l 상에서 모든 노드들은 가능하면 왼쪽의 위치에 존재하게 됨