[ALgorithm] Heap Sort | by university class

학교에서 배운 힙소트 정리 코드 아카이브 용.

이론을 안다는 전제하에 코드만 읽는다.

def heapify(arr,n,i):
  key = i
  l = key*2+1
  r = key*2+2

  # 왼쪽 자식 노드 검사
  if l <= n and arr[l]>arr[key]:
    largest = l
  else:
    largest = key

  # 오른쪽 자식 노드 검사
  if r <= n and arr[r] > arr[largest]:
    largest = r

  # 바뀐 게 있다면 자식 노드와 값을 바꾸고 해당 자식 노드를 검사
  if largest != key:
    temp = arr[largest]
    arr[largest] = arr[key]
    arr[key] = temp
    heapify(arr,n,largest)

# 절반부터 하는 이유는 절반보다 위에 노드는 리프 노드이기 때문
def bulid_max_heap(arr,n):
  for i in range((n-1)//2,-1,-1):
    heapify(arr,n,i)

def heapsort(arr,n):
  bulid_max_heap(arr,n)

  # 루트 노드와 맨 마지막 노드와 바꾼다.
  # 루트 노드는 가장 큰 값이 빌드되었으므로
  for i in range(n,0,-1):

    temp=arr[i]
    arr[i]=arr[0]
    arr[0]=temp

    # 마지막 제일 큰 값이 들어가고 트리에서 제거해준다.
    # (배열에는 저장되므로 오름차순 정렬이 형성 됌.)
    n=n-1
    # 루트 노드에 작은 값으로 대치되었으므로 다시 heapify를 해줘야 한다.
    heapify(arr,n,0)

arr = [5,2,7,6,0,8,3,4,9,1]
size = len(arr)-1
heapsort(arr,size)

print("result:",arr)

result: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]