[Python] Tree3 - heap

• heap
  • 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조
  • 최대 힙(max heap)
    • 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
    • 부모 노드의 키 값 > 자식 노드의 키 값
  • 최소 힙(min heap)
    • 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
    • 부모 노드의 키 값 < 자식 노드의 키 값

 

• 힙 연산 - 삽입
  • 완전 이진 트리를 유지 하기 위해 마지막 노드 다음에 추가
  • 최대 힙 or 최소 힙에 따라 위치 조정

# 최대 힙 삽입
def enq(n):
	# 마지막 정점 번호
    global last
    # 완전이진트리 유지
    last += 1
    tree[last] = n
    
    # 위치 조정
    # 새로 추가된 정점을 자식으로
    c = last 
    p = c//2
    
    # 부모가 있고, 자식의 키 값이 더 크면 교환(최대 힙은 부모가 더 커야 함)
    while p>=1 and tree[p] < tree[c]: 
        tree[p], tree[c] = tree[c],tree[p]
        # 부모를 자식으로 하여 확인 반복
        c = p
        p = c//2

enq(3)
enq(2)
enq(4)
enq(7)
enq(5)
enq(1)
enq(9)

print(tree)
# 결과
# [0, 9, 5, 7, 2, 4, 1, 3, 0, 0]

 

• 힙 연산 - 삭제
  • 루트 노드의 원소만을 삭제 가능
  • 마지막 노드를 루트 노드 위치에 올리고
  • 최대힙 or 최소힙에 따라 위치 조정

# 최대 힙 삭제
def deq():
	# 마지막 정점 번호
    global last
    # 루트의 key 값
    tmp = tree[1] 
    
    # 마지막 정점의 키를 루트에 복사
    tree[1] = tree[last] 
    # 마지막 정점 삭제
    last -= 1
    
    # 위치 조정
    # 부모 > 자식 규칙 유지
    p = 1
    # 왼쪽자식노드 번호
    c = p*2
    
     # 왼쪽자식이 존재하는가? : 존재하지 않으면 자식 없음(왼쪽부터 자식 둠, 완전 이진 트리)
    while c <= last:
    	# 오른쪽 자식노드도 있고 더 크면
        if c+1 <= last and tree[c] < tree[c+1]: 
        	#오른쪽 자식 선택
            c += 1 
            
        # 자식의 키 값이 더 크면 교환
        if tree[p] < tree[c]: 
            tree[p],tree[c] = tree[c],tree[p]
            # 부모를 자식으로 두어 확인 반복
            p = c
            c = p*2
        else:
            break
            
    return tmp