Heap Sort

1년 전에 배웠던 자료구조 기억을 더듬어서...

구현한 코드

def print_heap(heap_array):
    ent = 1
    cnt = 0
    for i in range(1, heap_array[0] + 1):
        cnt += 1
        print(heap_array[i], end=" ")
        if cnt == ent:
            print()
            ent *= 2
            cnt = 0
    print("\n-------------")


def insert_maxheap(arr: list, n):
    if len(arr) == 0:
        arr.append(1)
        arr.append(n)
        return
    arr.append(n)
    idx = len(arr) - 1

    while n > arr[idx // 2]:

        if arr[idx] > arr[idx // 2]:
            arr[idx], arr[idx // 2] = arr[idx // 2], arr[idx]
            idx = idx // 2
        if idx < 2:
            break
    arr[0] += 1

def delete_max(arr):
    if arr[0] == 0:
        return None
    max = arr[1]

    arr[1] = arr[arr[0]]
    next_child = 2
    while next_child < arr[0]:
        if arr[next_child] > arr[next_child + 1] or next_child + 1 >= arr[0]:
            arr[next_child // 2], arr[next_child] = arr[next_child], arr[next_child//2]
        else:
            next_child += 1
            arr[next_child // 2], arr[next_child] = arr[next_child], arr[next_child//2]
        next_child *= 2

    arr[0] -= 1
    return max

문제 상당하다.

 

가장 큰 값이 루트로 가야하는데

왜 마지막에 4가 12보다 먼저 루트로 들어갔을까..?

이런 바보 같은 코드..

def delete_max(arr):
    if arr[0] == 0: #만약 트리가 비어있다면 None 반환
        return None

    max = arr[1] #return 할 루트(가장 숫자가 큰)값
    arr[1] = arr[arr[0]]

    next_child = 2
    while next_child < arr[0]:
        if next_child < arr[0] and arr[next_child] <= arr[next_child + 1]:
            next_child += 1
        if arr[next_child] > arr[next_child // 2]:
            arr[next_child // 2], arr[next_child] = arr[next_child], arr[next_child // 2]
        next_child *= 2

    arr[0] -= 1
    return max

이렇게 수정했다. 왜 부모가 더 크면 자식이랑 원소를 교체할 필요가 없다는 걸 안 넣어줬을까?

이제는 잘.. 돌아간다.