[Algorithm] 힙(Heap)

'''
최대 100개의 정수
최대 heap
'''
 
def enq(n):
    global last
    last += 1         # 마지막 정점 인덱스 증가
    tree[last] = n    # 완전이진트리 유지를 위해 last 인덱스에 값 추가(정점 추가)
    c = last          # 새로 추가된 정점을 자식으로
    p = c//2          # 완전이진트리에서의 부모 정점 번호
 
 
    while p > 0 and tree[p] < tree[c]:   # 부모 노드가 있고 자식의 키 값이 더 크면 교환
        tree[p], tree[c] = tree[c], tree[p]   # 값을 교환
        c = p                                 # 원래 부모였던 키값을 자식 키값으로 두기 위해 c에 저장
        p = c//2                              # 이 자식 키값으로부터 부모 키값 계산해 p에 저장 -> 위의 부모자식 확인
 
 
# 포화 이진트리의 정점번호 1~100
tree = [0] * 101
last = 0
enq(3)
enq(2)
enq(4)
enq(7)
enq(5)
enq(1)
print(tree[1])  # 1번 노드의 값(최댓값)을 출력
복사

7
복사

def deq():
    global last
    
    ret = tree[1]          # 1. root의 값을 ret에 저장, 이게 반환값
    tree[1] = tree[last]   # 2. 마지막 정점의 key 값을 root에 복사
    last -= 1              # 3. 마지막 정점 인덱스 감소 : 즉 마지막 정점 삭제 처리
    
    # 부모 > 자식 규칙 유지
    p, c = 1, 2              # 최초 루트를 부모로 하고, 왼쪽 자식 조회
    
    while c <= last:       # 왼쪽 자식이 있으면 오른쪽 자식까지 고려해서 큰 자식이랑 계속 교환
        # 1. 오른쪽 자식이 있고, 오른쪽 자식이 더 크면
        if c+1<=last and tree[c] < tree[c+1]:
            c += 1      # 오른쪽 자식 선택
 
        # 2. 자식의 값이 더 크면 교환
        if tree[p] < tree[c]:
            # 값 교환
            tree[p], tree[c] = tree[c], tree[p]
        
            p = c              # 부모 노드였던 것이 자식으로 내려오고,
            c = p * 2          # 새 자식 노드 키 계산해서 또 확인 반복
        
        # 3. 부모의 값이 더 큰 경우 탈출
        else:
            break
    
    # pop했던 최대값 반환 -> 삭제 이후 루트에는 최댓값이 다시 배치
    return ret
 
 
while last > 0:
    print(deq(), tree[1])
복사