[python] 백준 2750번 수 정렬하기1 : 힙정렬(heap sort)

문제)

2750번: 수 정렬하기

 

알고리즘) 

[알고리즘] 힙 정렬 ( Heap Sort )

 

힙정렬은 힙트리를 이용한 정렬이다. 힙트리는 두 가지 조건이 충족되어야 한다. 

 

1) 완전이진트리여야 한다.

2) 부모는 반드시 자식보다 커야 한다. ( 부모는 반드시 자식보다 작아야 한다.)

 

고로, 루트(index가 0인 자리)에는 최댓값 혹은 최솟값이 온다. 

 

힙트리를 이용한 힙정렬은 아래와 같다.

 

1) 입력받은 수열을 힙트리로 생성한다. ( 힙트리 생성 )

2) 루트의값과 가장 마지막 인덱스 값을 서로 swap 한다. 

3) 마지막 인덱스에 최대값이 온다. 마지막 인덱스를 pop(제거)하여 새로운 정렬리스트에 추가(append)한다.

4) swap으로 인해, 루트자리에 최대값이 사라져 힙트리가 깨졌으므로 다시 힙트리를 생성한다.

5) 루트와 마지막 인덱스를 서로 swap 하고 마지막 인덳를 제거하여 정렬리스트에 추가한다. 

 

위 과정을 반복하면 최댓값을 이용하여 값이 큰 순서대로 하나씩 정렬리스트에 추가된다. 힙트리는 매정렬마다 n개를 n번 비교하는 것이 아니라 트리의 특성을 활용하여 부모를 기준으로 비교하므로 nlogn의 성능을 가진다. 

 

코드)

import sys
sys.setrecursionlimit(10**6)

n = int(input())

input_list = []
for i in range(n) :
  input_list.append(int(input()))

#힙정렬함수
def heap_sort(unsorted) :

  #힙트리 생성하기
  last_child_index = len(unsorted)-1 # 힙트리의 마지막 자식 인덱스
  last_parent_index = (last_child_index - 1)//2 # 힙트리의 마지막 부모 인덱스
  for i in range(last_parent_index,-1,-1) : # 모든 부모인덱스를 돌며 힙트리 생성, 밑(마지막부모인덱스)에서부터 생성되어야 root 자리에 최대값이 올라온다.
    doheap(unsorted, i)

  #힙정렬하기
  sorted = []
  for i in range(last_child_index,-1,-1) :
   unsorted[0], unsorted[i] = unsorted[i], unsorted[0] #root와 끝자리 swap
   sorted.append(unsorted.pop(i)) # 이미 정렬된 끝자리 제거하기
   if i != 0 : doheap(unsorted,0) # swap으로 인해, 힙트리가 깨졌으므로 다시 힙트리 생성

  return sorted

#힙트리는 완전이진트리이며 부모가 자식보다 크다. 그러므로 부모를 기준으로 해당 조건을 맞춘다.
def doheap(unsorted, pivotIndex) : 
  pivot = unsorted[pivotIndex] # 힙트리 생성의 기준값
  pointer = pivotIndex # 힙트리 생성의 기준인덱스
  
  while pointer <= ((len(unsorted)-1)-1)//2 :
    # 자식 left와 자식 right 중 큰 값을 child로 지정 (완전이진트리)
    left = 2*pointer+1
    right = left+1
    child = left
    if right < len(unsorted) and unsorted[right] > unsorted[left]  : child = right

    #비교하기
    if pivot > unsorted[child] : break; # 부모가 자식보다 크므로 반복문 종료
    else : #자식이 부모보다 큰 경우
      unsorted[pointer] = unsorted[child] # 부모자리에 자식이 올라가고 쟈식자리에는 부모였던 값이 내려온다.
      pointer = child # 자식인덱스에 부모였던 값이 내려왔으므로, 자식의 자식과 다시 비교해야한다.

  unsorted[pointer] = pivot #반복문이 종료되면 기준인덱스에 기준값을 넣는다. 

#출력
result = heap_sort(input_list) #힙정렬 호출
for i in range(n-1,-1,-1) : #오름차순 출력
  print(result[i])