[Algorithm] 힙(Heap)

TOC

• 힙(Heap)
  • 최대 힙(max heap)
  • 최소 힙(min heap)
  • 힙 연산1 : 삽입
  • 힙 연산2 : 삭제
• Heap 관련 라이브러리
  • heapq 모듈
  • heappop() 함수
  • heappush() 함수
  • heapify() 함수

힙(Heap)

완전 이진 트리에 있는 노드 중에서 key 값이 가장 큰 노드나 key 값이 가장 작은 노드를 찾기 위해서 만든 자료구조

최대 힙(max heap)

• 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
• 부모노드의 key값 > 자식노드의 key값
• 루트 노드 : key 값이 가장 큰 노드

최소 힙(min heap)

• 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
• 부모노드의 key값 < 자식노드의 key값
• 루트 노드 : key 값이 가장 작은 노드

힙 연산1 : 삽입

알고리즘

최대 힙에 값을 추가하고 배치를 바꾸는 알고리즘

'''
최대 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

힙 연산2 : 삭제

알고리즘

최대 힙에 루트인 최댓값을 반환하고 삭제해 재배치하는 알고리즘

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])

• deq()를 호출
• root 노드(최댓값) 반환
• 다음 최댓값은 tree[1]으로 이동

Heap 관련 라이브러리

heapq 모듈

• heap 관련 함수들을 가지는 모듈

heappop() 함수

• heappop(arr)
• heap arr의 val을 오름차순으로 pop해준다.

heappush() 함수

• heappush(arr, val)
• heap arr에 val을 추가해준다.

heapify() 함수

• heapify(arr)
• arr을 heap으로 바꿔준다.