[JavaScript] 힙 자료구조

힙이란…?

힙 정의

힙은 완전 이진 트리^[각주:1] 마지막 일종으로, 특정한 규칙을 따라 부모 노드와 자식 노드 간에 값이 정렬된다.
그러나 완전한 열이 아닌 느슨한 정렬이라고 할 수 있는 반정렬 상태를 유지한다.
힙은 정렬, 우선순위 큐, 스케줄링과 같은 다양한 알고리즘에서 활용되는 자료구조이다.

힙 종류

최대 힙

모든 부모 노드가 그 자식 노드보다 크거나 같은 값을 갖는 특성을 가지

최소 힙

모든 부모 노드가 그 자식 노드보다 작거나 같은 값을 갖는 특성을 가짐

힙 구현 방법

보통 배열을 이용하여 구현하는데, 루트 노드에 첫 번째 인덱스에 위치하게 되고 i 번째 인덱스에 있는 노드의 왼쪽 자식 노드는 2 x i 인덱스에 위치하며, 오른쪽 자식 노드는 2 x i + 1 인덱스에 위치한다.

힙 시간 복잡도

원소 삽입 혹은 삭제가 일어났을 때 힙을 재배열할 때 삽입과 삭제 연산는 $O(1)$ 시간복잡도이지만 재배열(heapify)의 과정은 $O(logN)$이므로 최종적으로 $O(logN)$의 시간복잡도를 가지게된다.

삽입

1. 가장 말단 노드에 원소 삽입
2. 최대 힙의 경우 새로운 원소가 부모 노드보다 크면 둘을 교환, 최소 힙의 경우 새로운 원소가 부모 노드 보다 작으면 둘을 교환
3. 힙 특성 만족할 때까지 위 2번 과정 반복

삭제

1. 루트 노드 삭제 후 가장 말단 노드를 루트노드로 이동
2. 최대 힙의 루트 노드가 자식 노드보다 작으면 더 큰 자식과 교환, 최소 힙의 경우 루트 노드가 자식 노드보다 크면 더 작은 자식과 교환
3. 힙 특성 만족할 때까지 위 2번 과정 반복

JS에서 힙 구현

최소 힙

class MinHeap {
    constructor() {
		    // 힙 저장할 배열 초기화, 첫 번째 인덱스 사용하지 않으므로움
        this.heap = [null]; 
    }

		// 힙의 사이즈를 반환하며, 첫 번째 인덱스를 비워두기 때문에 길이에서 1을 빼기
    get[각주:2] size() {
        return this.heap.length - 1;  
    }
		
		// 최소 힙의 최소 값을 반환
    get min() {
        return this.heap[1] ? this.heap[1] : null;
    }
		
