295. Find Median from Data Stream

문제링크: https://leetcode.com/problems/find-median-from-data-stream/

데이터를 삽입하고 중간값을 가져올 수 있는 데이터 구조를 만든다. 총 짝수개일 경우 중간값은 두개의 평균을 낸다.

Solution

MinHeap + MaxHeap

가장 큰 데이터, 가장 작은 데이터 등 우선순위의 조건이 단순할 경우 priority queue 의 형태로 Heap을 사용한다. 하지만 중간값은 단순한 우선순위 조건이 아니기 때문에 추가적으로 Heap을 두 개 생성해서 Heap의 사이즈로 밸런스를 잡는다면 중간값을 쉽게 유추할 수 있다. 중간값 보다 작은 값은 MaxHeap에 중간값보다 큰 값은 MinHeap을 사용하고 두 Heap의 크기를 동일하게(+-1)로 맞춘다면 작은 값들 중 가장 큰 값 또는 큰 값들 중 가장 작은값이 중간값이된다. 따라서 삽입할 때 현재 중간값보다 큰지 작은지를 확인해 Heap에 삽입하고 두 Heap의 밸런스를 조절하면 중간값을 쉽게 추출할 수 있다.

Algorithm

Heap with comparator

class Heap {
	constructor(comparator) {
		this.size = 0;
		this.values = [];
		this.comparator = comparator || Heap.minComparator;
	}

	push(val) {
		this.values.push(val);
		this.size ++;
		this.bubbleUp();
	}

	peek() {
		return this.values[0] || null;
	}

	pop() {
		const max = this.values[0];
		const end = this.values.pop();
		this.size --;
		if (this.values.length) {
			this.values[0] = end;
			this.bubbleDown();
		}
		return max;
	}

	bubbleUp() {
		let index = this.values.length - 1;
		let parent = Math.floor((index - 1) / 2);

		while (this.comparator(this.values[index], this.values[parent]) < 0) {
			[this.values[parent], this.values[index]] = [this.values[index], this.values[parent]];
			index = parent;
			parent = Math.floor((index - 1) / 2);
		}
	}

	bubbleDown() {
		let index = 0, length = this.values.length;

		while (true) {
			let left = null,
				right = null,
				swap = null,
				leftIndex = index * 2 + 1,
				rightIndex = index * 2 + 2;

			if (leftIndex < length) {
				left = this.values[leftIndex];
				if (this.comparator(left, this.values[index]) < 0) swap = leftIndex;
			}

			if (rightIndex < length) {
				right = this.values[rightIndex];
				if ((swap !== null && this.comparator(right, left) < 0) || (swap === null && this.comparator(right, this.values[index]))) {
					swap = rightIndex;
				}
			}
			if (swap === null) break;

			[this.values[index], this.values[swap]] = [this.values[swap], this.values[index]];
			index = swap;
		}
	}
  
  static minComparator(a, b) {
    return a - b;
  }
  
  static maxComparator(a, b) {
    return b - a;
  }
}

이 Heap은 생성자를 통해 우선순위 조건 함수를 함께 넣어 Priority queue를 만들 수 있다. static 메소드로 maxheap , minheap에 필요한 우선순위를 만들어 생성시에 활용하면 minHeap과 maxHeap을 만들 수 있다.

MedianFinder

• addNum은 먼저 leftHeap과 rightHeap중 어느 부분에 넣을 지 판단한다.
• 중간값(leftHeap.peek()) 보다 클 경우 오른쪽에, 작을 경우 왼쪽에 삽입한다.
• 양쪽 트리의 크기가 2로 벌어졌을 경우 큰 힙에서 pop()을 해 작은 힙으로 push()하여 크기를 조절한다.
• findMedian을 하면 두 힙의 크기를 통해 같으면(짝수) 두 중간값의 평균, 크기가 다르면 큰 트리의 peek()값을 통해 중간값을 리턴한다.

var MedianFinder = function() {
  this.leftHeap = new Heap(Heap.maxComparator);
  this.rightHeap = new Heap(Heap.minComparator);
};

/** 
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function(num) {
  if (this.leftHeap.size === 0) this.leftHeap.push(num);
  else if (this.leftHeap.peek() >= num) this.leftHeap.push(num);
  else this.rightHeap.push(num);
  
  // balance tree
  if (this.rightHeap.size >= this.leftHeap.size + 2) {
    const temp = this.rightHeap.pop();
    this.leftHeap.push(temp);
  } else if (this.leftHeap.size >= this.rightHeap.size + 2) {
    const temp = this.leftHeap.pop();
    this.rightHeap.push(temp);
  }
  
};

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function() {
  if (this.rightHeap.size === this.leftHeap.size) return (this.leftHeap.peek() + this.rightHeap.peek()) / 2;
  else return this.leftHeap.size > this.rightHeap.size ? this.leftHeap.peek() : this.rightHeap.peek();
};