Python Data Types

Data Types Heap Queue algorithm

priority queue algorithm

Heap:  
 binary trees which every parent node has a value less than or equal to any of its children. 

 implementation uses arrays for which heap[k] <= heap [2*k+1] and  heap(k) <= heap[2*k+2] for all k, counting elements form zero. 

our pop method returns the smallest item, not the largest(mini heap; max heap is more common because of sorting. 

heapq.heappush(heap, item)
    push the value item onto the heap, maintaining the heap invariant.

heapq.heapop(heap)
   Pop the return the smallest item from the heap, maintaining the heap invariant.  if the heap is empty, indexerror is raised.  To access the smallest item wihtout popping it, use heap[0].

invariant: never changing
-------------------------------------------------------------------------------------------------------------------------------------------------------------------


import heapq

class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        heapq.heappush(self._queue, (-priority, self._index, item))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]


---------------------------------------------------------------------------------------------------------------------------------------------------------------------