[자료구조] Heap과 Heap Sorting

소개글

자료 구조중 heap (max heap, min heap)에 대한 설명과 heap sorting에 관한 설명 및 C++의 구현 소스

목차

없음

본문내용

Heap(힙)의 정의
Max Heap : max heap은 complete binary tree + max tree 로 정의한다(Figure 2). 그러면 complete binary tree와 max tree는 무엇인가? Complete binary tree는 tree의 마지막 depth까지 binary tree이며 마지막 depth의 leaf node들은 맨 왼쪽부터 차례로 인접하여 구성되는 2진 트리의 한 종류이다(Figure1). 그리고 max tree는 각 node의 값이 children node의 값보다 더 작지 않는 tree이다.

Min Heap : min heap은 max heap과 min tree로 정의된다는 점만 다르다(Figure 3). Min tree는 쉽게 추측할 수 있듯이 각 node의 값이 children node의 값보다 더 크지 않은 tree이다.

<중 략>

Heap Sort
Heap의 정의와 기능을 보면 쉽게 Sorting이 가능함을 예상할 수 있다. Max heap은 root node에 항상 가장 큰 값을 가지고 있으므로 Max heap에 대해서 삭제를 계속하면 내림차순으로 정렬되며, Min Heap은 오름차순으로 정렬됨을 알 수 있다. 그리고 삭제 알고리즘의 과정3에서 root에서 child의 path를 따라 비교하므로 걸리는 시간은 logn 임을 알 수 있다(여기서 n은 item의 수). 따라서 정렬을 위해서 삭제를 n번 해야하므로 이 정렬에 걸리는 시간은 n logn 이다.

참고 자료

없음

압축파일 내 파일목록

Heap.cpp
Heap.docx
Heap.h