[알고리즘] 이진 힙과 우선순위 큐 (자바스크립트)

이진 힙 (Binary Heap) 기본적으로 힙은 트리 구조의 한 종류이다. 이진 힙 외에도 굉장히 많은 힙 알고리즘이 존재한다. 이진 힙은 최대 힙, 최소 힙으로 구분할 수 있다. 힙 구조는 그래프 순회를 위한 우선순위 큐 (Priority Queue) 구현에 주로 사용된다. 최대 이진 힙에서는 부모 노드가 항상 자식 노드보다 큰 값을 가진다. 루트부터 노드를 타고 내려갈수록 더 작은 값을 갖는다는 뜻이다. 최소 이진 힙에서는 그 반대로, 부모 노드가 언제나 좌우의 자식 노드보다 작은 값을 갖는다. 오름차순, 내림차순으로 생각해도 될 듯 그럼 이진 탐색 트리(BST)와 비슷한 것 아닌가? 할 수 있곘지만, 이진 탐색 트리와 다르게 좌우 자식 노드의 크기 순서를 고려하지 않는다. 힙 정렬 트리 구조를 갖..

원문링크 : [알고리즘] 이진 힙과 우선순위 큐 (자바스크립트)