자바스크립트로 min heap을 구현하는 class를 만들어 보고 프로그래머스 문제 더 맵게를 풀기
Lv0 ~ Lv1을 풀다 우선순위 큐 자료 구조를 활용한 문제가 나오면 기본 자료구조와 알고리즘 지식이 필요합니다.
큐의 자료구조는 알다시피 스택과 반대로 FIFO를 가지는 특성이 있습니다.
우선순위 큐는 더 나아가 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조입니다.
ADT(Abstract Data Type) : 실제 존재하지는 않지만동작을 설명하는 개념입니다.
Heap을 이용하여 구현할 수 있습니다.
(구현 방식 중 리스트도 있지만 heap이 더 적절하고 많이 사용됩니다.)
Heap은 이진트리 기반으로 구현됩니다.
부모 - 자녀처럼 계층적인 형태를 가지는 구조입니다.
아래와 같이 3은 8의 자식노드이며 8은 3의 부모노드입니다.
[이진트리 구조] 출처: 위키백과
Max heap : 부모 노드가 자식노드보다 항상 크거나 같은 트리
Min heap : 부모 노드가 자식노드보다 항삭 작거나 같은 트리
주요 동작과 Big O 표기
💡 중요!
여기서 부모 노드와 자식 노드를 찾는 공식이 있는데 외워두는 것이 좋습니다.
부모 노드의 index = 자식 노드의 (index - 1) / 2
(나머지는 버림)
왼쪽 자식 노드의 index = 부모 노드의 index 2 + 1
오른쪽 자식도드의 index = 부모 노드의 index 2 + 2
이래서 코딩테스트를 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 기능이 없기 때문에 기존에 정렬되어 있지 않은 상태의 배열을 정리하는 것은 넣지 않았습니다.
💫 결과는 ?
다음 포스트에서는 실제 프로그래머스 문제와 해답을 같이 풀어보겠습니다!