Javascript - 최소 힙(MinHeap)

• 이진 트리를 기반으로 한 자료구조

• 부모 노드가 자식들보다 작거나 같은 구조, 가장 작은 값이 root에 위치하는 자료구조

• 우선순위 큐 구현, Heap Sort에 활용된다.

• 가장 작은 값을 O(1)의 시간으로 빠르게 찾을 수 있다.

• heapifyUp();

  • 새로운 노드가 삽입되고 자기 위치를 찾아가도록 하는 메소드

• heapifyDown();

  • root 노드가 pop되고 최소 힙의 조건에 맞도록 트리를 재정비하는 메소드

class MinHeap {
	constructor() {
		this.heap = [];
	}
	  
	push(value) {
		this.heap.push(value);
		this.heapifyUp();
	}
	  
	pop() {
		if (!this.heap.length) return null;
	  
		const root = this.heap[0];
		const lastNode = this.heap.pop();
		  
		this.heap[0] = lastNode;
		this.heapifyDown();
		  
		return root;
	}
	  
	// 새로 들어온 노드가 최소 힙을 만족하는 자리를 찾도록 도와주는 메소드
	heapifyUp() {
		let index = this.heap.length - 1;
		while (index > 0) {
			const parentIndex = Math.floor((index - 1) / 2);
			if (this.heap[parentIndex] <= this.heap[index]) break;
			this.swap(this.heap[parentIndex], this.heap[index]);
			index = parentIndex;
		}
	}
	  
	// 루트 노드를 제거한 후 최소 힙의 조건에 맞도록 힙을 재정비하는 메소드
	heapifyDown() {
		let index = 0;
		const length = this.heap.length;
		  
		while (true) {
			let smallest = index;
			const leftChildIndex = 2 * index + 1;
			const rightChildIndex = 2 * index + 2;
	  
			// 왼쪽 자식이 더 작은 경우 가장 작은 수의 인덱스 = 왼쪽 자식 인덱스
			if (
			leftChildIndex < length &&
			this.heap[leftChildIndex] < this.heap[smallest]
			)
				smallest = leftChildIndex;
	  
			// 왼쪽 체크 후, 오른쪽 자식이 더 작을 경우 가장 작은 수의 인덱스 = 오른쪽 자식 인덱스
			if (
			rightChildIndex < length &&
			this.heap[rightChildIndex] < this.heap[smallest]
			)
				smallest = rightChildIndex;
	  
			// 가장 작은 수의 인덱스가 0 이라면 반복을 멈춤
			if (smallest === index) break;
		  
			// 자식 중 더 작은 수가 있었다면 부모와 위치 교환
			this.swap(this.heap[index], this.heap[smallest]);
	  
			// 바뀐 위치에서 반복
			index = smallest;
		}
	}

	swap(a, b) {
		[a, b] = [b, a];
	}
	
	size() {
		return this.heap.length;
	}
	  
	getMin() {
		return this.heap[0];
	}
	  
	isEmpty() {
		return this.heap.length === 0;
	}
}