[Algorithm]Priority Queue우선순위 큐 & Heap힙

🟠 Priority Queue우선순위 큐 & Heap힙

Heap이란?

• 완전 이진트리를 기본으로 한 자료구조(최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된)
• 부모 - 자식 노드의 대소 관계 성립
  
  
  
  
  
  
  

Heap 함수 활용하기

• heapq.heappush(heap, item) : item을 heap에 추가
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨.
• heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )

힙 생성 & 원소 추가

import heapq

heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)

print(heap)

이미 생성해둔 리스트가 있다면

• heapify 함수를 통해 즉각적으로 힙 자료형으로 변환할 수 있다.

heap2 = [50 ,10, 20]
heapq.heapify(heap2)

print(heap2)

힙에서 원소 삭제

• heappop 함수는 가장 작은 원소를 힙에서 제거함과 동시에 그를 결괏값으로 리턴한다.

result = heapq.heappop(heap)

print(result)
print(heap)

원소를 삭제하지 않고 가장 작은 원소 가져오고 싶으면

• [0] 인덱싱을 통해 접근하면 된다.

result2 = heap[0]

print(result2)
print(heap)

우선순위 큐 라이브러리를 활용한 힙 정렬 구현 예제

def solution(k, scores):
    from heapq import heappushpop, heappush

    answer = []
    hq = []
    for idx, score in enumerate(scores):
        if idx >= k:
            heappushpop(hq, score)
        else:
            heappush(hq, score)

        answer.append(hq[0])
    return answer