Python Heap Sorting

Python Heap Sorting

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

AUTHER = 'ArianX'
GITHUB = 'https://github.com/arianxx'
BLOG = 'https://arianx.me'


class Heap:
    def __init__(self, nodes=None, compare=None):
        self.size = 0
        self._heap = []

        if compare:
            self.compare = compare

        if nodes:
            self.build_heap(nodes)

    @property
    def top(self):
        return self._heap[0] if self._heap else None

    def compare(self, key1, key2):
        return key1 >= key2

    def parent(self, index):
        return index and (index - 1) // 2

    def max_child(self, index):
        if index * 2 + 1 > self.size - 1:
            return None
        elif index * 2 + 2 > self.size - 1:
            return index * 2 + 1
        else:
            if self.compare(self._heap[index * 2 + 1],
                            self._heap[index * 2 + 2]):
                return index * 2 + 1
            else:
                return index * 2 + 2

    def heap_up(self, index):
        parent = self.parent(index)
        while True:
            if not self.compare(self._heap[parent], self._heap[index]):
                self._heap[parent], self._heap[index] = \
                    self._heap[index], self._heap[parent]
            else:
                break
            index = parent
            parent = self.parent(index)

            if index == parent:
                break

    def heap_down(self, index=0):
        while True:
            child = self.max_child(index)
            if not child:
                break
            else:
                if self.compare(self._heap[child], self._heap[index]):
                    self._heap[child], self._heap[index] = \
                        self._heap[index], self._heap[child]
                    index = child
                else:
                    break

    def insert(self, node):
        self._heap.append(node)
        self.size += 1
        self.heap_up(self.size - 1)

    def build_heap(self, nodes):
        self._heap = iter(nodes)
        self.size = len(self._heap)
        for index in range(self.size - 1, -1, -1):
            self.heap_up(index)

    def extract(self):
        top = self._heap[0]
        self._heap[0] = self._heap[self.size - 1]
        self.heap_down(0)
        self._heap.pop()
        self.size -= 1
        return top