Priority Queues with Binary Heaps

Build and run algorithms on Priority Queues (as binary heaps) with just a few lines of code with AKDSFramework.

Priority Queues with Binary Heaps

I’m starting a data structure series where I introduce you to popular data structures and their implementations. I'll start with Priority Queues with Binary Heaps.

One of my favorite data structure is binary heaps. In this article I'll show you what is heap and how to make one with python and in the end I'll show you sorting technique that we can get for free just by building a heap.

What are priority queues?

A priority queue is a queue where the most important element is always at the front. The queue can be a max-priority queue (largest element first) or a min-priority queue (smallest element first).

So as a data structure designer you have the following options to design a priority queue:

  • An max sorted array or min-sorted array, but downside is inserting new items is slow because they must be inserted in sorted order.
  • or an binary heap (max heap or min heap)

Now the question arises what are heaps? The heap is a natural data structure for a priority queue. In fact, the two terms are often used as synonyms. A heap is more efficient than a sorted array because a heap only has to be partially sorted. All heap operations are in the order of \(\log\) or linear.

Examples of algorithms that can benefit from a priority queue implemented as heap

  • Dijkstra's algorithm for graph searching uses a priority queue to calculate the minimum cost.
  • A* pathfinding for artificial intelligence.
  • Huffman coding for data compression. This algorithm builds up a compression tree. It repeatedly needs to find the two nodes with the smallest frequencies that do not have a parent node yet.
  • Heap sort.

Let's design some heap

First we need to design what our heaps should do design wise. It should have some APIs to

  1. Build an binary heap right from a unsorted pile of numbers.
  2. Add a new number while maintaining the heap property with few swaps
  3. Find a minimum or a maximum in the heap
  4. Can remove that minimum or maximum from the heap and rearrange the heap to maintain it's heap property.

With design of the heap software out of the way let's get to coding. I've built AKDSFramework which is a great resource for data structure and algorithm designs, I'll use my framework to show you building a heap.

Code

Let's first import heap class from AKDSFramework

from AKDSFramework.structure import MaxHeap, MinHeap

Now let’s build a max heap with 15 values.

mxheap = MaxHeap([data**2 for data in range(15)])

Now it’s important to call the build method on the heap to build the heap from an unsorted array of numbers. If the build is not done, printing and doing operations on heap will not be valid and will generate HeapNotBuildError. So always build your heap with .heap() method if you caused any change in the heap structure. Each time calling .build() method if there is one element of heap violation it will use \(O(\log n)\) time otherwise it's a linear operation for a n number of unordered elements.

mxheap.build()
# Now add few elements to the heap
mxheap.add(12)
mxheap.add(4)
# As the heap structure is changed so we have to call .build() again
mxheap.build()

Now let's see the heap in a beautiful structure which is easy to understand.

mxheap.prettyprint()

Now here is how the heap looks: Screen Shot 2021-01-07 at 5.51.47 PM.png

Similarly you can implement the min heap by yourself.

Heapsort

As you can see for a max heap every time after each build you'll get the maximum element from the head of the heap in constant \(O(1)\) time. And you build the heap everytime (n times) after removing the max item you'll have a sorted array sorted in \(O(n \log n)\) times.

Let's implement that with the help of min heaps:

I've already implemented heap sort with min heap in AKDSFramework

from AKDSFramework.applications.sorting import heapsort
import random


array = [random.randint(1, 100) for _ in range(10)]
print(heapsort(array, visualize=False))

This return the sorted array like this [23, 32, 37, 51, 55, 57, 59, 63, 78, 93]. Try to implement this by yourself if you get stuck here is a source code for implementing the heap sort with the built-in min heap API in AKDSFramework.

def heapsort(array, visualize=False):
    r"""
    Heapsort implementation with min heap from AKDSFramework. Running time: :math:`O(N \log (n))`
        Args:
            - ``array`` (list): List of elements
            - ``vizualize`` (bool): Marked as False by default. If you want to vizualize set this as True
    """
    if visualize:
        iteration = 0

    ret = []

    mnheap = MinHeap(array)
    mnheap.build()

    while len(mnheap) >= 1:
        if len(mnheap) == 1:
            ret.append(mnheap[0])
            break

        # O(1) time access of minimum element
        root = mnheap.get_root()
        ret.append(root)
        # O(log n) operation
        mnheap.delete_root()
        # Constant operation, deleting at the beginning,
        # by this time you need to call .build() again to 
        # rebuild the heap property
        mnheap.build()        # O(log N) for a single violation

        if visualize:
            print("-"*40)
            print(f'End of Iteration: {iteration}')
            print(f'Currently heap: {mnheap}')
            print(f'Our returning array: {ret}')

            iteration += 1

    return ret

More readings

If you want to implement heaps all by yourself I'd recommend you to check out the following resources:

Thanks for reading

If you find this helpful please subscribe to my newsletter. Please feel free to reach out to me on twitter.

Did you find this article valuable?

Support theroyakash by becoming a sponsor. Any amount is appreciated!