import random

class PriorityQueue(object):
    
    '''Implementation of a Priority Queue using a Heap.'''
    
    def __init__(self):
        '''Create an empty heap.'''
        self.heap = []
        
    def build_heap(self, new_list):
        '''Populate the heap with the elements of new_list (and only those
        elements).'''
        self.heap = new_list[:]
        for i in range(len(new_list) - 1, -1, -1):
            self._sink(i)
        
    def insert(self, x):
        '''Add x to the heap.'''
        self.heap.append(x)
        i = len(self.heap) - 1
        # Small values float to the top...
        while i > 0 and self.heap[i] < self.heap[(i - 1) / 2]:
            t = self.heap[i]
            self.heap[i] = self.heap[(i - 1) / 2]
            self.heap[(i - 1) / 2] = t
            i = (i - 1) / 2
            
    def min(self):
        '''Return the smallest element in the heap.'''
        return self.heap[0]

    def _sink(self, i):
        '''Recursively fix the heap property violated by extract_min at
        position i.'''
        left = 2 * i + 1
        right = 2 * i + 2
        smallest = i
        if left < len(self.heap) and self.heap[smallest] > self.heap[left]:
            smallest = left
        if right < len(self.heap) and self.heap[smallest] > self.heap[right]:
            smallest = right
        if smallest != i:
            t = self.heap[i]
            self.heap[i] = self.heap[smallest]
            self.heap[smallest] = t
            self._sink(smallest)
    
    def extract_min(self):
        '''Return and remove the smallest element in the heap.'''
        ret = self.heap[0]
        # Move last node to the root.
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        self._sink(0)
        return ret
        
    def size(self):
        '''Return the size of the heap.'''
        return len(self.heap)
        
if __name__ == '__main__':
    items = range(20)
    random.shuffle(items)
    pq = PriorityQueue()
    pq.build_heap(items)
    items_sort = []
    while pq.size() > 0:
        items_sort.append(pq.extract_min())
    print items
    print items_sort