힙 정렬 (Heap Sort)

이진 힙 (Binary Heap)

힙 조건(각 노드의 우선순위가 자식 노드의 우선 수위보다 높음)을 만족하는 완전 이진트리

최대 힙(Maximum Heap) : 가장 큰 값을 루트에 저장

최소 힙(minimum Heap) : 가장 작은 값을 루트에 저장

최대 힙 - 참고) 알기 쉬운 알고리즘

힙에서 부모와 자식 관계

A[i]의 왼쪽 자식 = A[2i]

A[i]의 오른쪽 자식 = A[2i+1]

A[i]의 부모 = A[i/2] (i가 홀수면 i/2에서 정수 부분만)

 

힙 정렬 (Heap Sort)

정렬할 입력으로 최대 힙을 만들어 가장 큰 수가 저장되어 있는 루트와 힙의 가장 마지막 노드를 교환(가장 큰 수를 배열의 맨 뒤로 옮김)

힙 크기를 1개 줄인 후 위배된 힙 조건을 해결하여 다시 힙 정렬 수행

 

---

루트 90과 힙의 마지막 노드 40을 바꾼 후, 힙 크기를 1개 줄임

참고) 알기 쉬운 알고리즘

 

 

위배된 힙 조건 해결(루트를 자식들 중 자기보다 큰 값을 가진 자식(둘 다 자기보다 크면 제일 숫자가 큰 자식과 교환)과 계속 교환하며 힙 조건을 만족할 때까지 아래쪽으로 내려감)

참고) 알기 쉬운 알고리즘

 

참고) 알기 쉬운 알고리즘

 

 

위배된 힙 조건 해결 완료

참고) 알기 쉬운 알고리즘

 

 

다시 루트 80과 힙의 마지막 노드 20을 바꾼 후, 힙 크기를 1개 줄이고 힙 위배 조건을 해결하며 힙에 하나의 숫자만 남을 때까지 힙 정렬 반복

참고) 알기 쉬운 알고리즘