heap
-
[Data Structure] HeapCS/Data Structure 2021. 10. 7. 13:20
이 포스팅은 세미나를 위해 https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure를 참고하여 작성하였습니다. Heap 완전 이진 트리(Complete Binary Tree) 기반 자료구조로 반정렬 상태(느슨한 정렬 상태)를 유지한다. 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리 형제 또는 사촌 노드 간의 우선순위는 정해진 것이 없음 힙은 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않음) 종류 최대 힙(Max Heap) key(부모 노드) ≥ key(자식 노드) 최소 힙(Min Heap) key(부모 노드) ≤ key(자식 노드) 시간 복잡도 Max(Mi..