자료구조 1 Page 노트 정리_Heap 힙

heap 힙

- 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안됨

- 이진 트리(binary tree)를 기본으로 한 자료구조

- A가 B의 부모노드(parent node)이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립

- 키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립 (형제사이X)

- max heap 최대 힙: 부모노드 키값이 자식노드 키값보다 항상 크거나 같은 힙

- min heap 최소 힙: 부모노드 키값이 자식노드 키값보다 항상 작은 힙

- 주요동작: insert, delete, peek

- 활용 사례: 프로세스 스케줄링, 힙 정렬

priority queue 우선순위 큐

- 큐와 유사하지만 우선순위가 높은 아이템이 먼저 처리됨

- ADT인 priority queue를 구현한 대표적인 data structure가 heap