// Symmetric min max heap
// https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.472.6213&rep=rep1&type=pdf
class SymmetricMinMaxHeap {
constructor() {
this.heap = [null]
}
treeView() {
console.log('\n=TREE=')
console.log(`tree length: ${this.size()}`)
console.log(...this.heap.slice(0, 1))
console.log(...this.heap.slice(1, 3))
console.log(...this.heap.slice(3, 7))
console.log(...this.heap.slice(7, 15))
console.log(...this.heap.slice(15, 31))
}
size() {
return this.heap.length
}
insert(value) {
this.heap.push(value)
this.bubbleUp()
}
bubbleUp() {
// 변수 선언
let currentIndex
let isLeftNode
let siblingIndex
let parentIndex
let parentIsLeftNode
let parentSiblingIndex
// 변수 새로고침
const reloadVariables = (newIndex) => {
currentIndex = newIndex
isLeftNode = currentIndex % 2 === 1
siblingIndex = isLeftNode ? currentIndex + 1 : currentIndex - 1
parentIndex = Math.floor((currentIndex - 1) / 2)
parentIsLeftNode = parentIndex % 2 === 1
parentSiblingIndex = parentIsLeftNode
? parentIndex + 1
: parentIndex - 1
}
reloadVariables(this.heap.length - 1)
while (currentIndex > 0) {
// 형제가 있을 때,
if (this.heap[siblingIndex] !== undefined) {
// 현재 왼쪽 노드일 때,
if (isLeftNode) {
// 형제보다 클 때 SWAP
if (this.heap[currentIndex] > this.heap[siblingIndex]) {
;[this.heap[currentIndex], this.heap[siblingIndex]] = [
this.heap[siblingIndex],
this.heap[currentIndex],
]
reloadVariables(siblingIndex)
continue
}
}
// 현재 오른쪽 노드일 때,
else {
// 형제보다 작을 때 SWAP
if (this.heap[currentIndex] < this.heap[siblingIndex]) {
;[this.heap[currentIndex], this.heap[siblingIndex]] = [
this.heap[siblingIndex],
this.heap[currentIndex],
]
reloadVariables(siblingIndex)
continue
}
}
}
if (parentIndex === 0) break
// 부모가 왼쪽 노드일 때,
if (parentIsLeftNode) {
// 부모보다 작을 때 SWAP
if (this.heap[currentIndex] < this.heap[parentIndex]) {
;[this.heap[currentIndex], this.heap[parentIndex]] = [
this.heap[parentIndex],
this.heap[currentIndex],
]
reloadVariables(parentIndex)
continue
}
// 부모의 형제보다 클 때 SWAP
if (this.heap[currentIndex] > this.heap[parentSiblingIndex]) {
;[this.heap[currentIndex], this.heap[parentSiblingIndex]] =
[this.heap[parentSiblingIndex], this.heap[currentIndex]]
reloadVariables(parentSiblingIndex)
continue
}
}
// 부모가 오른쪽 노드일 때,
else {
// 부모보다 클 때 SWAP
if (this.heap[currentIndex] > this.heap[parentIndex]) {
;[this.heap[currentIndex], this.heap[parentIndex]] = [
this.heap[parentIndex],
this.heap[currentIndex],
]
reloadVariables(parentIndex)
continue
}
// 부모의 형제보다 작을 때 SWAP
if (this.heap[currentIndex] < this.heap[parentSiblingIndex]) {
;[this.heap[currentIndex], this.heap[parentSiblingIndex]] =
[this.heap[parentSiblingIndex], this.heap[currentIndex]]
reloadVariables(parentSiblingIndex)
continue
}
}
break
}
}
extractMin() {
const min = this.heap[1]
if (this.size() <= 1) {
return null
} else if (this.size() <= 2) {
this.heap.pop()
} else {
this.heap[1] = this.heap.pop()
this.bubbleDown(1)
}
return min
}
extractMax() {
let max = this.heap[2]
if (this.size() <= 1) {
return null
} else if (this.size() <= 2) {
max = this.heap[1]
this.heap.pop()
} else if (this.size() <= 3) {
this.heap.pop()
} else {
this.heap[2] = this.heap.pop()
this.bubbleDown(2)
}
return max
}
bubbleDown(index) {
const isLeftNode = index % 2 === 1
const leftChildIndex = 2 * index + 1
const rightChildIndex = 2 * index + 2
const siblingIndex = isLeftNode ? index + 1 : index - 1
const siblingLeftChildIndex = 2 * siblingIndex + 1
const siblingRightChildIndex = 2 * siblingIndex + 2
const length = this.heap.length
let toBeExchangeIndex = index
// 현재 인덱스가 왼쪽 노드라면
if (isLeftNode) {
// 왼쪽 자식이 존재하고, toBeExchangeIndex보다 작으면 toBeExchangeIndex에 왼쪽 자식 대입
if (
leftChildIndex < length &&
this.heap[leftChildIndex] < this.heap[toBeExchangeIndex]
) {
toBeExchangeIndex = leftChildIndex
}
// 오른쪽 자식이 존재하고, toBeExchangeIndex보다 작으면 toBeExchangeIndex에 오른쪽 자식 대입
if (
rightChildIndex < length &&
this.heap[rightChildIndex] < this.heap[toBeExchangeIndex]
) {
toBeExchangeIndex = rightChildIndex
}
// 형제의 왼쪽 자식이 존재하고, toBeExchangeIndex보다 작으면 toBeExchangeIndex에 형제의 왼쪽 자식 자식 대입
if (
siblingLeftChildIndex < length &&
this.heap[siblingLeftChildIndex] < this.heap[toBeExchangeIndex]
) {
toBeExchangeIndex = siblingLeftChildIndex
}
// 형제의 오른쪽 자식이 존재하고, toBeExchangeIndex보다 작으면 toBeExchangeIndex에 형제의 오른쪽 자식 대입
if (
siblingRightChildIndex < length &&
this.heap[siblingRightChildIndex] < this.heap[toBeExchangeIndex]
) {
toBeExchangeIndex = siblingRightChildIndex
}
// toBeExchangeIndex가 index와 불일치하면 서로 변경
if (toBeExchangeIndex !== index) {
;[this.heap[index], this.heap[toBeExchangeIndex]] = [
this.heap[toBeExchangeIndex],
this.heap[index],
]
this.bubbleDown(toBeExchangeIndex)
}
}
//
else {
// 왼쪽 자식이 존재하고, toBeExchangeIndex보다 크면 toBeExchangeIndex에 왼쪽 자식 대입
if (
leftChildIndex < length &&
this.heap[leftChildIndex] > this.heap[toBeExchangeIndex]
) {
toBeExchangeIndex = leftChildIndex
}
// 오른쪽 자식이 존재하고, toBeExchangeIndex보다 크면 toBeExchangeIndex에 오른쪽 자식 대입
if (
rightChildIndex < length &&
this.heap[rightChildIndex] > this.heap[toBeExchangeIndex]
) {
toBeExchangeIndex = rightChildIndex
}
// 형제의 왼쪽 자식이 존재하고, toBeExchangeIndex보다 크면 toBeExchangeIndex에 형제의 왼쪽 자식 자식 대입
if (
siblingLeftChildIndex < length &&
this.heap[siblingLeftChildIndex] > this.heap[toBeExchangeIndex]
) {
toBeExchangeIndex = siblingLeftChildIndex
}
// 형제의 오른쪽 자식이 존재하고, toBeExchangeIndex보다 크면 toBeExchangeIndex에 형제의 오른쪽 자식 대입
if (
siblingRightChildIndex < length &&
this.heap[siblingRightChildIndex] > this.heap[toBeExchangeIndex]
) {
toBeExchangeIndex = siblingRightChildIndex
}
// toBeExchangeIndex가 index와 불일치하면 서로 변경
if (toBeExchangeIndex !== index) {
;[this.heap[index], this.heap[toBeExchangeIndex]] = [
this.heap[toBeExchangeIndex],
this.heap[index],
]
this.bubbleDown(toBeExchangeIndex)
}
}
}
}
const solution = (operations) => {
const Heap = new SymmetricMinMaxHeap() // Heap 객체
for (let operation of operations) {
operation[0] === 'I'
? Heap.insert(+operation.slice(2))
: operation.slice(2) === '1'
? Heap.extractMax()
: Heap.extractMin()
}
if (Heap.size() <= 1) {
return [0, 0]
} else if (Heap.size() === 2) {
const data = Heap.extractMin()
return [data, data]
} else {
return [Heap.extractMax(), Heap.extractMin()]
}
}
From design to DevOps with frontend and backend.