#![allow(dead_code)]
pub(crate) struct PriorityQueue<T: std::cmp::PartialOrd> {
    size: usize,
    content: Vec<T>,
}

impl<T: std::cmp::PartialOrd> PriorityQueue<T> {
    pub fn new() -> Self {
        Self {
            size: 0,
            content: Vec::new(),
        }
    }

    pub fn initialize(&mut self) {
        self.size = 0;
        self.content = Vec::new();
    }

    pub fn is_empty(&self) -> bool {
        self.size == 0
    }

    pub fn insert(&mut self, item: T) {
        self.content.push(item);
        let mut cur = self.size;
        let mut par;
        while cur != 0 {
            par = (cur - 1) / 2;
            if self.content[cur] < self.content[par] {
                self.content.swap(cur, par);
                cur = par;
            } else {
                break;
            }
        }
        self.size += 1;
    }

    pub fn peek(&self) -> Option<&T> {
        if self.is_empty() {
            return None;
        }
        Some(&self.content[0])
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.is_empty() {
            return None;
        }
        let ret = self.content.swap_remove(0);
        let mut cur = 0;
        let mut nc;
        self.size -= 1;
        while cur < self.size {
            let lc = cur * 2 + 1;
            let rc = cur * 2 + 2;
            if lc >= self.size {
                break;
            } else if rc >= self.size {
                nc = lc;
            } else {
                nc = if self.content[lc] < self.content[rc] {
                    lc
                } else {
                    rc
                };
            }
            if self.content[nc] < self.content[cur] {
                self.content.swap(cur, nc);
                cur = nc;
            } else {
                break;
            }
        }
        Some(ret)
    }
}
