Heap정렬

이진트리

모든 노드의 자식 노드가 2개 이하인 트리구조

완전이진트리

데이터가 루트 노드부터 시작해서 자식 노드가 왼쪽 자식 노드, 오른쪽 자식 녿로 차근차근 들어가는 구조의 이진 트리

힙(Heap)

• 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리
• 최대 힙과 최소 힙이 존재(그림:최대힙)
  
• 최대 힙은 '부모 노드'가 '자식 노드'보다 큰 힙
• 힙 정렬을 하기 위해서는 정해진 데이터를 힙 구조를 가지도록 만들어야 한다.

힙 생성 알고리즘

• 하나의 노드를 제외하고는 최대 힙이 구성되어 있는 상태라 가정시
• Heapify Algorithm을 하여 특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 행동을 한다.
• 위치를 바꾼 뒤에도 여전히 자식이 존재하는 경우 또 자식 중에서 다 큰 자식과 자신의 위치를 바꾸어야 한다.
  
  

힙 만들기

• 배열의 첫번째 항i를 1에서 시작해야 자식등 검색할 때 맞음
  EX) 70의 왼쪽 자식은 ix2 = 2x2이므로 4번쨰인 90이 됨
  오른쪽 자식은 ix2+1이다