Heaps

Heaps are data structures designed to quickly find and extract the maximum (or minimum) value in a collection. A typical use-case for heaps is to process a series of incoming tasks in order of maximum priority.

One can theoretically use a sorted list using the tools in the bisect module; however, while extracting the maximum value will take O(1) time (using list.pop), insertion will still take O(N) time (remember that, even if finding the insertion point takes O(log(N)) time, inserting an element in the middle of a list is still a O(N) operation). A heap is a more efficient data structure that allows for insertion and extraction of maximum values with O(log(N)) time complexity.

In Python, heaps are built using the procedures contained in the heapq module on an underlying list. For example, if we have a list of 10 elements, we can reorganize it into a heap with the heapq.heapify function:

    import heapq

    collection = [10, 3, 3, 4, 5, 6]
    heapq.heapify(collection)

To perform the insertion and extraction operations on the heap, we can use the heapq.heappush and heapq.heappop functions. The heapq.heappop function will extract the minimum value in the collection in O(log(N)) time and can be used in the following way:

    heapq.heappop(collection)
    # Returns: 3

Similarly, you can push the integer 1, with the heapq.heappush function, as follows:

    heapq.heappush(collection, 1)

Another easy-to-use option is the queue.PriorityQueue class that, as a bonus, is thread and process-safe. The PriorityQueue class can be filled up with elements using the PriorityQueue.put method, while PriorityQueue.get can be used to extract the minimum value in the collection:

    from queue import PriorityQueue

    queue = PriorityQueue()
    for element in collection:
        queue.put(element)

    queue.get()
    # Returns: 3

If the maximum element is required, a simple trick is to multiply each element of the list by -1. In this way, the order of the elements will be inverted. Also, if you want to associate an object (for example, a task to run) to each number (which can represent the priority), one can insert tuples of the (number, object) form; the comparison operator for the tuple will be ordered with respect to its first element, as shown in the following example:

    queue = PriorityQueue()
    queue.put((3, "priority 3"))
    queue.put((2, "priority 2"))
    queue.put((1, "priority 1"))

    queue.get()
    # Returns: (1, "priority 1")