🎯 목표

자바스크립트로 min heap을 구현하는 class를 만들어 보고 프로그래머스 문제 더 맵게를 풀기

Lv0 ~ Lv1을 풀다 우선순위 큐 자료 구조를 활용한 문제가 나오면 기본 자료구조와 알고리즘 지식이 필요합니다.

📚 우선순위 큐 (Priority Queue) 정의

• 큐의 자료구조는 알다시피 스택과 반대로 FIFO를 가지는 특성이 있습니다.

• 우선순위 큐는 더 나아가 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조입니다.

  • ex) 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우

• ADT(Abstract Data Type) : 실제 존재하지는 않지만동작을 설명하는 개념입니다.

• Heap을 이용하여 구현할 수 있습니다.

• (구현 방식 중 리스트도 있지만 heap이 더 적절하고 많이 사용됩니다.)
  

  • Heap은 이진트리 기반으로 구현됩니다.

  • 부모 - 자녀처럼 계층적인 형태를 가지는 구조입니다.
    아래와 같이 3은 8의 자식노드이며 8은 3의 부모노드입니다.
    
    [이진트리 구조] 출처: 위키백과

  • Max heap : 부모 노드가 자식노드보다 항상 크거나 같은 트리

  • Min heap : 부모 노드가 자식노드보다 항삭 작거나 같은 트리

주요 동작과 Big O 표기

• Insert : O(log N)
  들어오는 값은 가장 바깥쪽에 넣어진 후 부모노드와 비교하여 차근차근 맞는 곳과 스와핑(교환)됩니다.

• Delete : O(log N)
  루트 노드가 먼저 삭제된 다음 자녀 노드들과 비교하여 맞는 곳에 스와핑됩니다.
  스와핑 시 자녀 노드들 중 우선순위가 더 높은 노드가 선택됩니다.
  

• Heapify : 힙 구조를 build 하는 것 O(N)
  • 가장 오른쪽에 있는 child key를 선택합니다.
  • 선택한 곳의 부모노드로 이동합니다.
  • 이제 선택한 부근의 트리부터 힙을 만족하는지 확인하여 재정렬합니다.
  • 다음 왼쪽 트리의 힘이 만족하는 지 확인하여 재정렬 합니다.

💡 중요!
여기서 부모 노드와 자식 노드를 찾는 공식이 있는데 외워두는 것이 좋습니다.
부모 노드의 index = 자식 노드의 (index - 1) / 2
(나머지는 버림)
왼쪽 자식 노드의 index = 부모 노드의 index 2 + 1
오른쪽 자식도드의 index = 부모 노드의 index 2 + 2

🎮 Javascript로 우선순위 큐를 min heap으로 구현해보기

• Java나 C언어는 heapify 함수가 있어 구현하기 쉽다고 하네요
• Javascript는 그런 기능이 없어서 class를 이용하여 한땀한땀 만들 예정입니다.

이래서 코딩테스트를 C언어나 python으로 하는 것이 좋다고 하는 것일까요?

코드 보기
💨 아래 코드에 상세하게 주석을 하나하나 달아보았습니다.

❗ insert와 delete만 구현해보았습니다.

(heapify는 다음 포스팅에서..)

class Heap {
	constructor() {
		this.heap = []
	}

	insert(value) {
		
		// 우선 가장 배열의 가장 마지막에 삽입
		this.heap.push(value)
		// 부모노드를 찾은 뒤 부모노드와 비교하여 해당 값이 더 작으면 스와핑
		let currentIdx = this.heap.length - 1
		let parentIdx = Math.floor((currentIdx - 1) / 2)
		while ( currentIdx > 0 && this.heap[currentIdx] < this.heap[parentIdx] ) { 
		// while문 사용 : 해당 값이 이 조건에 부합하지 않을때까지 반복
			[this.heap[currentIdx], this.heap[parentIdx]] = [this.heap[parentIdx], this.heap[currentIdx]]
			// 구조분해 할당을 이용하여 값을 바꿔줌
			currentIdx = parentIdx
			parentIdx = Math.floor((currentIdx - 1) / 2 )
			// 값을 바꿔주었으니 index값도 변경해줌
		}
	}

	delete() {
	// 가장 우선순위가 높은 즉, 가장 작은 숫자가 먼저 삭제된다.
	// 그 후 가장 끝에 있는 숫자가 가장 위로 올라오면서 정렬을 진행한다. 
		
		this.heap.splice(0, 1, this.heap.pop()) // 맨 앞에 있는 요소를 삭제
		let currentIdx = 0
		// 반복문 : 맨 앞의 요소가 자식노드보다 크면 스왑
		while(
			// 왼쪽 자식노드, 오른쪽 자식노드 크기 비교
			this.heap[currentIdx] > this.heap[currentIdx * 2 + 1] ||
			this.heap[currentIdx] > this.heap[currentIdx * 2 + 2]
		) {
			// 더 작은 자식노드를 변수에 할당
			let smallerChildIdx = 
               this.heap[currentIdx * 2 + 1] > this.heap[currentIdx * 2 + 2] 
               ? currentIdx * 2 + 2 : currentIdx * 2 + 1
			// 더 작은 자식노드와 현재 값을 스와핑

           // 임시 변수를 사용하여 값 교환
           let temp = this.heap[currentIdx]
           this.heap[currentIdx] = this.heap[smallerChildIdx]
           this.heap[smallerChildIdx] = temp

           // 현재 인덱스를 업데이트
           currentIdx = smallerChildIdx
		}
	}
}

기능을 만들어 봤으니 사용해봐야겠죠?

💨 예제 코드

let minArray = [10, 3, 100, 40, 80, 6, 200, 421]
const minHeap = minArray.reduce((arr, value) => {
    arr.insert(value)
    return arr
}, new Heap())
console.log(minHeap.heap)
minHeap.delete()
console.log(minHeap.heap)

❗ reduce 함수를 사용하여 배열의 값을 하나하나 넣는 것으로 해주었습니다.
❗ 아직 heapify 기능이 없기 때문에 기존에 정렬되어 있지 않은 상태의 배열을 정리하는 것은 넣지 않았습니다.

💫 결과는 ?

다음 포스트에서는 실제 프로그래머스 문제와 해답을 같이 풀어보겠습니다!