CS/Data Structures 썸네일형 리스트형 [Data Structures] 자료구조 힙(Heap)이란? 소개 Heap은 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 부모 노드의 인덱스는 1로, 왼쪽 자식 노드부터 2, 3 순서이다. (부모 노드의 인덱스) = (자식 노드 인덱스) // 2 (왼쪽 자식 노드의 인덱스) = (부모 노드의 인덱스) * 2 (오른쪽 자식 노드의 인덱스) = (부모 노드의 인덱스) * 2 + 1 힙을 사용하는 이유? 최솟값이나 최댓값을 찾기 위해 배열을 사용하면 Ο(n) 만큼 시간이 걸린다. 하지만 힙을 사용하면 O(logn) 만큼 소요되므로, 배열을 사용할 때보다 빠르게 최솟값과 최댓값을 구할 수 있다. 우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야하는 알고리즘 등에 활용된다. 특징 힙은 최대힙(Max he.. 더보기 이전 1 다음
