Heap이란?
heap은 완전이진트리 기반의 자료구조이다. 다음 두가지로 나뉜다.
max heap: 자식 노드 C의 key 값이 부모 노드 P의 key값 보다 작거나 같아야 한다.
min heap: 자식 노드 C의 key 값이 부모 노드 P의 key값 보다 크거나 같아야 한다.
힙의 응용
반복적으로 우선순위에 있는 값들을 제거해야할 때 유용하다.
- 우선순위 큐
- 힙정렬
- 다익스트라
- prims 최소신장 트리
(1)우선순위 큐(Priority Queue, C++ STL)
(2)힙정렬(Heap sort)
'PS' 카테고리의 다른 글
| 백준 15649번 N과 M(1) C++ code (0) | 2020.04.27 |
|---|---|
| 자료구조 List (0) | 2020.04.22 |
| 자료구조 Graph (0) | 2020.04.21 |
| 자료구조 Trie (0) | 2020.04.20 |
| 자료구조 Tree (0) | 2020.04.20 |
