[자료구조] 힙(Heap)의 개념 및 구현 (JavaScript)

1.힙(Heap)이란? 힙(Heap)이란 우선순위 큐(Priority Queue)를 위해 만들어진 자료구조이다. 완전 이진트리의 일종으로, 최대값과 최소값을 빠르게 찾기 위해 만들어진 자료구조이다. * 우선순위 큐는 말 그대로 큐에 우선순위 개념을 도입한 큐이다. 우선순위가 높은 데이터가 먼저 나가는 자료구조이다. 힙은 두 종류로 나눠진다. 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 작은 힙 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 큰 힙 여기서 키 값의 대소관계는 부모와 자식관계만 성립하고 형제 사이에는 대소관계가 정해지지 않는다. 아래 그림은 최소힙 예시이다. 2. 최소 힙(Min-Heap) 구현방법 힙은 배열을 이용하여 구현할 수 있다. 아래 그림과 같이 구현된다. 각 자식 노드들의 인덱스는 아래와 같이 계산한다. 왼쪽 자식노드 (부모 노드의 인덱스*2) + 1 오른쪽 자식노드 (부모 노드의 인덱스*2) + 2 먼저 아래처럼 최소힙 생성자 함수부터...

원문링크 : [자료구조] 힙(Heap)의 개념 및 구현 (JavaScript)