 //
 //  Heap.swift
-//  Min-heap
+//  Binary min-heap.
 //
 //  Created by Vyacheslav Khorkov on 18/08/2017.
 //  Copyright © 2017 Vyacheslav Khorkov. All rights reserved.

		return nil
	}
	
	// Swaps two values by their indexes.
	// Complexity: O(1)
	private mutating func swap(_ i: Int, _ j: Int) {
		Swift.swap(&a[i], &a[j])
	}
	
	// Returns the parent value of child.
	// Complexity: O(1)
	private func parent(_ child: Int) -> T? {
		let i = parentIndex(child)
		guard i >= 0 && i < a.count else { return nil }
		return a[i]
	}
	
	// Returns the left child value of parent.
	// Complexity: O(1)
	private func left(_ parent: Int) -> T? {
		let i = leftIndex(parent)
		guard i < a.count else { return nil }
		return a[i]
	}
	
	// Returns the right child value of parent.
	// Complexity: O(1)
	private func right(_ parent: Int) -> T? {
		let i = rightIndex(parent)
		guard i < a.count else { return nil }
		return a[i]


import Foundation

// Binary min-heap.
public struct Heap<Element: Comparable>: CustomDebugStringConvertible {
	// Return min element from heap.
	// Complexity: O(1)
	public var min: Element? { return a.first }
	
	// Returns true if heap is empty.
	// Complexity: O(1)
	public var isEmpty: Bool { return a.isEmpty }
	
	// Returns the count of elements.
	// Complexity: O(1)
	public var count: Int { return a.count }
	
	// Build heap with array.
	// Complexity: O(n)
	public init(_ a: [Element] = []) {
		build(a)
	}
	
	// Deletes and returns a minimum element from heap.
	// Complexity: O(log n)
	public mutating func extractMin() -> Element? {
		guard !isEmpty else { return nil }
		guard count > 1 else { return a.removeLast() }
		swap(0, a.count - 1)