		// 두 인덱스의 값을 교환
    swap(index1, index2) {
        [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
    }
		
		// 새로운 값 힙에 삽입
    heappush(value) {
        this.heap.push(value);
        this.heapifyUp();
    }
		
		// 새로운 값 적절한 위치로 이동
    heapifyUp() {
		    // 마지막 인덱스부터 시작
        let index = this.heap.length - 1;
        // 부모 노드가 현재 노드 보다 큰 경우 교환
        while (index > 1 && this.heap[(index / 2) >>[각주:3] 0 > this.heap[index]) {
            this.swap((index / 2) >> 0, index);  // 부모 노드와 현제 노드 교환
            index = (index / 2) >> 0;  // 부모 노드의 인덱스로 이
        }
    }
		
		// 루트 노드를 제거하고 힙 속성을 유지
    heappop() {
		     // 힙이 비어 있는 경우 null을 반환
        if (this.size === 0) return null;
        // 힙에 하나의 원소만 있는 경우 바로 반환
        if (this.size === 1) return this.heap.pop();
        // 루트 노드를 저장
        const min = this.heap[1];
        // 마지막 노드를 루트 노드로 이동
        this.heap[1] = this.heap.pop();
         // 힙 속성을 유지하기 위해 아래로 이동
        this.heapifyDown(1);
        // 제거된 루트 노드를 반환
        return min;
    }

		// 루트 노드를 적절한 위치로 이동시켜 힙 속성을 유지
    heapifyDown(index) {
        while (index * 2 < this.heap.length) {
		        // 왼쪽 자식 인덱스
            let smallerChildIndex = index * 2;
            // 오른쪽 자식이 존재하고 왼쪽 자식보다 작은 경우 오른쪽 자식을 선택
            if (smallerChildIndex + 1 < this.heap.length && this.heap[smallerChildIndex + 1] < this.heap[smallerChildIndex]) {
                smallerChildIndex++;
            }
             // 현재 노드가 자식 노드보다 작으면 종료
            if (this.heap[index] <= this.heap[smallerChildIndex]) break;
            this.swap(index, smallerChildIndex);
            // 자식 노드의 인덱스로 이동
            index = smallerChildIndex;
        }
    }
}

최대 힙

class MaxHeap {
    constructor() {
			  // 힙 저장할 배열 초기화, 첫 번째 인덱스 사용하지 않으므로움
        this.heap = [null];
    }
		
		// 힙의 사이즈를 반환하며, 첫 번째 인덱스를 비워두기 때문에 길이에서 1을 빼기
    get size() {
        return this.heap.length - 1; 
    }
		
		// 최대 힙의 최대 값 반환
    get max() {
        return this.heap[1];  
    }
		
		// 두 인덱스의 값을 교환
    swap(index1, index2) {
        [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
    }
		
		// 새로운 값을 힙에 삽입
    heappush(value) {
		    // 새로운 값을 배열의 끝에 추가
        this.heap.push(value);
	      // 힙 속성을 유지하기 위해 위로 이동
        this.heapifyUp();
    }
		
		// 새로운 값을 적절한 위치로 이동시켜 힙 속성을 유지
    heapifyUp() {
		    // 마지막 인덱스부터 시작
        let index = this.heap.length - 1;
        // 부모 노드가 현재 노드보다 작은 경우 교환
        while (index > 1 && this.heap[(index / 2) >> 0] < this.heap[index]) {
            // 부모 노드와 현재 노드를 교환
            this.swap((index / 2) >> 0, index);
            // 부모 노드의 인덱스로 이동합니다.
            index = (index / 2) >> 0;
        }
    }
		
		// 루트 노드를 제거하고 힙 속성을 유지
    heappop() {
        // 힙이 비어 있는 경우 null을 반환
        if (this.size === 0) return null;
        // 힙에 하나의 원소만 있는 경우 바로 반환
        if (this.size === 1) return this.heap.pop();
        // 힙 속성을 유지하기 위해 아래로 이동
        const max = this.heap[1];
        // 마지막 노드를 루트 노드로 이동
        this.heap[1] = this.heap.pop();
		    // 힙 속성을 유지하기 위해 아래로 이동
        this.heapifyDown(1);
        // 제거된 루트 노드를 반환
        return max;
    }
		
		// 루트 노드를 적절한 위치로 이동시켜 힙 속성을 유지
    heapifyDown(index) {
        while (index * 2 < this.heap.length) {
		        // 왼쪽 자식 인덱스
            let largerChildIndex = index * 2;
            // 오른쪽 자식이 존재하고 왼쪽 자식보다 큰 경우 오른쪽 자식을 선택
            if (largerChildIndex + 1 < this.heap.length && this.heap[largerChildIndex + 1] > this.heap[largerChildIndex]) {
                largerChildIndex++;
            }
            // 현재 노드가 자식 노드보다 크면 종료
            if (this.heap[index] >= this.heap[largerChildIndex]) break;
            // 현재 노드와 큰 자식 노드를 교환
            this.swap(index, largerChildIndex);
            // 자식 노드의 인덱스로 이동
            index = largerChildIndex;
        }
    }
}

1. 부모 노드 밑에 자식 노드가 최대 2개 있을 수 있고, 마지막 레벨 제외한 모든 레벨의 노드가 완전히 채워진 트리 구조 [본문으로]
2. ES6에 도입된 Javascript getter 메서드로 클래스 내에 get 키워드 사용하여 메서드 정의 시, 해당 메서드는 프로퍼티처럼 호출할 수 있다. 그러나 직접적인 변경은 불가능하다. [본문으로]
3. 비트 연산자를 이용해 소수점 버림 연산하는 것으로 >> 연산자는 비프 시프트 연산자로 오른쪽으로 시프트할 때 부호를 유지하면서 소수점 이하를 버린다. 음수와 양수 모두 작동하며 Math.floor와 유사한 역할을 하는데 비트 연산자가 조금 더 빠르게 연산을 수행한다. [본문으로]