우선순위 큐
큐와 달리 먼저 들어오는 데이터가 아닌, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조
배열, 연결리스트로도 구현할 수 있지만 일반적으로 힙(Heap)을 이용하여 구현
힙
최댓값, 최솟값을 찾아내는 연산을 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조 (파이썬의 heapq는 최소 힙을 기준으로 한다.)
힙 속성
-
부모 노드와 자식 노드의 값은 대소관계가 성립한다.
부모>자식 : 최대 힙
부모<자식 : 최소 힙 -
대소관계는 부모, 자식 노드 간에만 성립, 형제 노드끼리는 대소관계가 정해지지 않는다.
힙 구현
사진 출처: https://suyeon96.tistory.com/31
-
힙은 일반적으로 배열(리스트)를 이용하여 구현
-
자식 노드
왼쪽 자식노드 = (부모 노드)2
오른쪽 자식노드 = (부모 노드)2+1
-
부모 노드 = (자식노드)//2
※ 완전 이진 트리, 힙 정렬, 우선순위 큐의 데이터 삽입, 데이터 추출에 관한 내용은 이전에 정리한 사이트를 참조
↓↓↓↓↓↓↓↓↓↓
트리, 힙, 우선순위 큐
