JS 알고리즘 19일차 - 이진 힙

정의 힙은 트리 구조의 일종이다. 이진 탐색 트리와도 매우 비슷하다. 이진 탐색 트리와는 다르게 왼쪽과 오른쪽에는 순서가 존재하지 않는다. 최대 이진 힙에서는 부모 노드가 항상 자식 노드보다 큰 값을 가진다. 다시 말해 최대 이진 힙에서는 모든 자식 노드가 부모보다 작다. 그렇지만 형제 노드 사이에는 순서가 보장되지 않는다. 각 노드는 언제나 최대 2개의 자식을 가진다. 항상 왼쪽이 먼저 채워지고 오른쪽이 채워진다. 이진 힙은 언제나 최적의 용량을 가진다. 우선순위 큐에 사용된다. 힙 정렬 배열 안에 있는 모든 인덱스에 대해, 왼쪽 자식은 2n+1에 저장되어 있고, 오른쪽 자식은 2n+2에 저장되어 있다. 반대로 자식의 인덱스에서 (인덱스 - 1) / 2의 소수점을 버린 정수가 부모 인덱스가 된다. Insert 메소드 - 최대 이진 힙 의사코드 값을 하나 입력한다. 배열의 끝에 값을 추가한다. 알맞은 자리로 갈 때까지 버블 업을 해준다. 부모의 자리를 찾는다. ((인덱스 - 1) /...

원문링크 : JS 알고리즘 19일차 - 이진 힙