[힙] 2220번 힙 정렬

1. 문제

2. 나의 풀이

• index가 1부터 시작하는 이진 트리

n = int(input())
heap = [0, 1]


def swap(arr, x, y):
    arr[x], arr[y] = arr[y], arr[x]


for i in range(2, n + 1):
    heap.append(i)  # 맨 뒤에 최댓값 추가
    print(i, heap)
    swap(heap, i, i - 1)  # 마지막이랑 마지막 전이랑 교체

    j = i - 1  # j위치에 있는 최댓값
    while j != 1:
        swap(heap, j, j // 2)
        j = j // 2  # 부모 노드의 위치

print(' '.join(str(x) for x in heap[1:]))

3. 남의 풀이

• https://claude-u.tistory.com/342

n = int(input())
heap = [0, 1]

def swap(arr, x, y): #두 위치를 바꾸는 코드
    temp = arr[x]
    arr[x] = arr[y]
    arr[y] = temp
 
for i in range(2, n+1):
    heap.append(i) #맨 뒤에 최댓값 추가
    swap(heap, i, i-1) #1과 바꿔줌
    j = i-1 #j위치에 있는 최댓값
    while j != 1: #j위치에 있는 최댓값은 최상단에 위치할 때 까지 부모 노드와 지속적으로 바꾸어줌
        swap(heap, j, j//2) #교환
        j = j//2 #부모 노드의 위치

for i in heap[1:]:
    print(i, end = ' ')

4. 느낀 점