[ 자료구조 ] 힙 (Heap)
Heap 이란? 우선순위큐를 위해 고안된 완전이진트리 형태의 자료구조, 여러값 중 최대/최소값을 빠르게 찾아내도록 만들어진 자료구조. ▶ 완전 이진트리 : 노드가 왼쪽부터 채워지는 형태 Heap의 종류 최소 힙 (min heap) : 부모노드 = 자식노드 데이터 삽입 최소 힙에 저장 - 삽입되는 값을 상위 부모노드와 비교하여 더 작을 경우 위로 swap 2. 최대힙에 저장 - 삽입되는 값을 상위 부모노드와 비교하여 더 클 경우 위로 swap 데이터 삭제 최소/최대힙의 가장 최상위 노드가 결국 최소값, 최대값이 되며, 힙 자료구조는 최소/최대값을 알아내는것이 목표임 따라서, 데이터를 삭제하면 최소/최대값이 삭제된다. 최대힙 삭제 예시 시간 복잡도 O(logN) 최악의 상황은 가장 root노드와 비교까지 할..
코딩테스트/[ 자료구조 ]
2024. 3. 16. 16:18
