[자료구조] heap sort 힙소트 프로그램

목차

힙정렬 정의
알고리즘
소스코드// 주석 포합
소스 분석
실행후 걸리는 시간분석
효율적임을 입증
입력 데이터값 출력
결론

본문내용

힙은 우선순위 큐의 일종으로 우선순위가 높은 요소를 효율적으로 선택할 수 있는 자료 구 조입니다. 저는 힙을 나무구조로 구현했으며 배열을 이용하여 구현했습니다.
힙 정렬은 부가적인 메모리가 전혀 필요 없으면서도 O(NlogN)의 성능을 가지는 매우 빠른 정렬 법이며 입력자료에도 거의 무관하고 고른 성능을 보여주는 뛰어나 알고리즘입니다.
힙의 우선순위는 킷값의 크기에 의해 정해지는 자료구조이며 힙은 어떤 키가 다른 특정한 두 키보다 큰 키 값을 가져야 한다는 조건을 만족한다 그래서 힙은 나무구조와 자연스럽게 연결된다 나무 구조에서 키는 두 자식의 키 값보다 크게 만들어 주면 자연스럽게 힙의 구조가 된다. 다음 아래의 힙에 Z라는 자료를 삽입할 때 Z는 힙의 최 말단에 추가된다 하지만 이는 힙의 규칙을 위배하는 것이다. 왜냐하면 Z의 부모인 M은 Z보다 작은 값이기 때문이다. 그래서 Z는 위로 상승하게 되어 M과 자리를 바꾼다. 이제는 R이 Z의 부모가 되는데 역시 힙의 규칙에 어긋난다. 그래서 R과 Z를 바꾸어 Z는 한 칸 또 위로 올라간다. 이제 Z의 부모는 T이며 역시 T는 Z보다 작으므로 자리를 바꾼다. 결국 Z는 뿌리의 자리를 차지하며 이것은 Z는 모든 힙의 값 중에서 최대 값이기 때문입니다.

참고자료

· 없음