우선순위 큐 (1) 썸네일형 리스트형 [Data Structure / JS] 이진 힙(Binary Heaps) / 우선순위 큐(Priority Queue) 힙(Heap)이란 ? 완전 이진트리 기반의 자료구조로, 최대 힙과, 최소 힙 두 종류로 구분됩니다. 최대 힙의 경우에는 루트노드에 가까울 수록 크고, 최소힙은 루트 노드에 가까울 수록 작은 값을 가집니다. 힙에서는 데이터의 중복이 허용되며, 주로 우선순위 큐를 구현하는데 사용됩니다. 나아가 힙 정렬, 다익스트라의 최단 경로 알고리즘에서도 사용됩니다. 힙은 부모자식간의 크기 차이만 비교합니다. 형제 노드 간에의 크기 차이를 고려하지 않습니다. 구현 힙은 일반적으로 각 요소에 효율적으로 접근할 수 있는 배열을 통해 구현됩니다. 인덱스 i에 위치한 노드의 부모는 (i-1)/2에 위치하며, 왼쪽 자식 노드는 2*i + 1, 오른쪽자식 노드는 2*i + 2에 위치하게 됩니다. Heap에서의 삽입 힙에서의 삽입은 .. 이전 1 다음
