Heap sort

def Sort(A):
  for i in range(n-1,-1,-1):
    m, idx = get_max(A,i) # m최댓값, idx인덱스 리턴
    A[idx],A[i] = A[i],A[idx]
   

selection

• get_max를 for문을 돌려 O(n^2)이 걸린다

heap sort

• O(nlogn)
  

• A[2]의 왼쪽자식노드: A[5] -> A[2x2+1]=A[5]

• A[2]의 오른쪽자식노드: A[6] -> A[2x2+2] =A[6]

• 부모노드는 A[(k-1)/2] A[(k-2)/2]로 알 수 있다
  상수시간O(1) 내에 자식과 부모 노드를 알 수 있다

heap성질

1. 모양성질: 이진트리
2. 힙성질: 부모노드 Key값 >= 자식노드의 Key값

• 2번 성질에 맞게 스왑을 해줘야하는데 스왑은 상수시간으로 할 수 있다.

• 높이는 logn <- 하나의 부모노드에 두개의 자식이 붙어 있으니 2^n씩 늘어난다

Make Heap

0. makeHeap(A)
1. root node: 최댓값
2. for (n-1)번: A[0]와 A[n-1]과 교환
3. heapifydown으로 A[0]의 값이 최댓값이 되도록 한다
   n=n-1