[백준] 2751번 : 수 정렬하기 2 in python 파이썬 :: heap sort

파이썬으로 백준풀기 :: 2751번 수 정렬하기 2 :: 힙 정렬

https://www.acmicpc.net/problem/2751

---

merge sort로 풀었던 것에 이어 heap sort로 풀어보았다.

>> [백준] 2751번 python with merge sort 바로가기 : https://leedakyeong.tistory.com/entry/%EB%B0%B1%EC%A4%80-2751%EB%B2%88-%EC%88%98-%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B0-2-in-python-%ED%8C%8C%EC%9D%B4%EC%8D%AC?category=842565

주의할 점은 같은 코드라도 python3으로 제출하면 시간초과가 나기때문에 pypy3으로 제출해야한다.

코드

v = [int(input()) for i in range(int(input()))] # 입력
 
def heapify(li, idx, n):
    l = idx * 2;
    r = idx * 2 + 1
    s_idx = idx
    if (l <= n and li[s_idx] > li[l]):
        s_idx = l
    if (r <= n and li[s_idx] > li[r]):
        s_idx = r
    if s_idx != idx:
        li[idx], li[s_idx] = li[s_idx], li[idx]
        return heapify(li, s_idx, n)
 
def heap_sort(v) :
    n = len(v)
    v = [0]+v
 
    # min heap 생성
    for i in range(n, 0, -1) :
        heapify(v, i, n)
 
    # min element extract & heap
    for i in range(n, 0, -1) :
        print(v[1])
        v[i], v[1] = v[1], v[i]
        heapify(v, 1, i-1)
 
heap_sort(v)