use std::cmp::{max, Ordering};

/// An implicit binary heap that can efficiently find the min or max of its contained elements.

/// - Find min / find max: `O(1)`

/// - Pop min / pop max: `O(log(n))`

/// - Push: `O(log(n))`

/// - Heapify: `O(n)`

/// The comparison function can be changed after creation by just calling [`MmHeap::ify_by`] again.

/// Rust's standard [`std::collections::BinaryHeap`] claims an `O(1)` average complexity for push,

/// but as it notes in the documentation this is amortized over a randomly ordered sequence.

/// This heap is also a binary heap so for a randomly ordered sequence it could also be considered `O(1)`,

/// but for this, the standard binary heap, and indeed any binary heap, the worst case insertion time

/// is `O(logn)`.  Also, when a min (or minmax) heap is used to find the `m` largest elements in a large sequence of `n > m`

/// elements or visa versa, the expected cost of insertion drops from `1 - m/2^m` to ... even lower.

pub struct MmHeap<T> {

    buf: Vec<T>

}

impl<T> MmHeap<T> {

	/// Create an empty MmHeap

	/// Create an MmHeap out of a vector and immediately heapify it according to cmp

	/// Note that cmp takes references, which means the common case of storing references

	/// in the heap can require wrapping the comparison function since it will have to take

	/// references to references

    pub fn make(buf: Vec<T>, cmp: &impl Fn(&T, &T) -> Ordering) -> Self {

        let mut res = Self{buf};

        res.ify_by(cmp);

        res

    }

	/// Reorder the heap according to a new comparison function.

	/// It's impossible to add to the heap's private buffer directly, so this is only necessary

	/// when changing the comparison function.  When calling [`Self::push_by`] etc with the same comparison

	/// function, the heap will maintain its invariant

    pub fn ify_by(&mut self, cmp: &impl Fn(&T, &T) -> Ordering) {

        let nonleaf_idx_upper_bound = (usize::MAX >> 1) >> self.buf.len().leading_zeros();

        for i in (0..nonleaf_idx_upper_bound).rev()

            { self.sift_down_by(i, cmp) }

    }

	/// Get the number of elements in the heap

	/// Get the minimum element without removing it

    pub fn peek_min(&self) -> Option<&T> {

        self.buf.first()

    }

	/// Get the maximum element without removing it

        }

        // nodes with index i will be in layer n where 2^n is the maximal power of 2 <= i + 1,

        // so we can check if n is odd/even by checking if the number of leading zeros in (i + 1)

        // is odd/even.  In odd layers, nodes should be >= their descendents, and in even layers, <=.

        }

            // Find m, the index of the extremal element among the children and grandchildren

            // of the element at index i. For min layers, extremal means

            // minimal, and for max layers it means maximal

            }

            // If m is a grandchild of i (as should be the case most of the time)

            // we may have to sift down farther after fixing up here

            } else {// otherwise em is a direct child so it must be a leaf or its invariant would be wrong

            }

        }

	/// Insert an element into the heap

	/// Elements that compare equal are fine, but their order will be unspecified

	/// Get the minimal element and remove it

    pub fn pop_min_by(&mut self, cmp: &impl Fn(&T, &T) -> Ordering) -> Option<T> {

        self.pop_idx_by(0, cmp)

    }

	/// Get the maximal element and remove it

        }

	/// Insert a new element and remove the min element in the resulting heap in a single operation

	/// Could be faster than [`Self::push_by`]` + [`Self::pop_min_by`] separately

	/// (the current implementation is only more efficient if the heap is empty, but it will always

	/// be at least as good)

    pub fn pushpop_min_by(&mut self, e: T, cmp: &impl Fn(&T, &T) -> Ordering) -> T {

        if self.buf.is_empty() { e } else {

            self.push_by(e, cmp);

            self.pop_min_by(cmp).unwrap()

        }

    }

	/// Insert a new element and remove the max element in the resulting heap in a single operation

        }

    /// Add all elements yielded from an iterator

    /// This is the same functionality provided by the [`Extend`] trait, except we need an additional

    /// argument (cmp) so we cannot implement that trait

        }

}

impl<'a, T> IntoIterator for &'a MmHeap<T> {

    type Item = &'a T;

    type IntoIter = <&'a Vec<T> as IntoIterator>::IntoIter;

    fn into_iter(self) -> Self::IntoIter {

        (&self.buf).into_iter()

    }

}

impl<T> Into<Vec<T>> for MmHeap<T> {

}