자료구조 & 알고리즘/비선형 자료구조

[자료 구조] 힙(Heap) in java

힙의 구조와 특징 완전 이진 트리 형태 [중복 값 허용, 반 정렬 상태]로 최소값 또는 최대값을 빠르게 찾아내는데 유용한 자료구조입니다. 따라서 최소 힙, 최대 힙 두가지 종류가 존재합니다. + 우선순위 큐(Priority Queue)를 위한 자료구조라고도 합니다. 최소 힙(Min Heap) 부모 노드의 키가 자식 노드의 키보다 작거나 같은 형태 -> 즉, root 노드가 가장 작습니다. 자식 노드에서는 따로 규칙이 없어서 왼쪽이 오른쪽보다 클수도, 오른쪽이 왼쪽보다 클 수도 있습니다.. 보장되어있지 않아 반 정렬 형태라고 합니다. 최대 힙(Max Heap) 부모 노드의 키가 자식노드의 키보다 크거나 같은 형태 -> 즉, root 노드가 가장 큽니다. 최소 힙과 마찬가지로 반 정렬 형태입니다. 힙의 시간..