Heap

힙

: 완전 이진 트리로 구현된 자료구조. 키 값이 가장 큰 노드나 가장 작은 노드를 찾을 때 사용

 

max heap

: 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리

(부모노드의 키 값 > 자식노드의 키 값)

루트노드 -> 키 값이 가장 큰 노드

 

min heap

: 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리

(부모노드의 키 값 < 자식노드의 키 값)

루트노드 -> 키 값이 가장 작은 노드

 

 

힙 연산 - 삭제

>> 힙에서는 루트 노드의 원소만을 삭제할 수 있다.

1. 루트 노드의 원소 삭제

2. 마지막 노드 삭제

3. 자리 바꾸기 ( 최대힙 상태 유지)

 

 

연산을 수행할 때마다 힙 상태를 유지해야 한다.

# 최대힙

# 힙 연산 - 삽입
def enq(n):
    global last
    last += 1  # 마지막 정점 추가
    heap[last] = n   # 마지막 정점에 key 추가

    c = last  # 자식노드
    p = c//2  # 부모노드
    # 부모가 있고, 부모 < 자식 인 경우 자리교환
    while p and heap[p] < heap[c]:
        heap[p], heap[c] = heap[c], heap[p]
        # 새로운 부모, 자식 노드
        c = p
        p = c//2

# 힙 연산 - 삭제
def deq():
    global last
    tmp = heap[1]   # 루트 백업
    heap[1] = heap[last]     # 삭제할 노드의 키를 루트에 복사
    last -= 1    # 마지막 노드 삭제

    p = 1    # 루트에 옮긴 값을 자식과 비교
    c = p * 2  # 왼쪽 자식
    while c <= last:     # 자식이 하나라도 있으면
        if c+1 <= last and heap[c] < heap[c+1]:   # 오른쪽 자식도 있고, 오른쪽 자식이 더 크면
            c += 1      # 비교 대상을 오른쪽 자식으로 정함
        if heap[p] < heap[c]:      # 자식이 더 크면 최대힙 규칙에 어긋나므로
            heap[p], heap[c] = heap[c], heap[p]
            p = c                  # 자식을 새로운 부모로
            c = p * 2              # 새로운 부모의 왼쪽 자식
        else:                      # 부모가 더 크면
            break                  # 비교 중단,

    return tmp


heap = [0] * 100
# 마지막 리프노드의 인덱스
last = 0

enq(2)
enq(5)
enq(7)
enq(3)
enq(4)
enq(6)

# 힙 정렬, 내림차순으로 프린트 된다.
while last:
    print(deq())

 

 

 

 

나빼고 전부 파워 N 들로 구성되었던 작년 겨울 제주도 여행.

구름을 가리키며 "유나, 구름 위에서 어떻게 놀건지 상상해본적 있어?" 라는 질문에

"아니. 발 내딛자마자 땅으로 곤두박질 칠 것 같아서 안해봤어" 라고 답해서 대화가 급히 마무리 되었던,,ㅎ