heap 이란?
- 최댓값이나 최솟값을 빠르게 찾아내도록 고안된 완전이진트리를 기본으로 한 자료구조
- 우선순위 큐를 위해 만들어진 자료구조
heap 의 종류
Min heap (최소힙)
작은 값을 항상 트리의 위에 있게 해서 트리의 루트에는 가장 작은 값이 오도록 한다.
Max heap (최대힙)
가장 큰 값이 루트에 오도록 한다. 모든 노드는 자기 부모 노드가 자기보다 큰 값을 가지고 있다.
heap의 구현
- 힙을 저장하는 표준적인 자료구조는 '배열'이다.
- 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
heap의 삽입
- 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
- 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.
*메모리 구조 참고용
참고
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html