The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.

• For example, for arr = [2,3,4], the median is 3.
• For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

• MedianFinder() initializes the MedianFinder object.
• void addNum(int num) adds the integer num from the data stream to the data structure.
• double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output

[null, null, null, 1.5, null, 2.0]

Explanation MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0

Constraints:

• -105 <= num <= 105
• There will be at least one element in the data structure before calling findMedian.
• At most 5 * 104 calls will be made to addNum and findMedian.

Follow up:

• If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
• If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

struct Heap<Element>
{
	var elements : [Element]
	let priorityFunction : (Element, Element) -> Bool

	init(elements: [Element] = [], priorityFunction: @escaping (Element, Element) -> Bool) {
		self.elements = elements
		self.priorityFunction = priorityFunction
		buildHeap()
	}

	mutating func buildHeap() {
		for index in (0 ..< count / 2).reversed() {
			siftDown(elementAtIndex: index)
		}
	}
	
	var isEmpty : Bool { return elements.isEmpty }
	var count : Int { return elements.count }

	func peek() -> Element? {
		return elements.first
	}

	mutating func enqueue(_ element: Element) {
		elements.append(element)
		siftUp(elementAtIndex: count - 1)
	}

	mutating func siftUp(elementAtIndex index: Int) {
		let parent = parentIndex(of: index)
		guard !isRoot(index),
			isHigherPriority(at: index, than: parent)
			else { return }
		swapElement(at: index, with: parent)
		siftUp(elementAtIndex: parent)
	}

	mutating func dequeue() -> Element? {
		guard !isEmpty
			else { return nil }
		swapElement(at: 0, with: count - 1)
		let element = elements.removeLast()
		if !isEmpty {
			siftDown(elementAtIndex: 0)
		}
		return element
	}
	
	mutating func siftDown(elementAtIndex index: Int) {
		let childIndex = highestPriorityIndex(for: index)
		if index == childIndex {
			return
		}
		swapElement(at: index, with: childIndex)
		siftDown(elementAtIndex: childIndex)
	}

	// Helper functions
	
	func isRoot(_ index: Int) -> Bool {
		return index == 0
	}
	
	func leftChildIndex(of index: Int) -> Int {
		return (2 * index) + 1
	}
	
	func rightChildIndex(of index: Int) -> Int {
		return (2 * index) + 2
	}
	
	func parentIndex(of index: Int) -> Int {
		return (index - 1) / 2
	}
	
	func isHigherPriority(at firstIndex: Int, than secondIndex: Int) -> Bool {
		return priorityFunction(elements[firstIndex], elements[secondIndex])
	}
	
	func highestPriorityIndex(of parentIndex: Int, and childIndex: Int) -> Int {
		guard childIndex < count && isHigherPriority(at: childIndex, than: parentIndex)
			else { return parentIndex }
		return childIndex
	}
	
	func highestPriorityIndex(for parent: Int) -> Int {
		return highestPriorityIndex(of: highestPriorityIndex(of: parent, and: leftChildIndex(of: parent)), and: rightChildIndex(of: parent))
	}
	
	mutating func swapElement(at firstIndex: Int, with secondIndex: Int) {
		guard firstIndex != secondIndex
			else { return }
		elements.swapAt(firstIndex, secondIndex)
	}
}

// A bonus extra for you: two extra functions, if the Element type is Equatable
extension Heap where Element : Equatable {
	
	// This function allows you to remove an element from the heap, in a similar way to how you would dequeue the root element.
	mutating func remove(_ element: Element) {
		guard let index = elements.index(of: element)
			else { return }
		swapElement(at: index, with: count - 1)
		elements.remove(at: count - 1)
		siftDown(elementAtIndex: index)
	}

	// This function allows you to 'boost' an element, by sifting the element up the heap. You might do this if the element is already in the heap, but its priority has increased since it was enqueued.
	mutating func boost(_ element: Element) {
		guard let index = elements.index(of: element)
			else { return }
		siftUp(elementAtIndex: index)
	}
}

var heap = Heap<Int>(elements: [3, 2, 8, 5, 0], priorityFunction: >)
heap.enqueue(6)
heap.enqueue(1)
heap.enqueue(4)
heap.enqueue(7)
//heap.dequeue()
//print(heap.elements)


class MedianFinder {
	var modifiedArr = [Double]()
	var minHeap = Heap<Int>(elements: [Int](), priorityFunction: <)
	var maxHeap = Heap<Int>(elements: [Int](), priorityFunction: >)
	init() {
		
	}
	
	func addNum(_ num: Int) {
		modifiedArr.append(Double(num))
	}
	
	func findMedian() -> Double {
		if modifiedArr.count == 1 {
			return modifiedArr[0]
		} else if modifiedArr.count == 2 {
			return Double(modifiedArr[0]+modifiedArr[1])/2.0
		} else {
			modifiedArr.sort()
			if modifiedArr.count % 2 == 0 {
				// even
				let middle = modifiedArr.count / 2
				return (modifiedArr[middle-1]+modifiedArr[middle])/2
			} else {
				// odd
				let middle = modifiedArr.count / 2
				return modifiedArr[middle]
			}
		}
	}
	
	// Using minHeap and maxHeap
	// https://www.youtube.com/watch?v=1LkOrc-Le-Y
	func addNum2(_ num: Int) {
		// maxHeap is empty
		if maxHeap.isEmpty {
			maxHeap.enqueue(num)
		}
		// heap size is same
		else if minHeap.count == maxHeap.count {
			if num < minHeap.peek()! {
				maxHeap.enqueue(num)
			} else {
				let lowest = minHeap.dequeue()
				minHeap.enqueue(num)
				maxHeap.enqueue(lowest!)
			}
		}
		// unequal heap sizes
		else {
			if minHeap.count == 0 {
				if num > maxHeap.peek()! {
					minHeap.enqueue(num)
				} else {
					let highest = maxHeap.dequeue()!
					maxHeap.enqueue(num)
					minHeap.enqueue(highest)
				}
			} else if num >= minHeap.peek()! {
				minHeap.enqueue(num)
			} else {
				if num < maxHeap.peek()! {
					let highest = maxHeap.peek()!
					maxHeap.dequeue()
					maxHeap.enqueue(num)
					minHeap.enqueue(highest)
				} else {
					minHeap.enqueue(num)
				}
			}
		}
	}
	
	func findMedian2() -> Double {
		if maxHeap.count > minHeap.count {
			return Double(maxHeap.peek()!)
		} else {
			print(minHeap.peek()!, maxHeap.peek()!)
			return Double(((Double(minHeap.peek()!) + Double(maxHeap.peek()!)) / 2.0))
		}
	}
}

var medianFinder = MedianFinder()
// medianFinder.addNum(5);    // arr = [1]
// medianFinder.addNum(2);    // arr = [1, 2]
// print(medianFinder.findMedian()) // return 1.5 (i.e., (1 + 2) / 2)
// medianFinder.addNum(3);    // arr[1, 2, 3]
// medianFinder.findMedian(); // return 2.0
medianFinder.addNum2(5)
print(medianFinder.findMedian2())
medianFinder.addNum2(3)
print(medianFinder.findMedian2())
medianFinder.addNum2(4)
print(medianFinder.findMedian2())
medianFinder.addNum2(2)
print(medianFinder.findMedian2())
medianFinder.addNum2(6)
print(medianFinder.findMedian2())