힙 자료구조 - insert 연산

위의 트리는 힙이 맞다

1. 힙의 모양성질 만족

2. 모든 부모의 key가 자식의 key 보다 커야함

 

이러한 힙에서 만약 14가 들어오고자 하면,

새로 들어온 14 때문에 힙 성질을 만족하지 못한다. 따라서 이를 적절히 변경해줘야 함.

14를 위로 올려 보내면서 자기 자리를 찾도록 해야 한다.

 

def insert(14):
    A.append(14)
    A.heapify(9) # up
    # A[k]를 root 방향으로 이동하면서 heapify
    
def heapify(k): # A[k]를 heapify
    # 아직 루트에 도달하지 않았고, 부모의 key 값이 나보다 작을 때
    while k > 0 and A[(k-1)//2] < A[k] :
        A[k], A[(k-1)//2 = A[(k-1)//2], A[k]
        k = (k-1)//2

 

 

 

 

 

 

 

 

 

 

참조 - https://www.youtube.com/watch?v=gVRDc5NRjjw&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=23