힙1 6. 파이썬 마지막 자료구조 힙 1. 힙(Heap) 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 완전 이진트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙을 사용하는 이유 배열에 데이터를 넣고, 최대값과 최소값을 찾을 때 시간복잡도는 O(n)이다. 이에 반해, 힙에 데이터를 넣고, 최댓값과 최소값을 찾으려면 시간복잡도는 O(logn)이다. 우선순위 큐와 같이, 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘을 구현할 때 힙을 쓴다 2. 힙의 구조 최대힙 : 최대값을 가지기 위한 구조 최소힙 : 최소값을 구하기 위한 구조 다음 두가지 조건을 가지고 있는 자료구조 최대힙 : 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다 최소힙 : 각 노드의 값은 해당 노드.. 2023. 1. 21. 이전 1 다음
