우선순위 큐

우선순위 큐

데이터에 우선순위를 부여하여 추가하고 우선순위가 가장 높은 데이터를 꺼내는 방식

heap 모듈을 활용하여 수행..

Heap

-쌓아 놓은 더미라는 뜻

“부모의 값이 자식의 값보다 항상 크다.” → 루트 노드의 값 == 최대값

부모 = 자식 -1 // 2

왼 자식 = 부모 * 2 +1

오른 자식 = 부모 * 2 + 2

heappush(힙푸시)

heap = [5,4,2,1]
# 힙의 마지막에 새로운 값을 추가한다
heap.append(3)
cur = len(heap)-1
parent = 0
while parent >= 0:
    parent = cur//2
    
    if heap[cur] > heap[parent]:
        # 현재 위치를 부모노드로 변경
        heap[cur], heap[parent] = heap[parent], heap[cur]
        cur = parent
    else:
      break
      

heappop(힙팝)

heap = [3, 2, 1]

heap[0] = heap[-1]
heap.pop()
cur = 0

# 왼쪽 자식과 오른쪽 자식 노드 비교 -> 더 큰 자식 노드와 부모 노드 스위치
while cur < len(heap)//2:
    left = 2*cur
    right = left +1
    idx = cur
    if left < len(heap) and heap[left] > heap[cur]:
        print("left", cur, left)
        cur = left
    elif right < len(heap) and heap[right] > heap[cur]:
        print("right", cur, left)
        cur = right
    if idx != cur:
        heap[idx], heap[cur] = heap[cur], heap[idx]