힙 정렬(Heap Sort)

Algorithmday_4 정리 (2021.12.01 수요일)

힙 정렬 (Heap Sort)

• 정렬할 원소를 힙(heap)이라는 자료 구조를 이용하여 정렬하는 방법
• 힙 구조
  • 완전 이진 트리로, 각 노드의 키 값이 자식 노드들의 키 값보다 작지 않은 트리 로서 힙 루트는 트리 중 가장 큰 값 을 나타냄
• 힙 정렬 방법
  • 주어진 데이터로 이진 트리를 구성한 후 힙 구조 알고리즘과 힙 정렬 알고리즘을 수행
• 힙 구조 알고리즘
• 제일 늦게 구성된 트리 선택
  • 부모 노드와 자식 노드 중 가장 큰 값 선택
  • 부모 노드와 자식 노드 중 가장 큰 값을 비교하여 자식 노드가 크면 서로 위치 교환 (큰 값을 위로 보냄)

• 힙 정렬 알고리즘
  • 근 노드의 값을 배열의 맨 마지막에 저장 (근 노드 삭제에 해당)
  • 빈 근 노드의 자리에선 자식 노드 가장 가장 큰 값 위치
  • 빈 자식 노드의 자리에는 서브 트리의 자식 노드 중 맨 마지막 노드 값으로 채움
  • 맨 마지막 노드부터 차례로 제거됨

• 힙의 노드들이 배열에 저장된 모습

• 원래 힙의 마지막 노드 40과 루트 90을 바꿈

• 힙 조건 위배 검사 후 조건에 위배 됐기 때문에 조건에 따라 노드를 움직여준다.

• 또 힙 조건에 위배 됐기 때문에 노드 위치를 조정 후 조건을 만족했기 때문에 확정 후 제일 마지막 노드 확정

• 80과 20이 교환된 후 힙 조건을 만족한 결과

• 70과 10이 교환된 후 힙 조건을 만족한 결과

• 위 과정 반복하고 마지막 결과