우선순위 큐(Priority Queue), 힙(Heap)

◎우선순위 큐(Priority Queue)

스택(Stack) : LIFO - 마지막에 들어간 요소가 가장 먼저 나온다

큐(Queue) : FIFO - 처음 들어간 요소가 가장 먼저 나온다

↑ 스택과 큐가 위와 같은 특징이 있다면

    우선순위 큐(Priority Queue)는 입력 순서와 상관 없이 가장 우선순위가 높은 데이터가 가장 먼저 나오게 된다.

---

◎힙(Heap)

<시간복잡도>

삽입 : O(logn)

삭제 : O(logn)

 

<형태>

완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조

*완전 이진트리 : 노트 1개당 자식노드 2개를 유지하는 형태

최대 힙 : 부모 노드 값 >= 자식 노드 값

최소 힙 : 부모 노드 값 <= 자식 노드 값

 

부모노드 인덱스 = 자식노드 인덱스 / 2

왼쪽 자식노드 인덱스 = 부모노드 인덱스 * 2

오른쪽 자식노드 인덱스 = 부모노드 인덱스 * 2 + 1

 

<Python 코딩> :

import heapq

heapq.heapify( 리스트 )  < 리스트를 힙구조로 변환

heapq.heappush( 리스트, 값) < 값 추가 (힙구조로 재 변환)

heapq.heappop(리스트)   < 최소값 추출 및 삭제 (힙구조로 재 변환)