# -*- coding: utf-8 -*-
from __future__ import unicode_literals


class BinHeap(object):

    def __init__(self, iterable=None):
        self.list = []
        if iterable:
            for item in iterable:
                self.push(item)

    def push(self, value):
        self.list.append(value)
        self._bubble_up(len(self.list) - 1)

    def _bubble_up(self, index):
        if self.list[index] < self.list[(index - 1) // 2]:
            self.list[index], self.list[(index - 1) // 2] = self.list[(index - 1) // 2],
            self.list[index]
            self._bubble_up((index - 1) // 2)

    def pop(self):
        return_val = self.list[0]
        self.list[0] = self.list.pop()
        self._bubble_down(0)
        return return_val

    def _bubble_down(self, index):
        child = None
        if self.list[2 * index + 1] > self.list[2 * index + 2]:
            child = 2 * index + 2
        else:
            child = 2 * index + 1

        if self.list[index] < self.list[child]:
            self.list[index], self.list[child] = self.list[child], self.list[index]
            self._bubble_down(child)

add binheap