Heap Datastructures- Detailed Explanation in Python.

What are heap data structures?

When a binary tree is complete, it is a special binary tree where every parent node has a value lesser than or equal to any of its children.

This implementation uses an array for which, heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] for all k, counting elements from zero

The smallest element in a heap is always the root.(heap[0])

There are two types of the heap, Max-Heap and Min Heap.

In a Max-Heap the key present at the root node must be greatest among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree.

In a Min-Heap the key present at the root node must be minimum among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree.

Let the size of heap be N and height be h
If we take few examples, we can actually make a note that the value of h in a heap(complete Binary Tree) is ceil(log2(N+1)) — 1.

To create a heap, use a list initialized to [], or you can transform a populated list into a heap via function heapify()

The following functions are provided:

Push the item as value to the heap.

Pop and return the smallest item from the heap, maintaining the heap invariant. If the heap is empty, IndexError is raised. To access the smallest item without popping it, use heap[0].

Push item on the heap, then pop and return the smallest item from the heap. The combined action runs more efficiently than heappush() followed by a separate call to heappop().

Transform list x into a heap, in-place, in linear time.

Pop and return the smallest item from the heap, and also push the new item. The heap size doesn’t change. If the heap is empty, IndexError is raised.

Merge multiple sorted inputs into a single sorted output (for example, merge timestamped entries from multiple log files). Returns the iterator over the values.

Return a list with the n largest elements from the dataset defined by iterable. key, if provided, specifies a function of one argument that is used to extract a comparison key from each element in iterable (for example, key=str.lower). Equivalent to: sorted(iterable, key=key, reverse=True)[:n].

Return a list with the n smallest elements from the dataset defined by iterable. key, if provided, specifies a function of one argument that is used to extract a comparison key from each element in iterable (for example, key=str.lower).

Implementation of Heapsort using Heapq Datastructre by pushing all values onto a heap and then popping off the smallest values one at a time.

Next Article, we will discuss Priority Queues

--

--

I write about Software Engineering, Backend Development, Algorithmic Trading, Quantitative Finance, and our Mind and Universe.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Balaji MJ

I write about Software Engineering, Backend Development, Algorithmic Trading, Quantitative Finance, and our Mind and Universe.