Heap 기초1 Data Structure - Heap(1) 1. Heap이란? - Heap은 트리구조를 기반으로한 자료구조로 데이터에서 최대값과 최소값을 빠르게 찾기위해 고안된 완전 이진트리(Complete Binary Tree)이다. * 완전이진트리란? → 트리에 데이터가 삽입될 때, 왼쪽에 위치한 자식노드를 먼저 채우는 규칙을 갖고 있는 이진트리이다. 이진트리이기 때문에 자식노드는 2개만 가질 수 있다. 1) Heap을 사용하는 이유 - 우선순위 큐와 같이 최대값과 최소값을 빠르게 찾기위해 사용한다. - 이를 배열로 구현하면 최대값과 최소값을 찾는데 O(n)만큼 걸린다. - 반면에, heap을 이용하여 최대값과 최소값을 찾으면 O(log n)만큼 걸린다. (더 빠르다) 2) Heap의 구조 - Heap은 최대/최소 값을 구하기 위한 구조인 최대 힙(Max H.. 2020. 8. 31. 이전 1 다음
