[알고리즘] 힙 정렬 (Java)

힙 정렬 정렬 알고리즘의 한 종류인 힙 정렬입니다. 힙 정렬을 하기전에 먼저 힙에 대해 알아보겠습니다. 힙 이란? 힙은 완전 이진 트리에 가까운 형태입니다. 이진트리란 각 노드의 자식수가 2이하인 경우입니다. 완전 이진트리란 Root 노드부터 Leaf 노드까지 모두 값이 있는 형태입니다. 최대힙 루트 노드에 있는 키는 모든 자식 노드보다 가장 커야합니다. 각 노드의 자식 노드와의 관계도 마찬가지입니다. 최소힙 루트 노드에 있는 키는 모든 자식 노드보다 가장 작아야 합니다. 각 노드의 자식 노드와의 관계도 마찬가지입니다. 다음은 최대힙 구조입니다. 최대힙에 삽입시 데이터 변환 구조 입니다. 기존 힙에 65 노드를 추가 하였습니다. 65는 차례로 부모 노드와 비교하여 스왑합니다. 비교 스왑을 통하여 최종적으로 제일 상위 노드가 되었습니다. 최대힙에 삭제시 데이터 변환 구조 입니다. 최대힙에서 삭제시 최댓값인 60이 삭제됩니다. 제일 마지막 노드인 30이 최상위 루트 노드가 되고 다시 자...

원문링크 : [알고리즘] 힙 정렬 (Java)