Largest Triple Products

You’re given a list of n integers arr[0..(n-1)]. You must compute a list output[0..(n-1)] such that, for each index i (between 0 and n-1, inclusive), output[i] is equal to the product of the three largest elements out of arr[0..i] (or equal to -1 if i < 2, as arr[0..i] then includes fewer than three elements).Note that the three largest elements used to form any product may have the same values as one another, but they must be at different indices in arr.

Signature

int[] findMaxProduct(int[] arr)

Input

n is in the range [1, 100,000]. Each value arr[i] is in the range [1, 1,000].

Output

Return a list of n integers output[0..(n-1)], as described above.

Example 1

n = 5 arr = [1, 2, 3, 4, 5] output = [-1, -1, 6, 24, 60]

The 3rd element of output is 3*2*1 = 6, the 4th is 4*3*2 = 24, and the 5th is 5*4*3 = 60.

Example 2

n = 5 arr = [2, 1, 2, 1, 2] output = [-1, -1, 4, 4, 8]

The 3rd element of output is 2*2*1 = 4, the 4th is 2*2*1 = 4, and the 5th is 2*2*2 = 8.

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)


// We don’t provide test cases in this language yet, but have outlined the signature for you. Please write your code below, and don’t forget to test edge cases!
func findMaxProduct(arr: [Int]) -> [Int] {
	var newArray = [Int]()
	var heap = Heap<Int>(elements: [], priorityFunction: >)
	var temporaryArray = [Int]()
	for i in 0 ..< arr.count {
		temporaryArray.append(arr[i])
		heap.enqueue(arr[i])
		if i < 2 {
			newArray.append(-1)
		} else {
			var product = 1
			for _ in 0...2 {
				let highest = heap.dequeue()
				if highest != nil {
					product = product * highest!
				}
			}
			newArray.append(product)
		}
		heap.elements.removeAll()
		for element in temporaryArray {
			heap.enqueue(element)
		}
	}
	return newArray;
}

heap = Heap<Int>(elements: [1,2,3,4,5], priorityFunction: >)
//print(heap.elements)

//print(findMaxProduct(arr: [1,2,3,4,5]))
//print(findMaxProduct(arr:  [2, 1, 2, 1, 2]))