JS 알고리즘 20일차 - 이진 힙(2)

ExtractMax 메소드 소개 힙에서 루트를 제거하는 과정, 즉 최대 힙에서는 최대값을 최소 힙에서는 최소값을 제거한 다음에 프로퍼티를 정리한다. 이 과정을 다운힙 혹은 버블 다운, 퍼콜레이트 다운, 시프트 다운, 트리클 다운, 히피파이 다운, 카스케이드 다운, 최대/최소값 추출 등으로 불린다. 의사코드 최대 이진 힙 클래스에 인수는 받지 않고 이진 힙의 루트를 출력하는 메소드를 작성한다. 루트를 힙에서 삭제한 뒤 루트를 가장 마지막 값으로 변경한다. 해당 인덱스의 왼쪽과 오른쪽 자식을 확인한다. 왼쪽 자식은 2*인덱스+1에 위치한다. 오른쪽 자식은 2*인덱스+2에 위치한다. 자식 중 현재 루트보다 큰 값이 있으면 자리를 변경한다. 이 과정을 자식이 현재 루트보다 작을 때까지 반복한다. 코드 class MaxBinaryHeap { constructor() { this.values = []; } extractMax() { const max = this.values[0]; const ...

원문링크 : JS 알고리즘 20일차 - 이진 힙(2)