목록힙 (1)

개발 블로그

[자료구조 / Javascript] Heap

1. Heap이란? - 최댓값 또는 최솟값을 빠르게 찾아내기 위해 고안된 완전 이진트리를 기반으로 하는 자료구조이다. - Heap은 이진트리라는 특성 덕분에 반 정렬상태를 유지한다. - 부모 노드의 값이 자식 노드의 값보다 항상 크거나(Max heap) 작은(Min heap) 이진 트리를 말한다. - 즉, 값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다. - 힙에서는 가장 높은(혹은 가장 낮은) 값을 가지는 노드가 항상 Root 노드에 오게 되는 특징이 있으며, 이를 응용하면 우선 순위 큐와 자료형을 구현할 수 있다. 2. Heap의 종류 - Max heap - 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진트리 - Min heap ..
IT/자료구조 2021. 4. 4. 21:16
이전 Prev 1 Next 다음