#!/usr/bin/python
# -*- coding: utf-8 *-*

class HeapError(IndexError):
    pass

class Heap(object):
    """Un tas est un arbre binaire presque équilibré dans lequel tout noeud a
    une valeur inférieure à celles de ses fils.

    L'hypothèse de presque équilibrage permet d'implémenter l'arbre par un
    tableau : les éléments sont listés en partant de la racine (d'index 0 dans
    le tableau) et en parcourant l'arbre étage par étage, de gauche à droite ;
    le fils gauche d'un noeud d'index i se trouve donc à l'index 2i + 1, le
    fils droit à l'index 2i + 2 et le père à l'index (i - 1)/2. Le dernier
    noeud (le plus à droite du dernier étage de l'arbre) est le dernier élément
    du tableau."""

    def __init__(self, l = ()):
        """Initialisation d'un tas : l est une liste de valeurs à stocker dans
        le tas."""

        self.table = [] # le tableau représentant l'arbre
        self.size = 0   # la taille du tas

        # on ajoute un par un les éléments de l ; la méthode push() garantit
        # que les éléments seront insérés dans l'arbre de façon à respecter la
        # propriété de tas
        for v in l:
            self.push(v)

    def push(self, val):
        """Ajout d'une valeur val dans le tas : on commence par placer la
         valeur en fin de tas, puis on la fait descendre le long de la branche
         de l'arbre de façon à respecter la propriété de tas"""

        index = self.size      # index de la nouvelle valeur, en fin de tas
        self.table.append(val) # ajout de la nouvelle valeur, en fin de tas
        self.size += 1

        # descente de la nouvelle valeur le long de sa branche
        while index > 0:
            father_index = (index - 1)/2
            father = self.table[father_index]
            if father <= val:
                # nous sommes arrivé à destination
                break
            else:
                # il faut continuer à descendre
                self.table[index] = father
                self.table[father_index] = val
                index = father_index

    def pop(self):
        """Suppression de la valeur à la racine du tas : on supprime le dernier
        élément du tas après avoir sauvé sa valeur à la racine, puis on percole
        pour redisposer cette valeur à sa place"""

        if len(self.table) == 0:
            # erreur : on ne peut pas supprimer un élément d'un tas vide
            raise HeapError("Tas vide")

        # on mémorise la valeur de la racine avant de la supprimer de l'arbre
        popped_val = self.table[0]

        # on copie la valeur du dernier élément à la racine, puis on efface ce
        # dernier élément
        last_index = self.size - 1
        self.table[0] = self.table[last_index]
        del(self.table[last_index])
        self.size = last_index

        # on percole (s'il reste des éléments dans le tas)
        if self.size > 0:
            self.percolate(0)

        # et on retourne la valeur supprimée
        return popped_val

    def percolate(self, index):
        """Percolation : la valeur localisée au noeud identifié par index n'est
        pas à sa place mais les deux sous-arbres sont des tas ; il faut faire
        monter la valeur pour respecter la propriété de tas"""

        current = self.table[index] # valeur courante
        left_index = 2*index + 1    # index du fils gauche
        right_index = 2*index + 2   # index du fils droit

        if right_index < self.size:
            # nous avons deux sous-arbres
            left = self.table[left_index]   # valeur du fils gauche
            right = self.table[right_index] # valeur du fils droit

            # doit on faire monter la valeur courante, et de quel côté ?
            if left < current and left <= right:
                # oui, à gauche
                self.table[left_index] = current
                self.table[index] = left
                # et on continue avec le fils gauche
                self.percolate(left_index)

            elif right < current and right <= left:
                # oui, à droite
                self.table[right_index] = current
                self.table[index] = right
                # et on continue avec le fils droit
                self.percolate(right_index)

            # else: la valeur courante est déjà à sa place

        elif left_index < self.size:
            # nous avons un seul sous-arbre ; à cause de l'équilibrage c'est le
            # fils gauche et c'est une feuille

            left = self.table[left_index] # valeur du fils gauche

            # doit on faire monter la valeur courante ?
            if left < current:
                # oui
                self.table[left_index] = current
                self.table[index]  = left
                # il n'y a plus rien à faire puisque le fils gauche est une
                # feuille, la valeur ne montera pas plus haut

            # else: la valeur courante est déjà à sa place