Heaps

A Heap is a Tree-based data structure that satisfies the heap property [1]:

• Min Heap: for any node $n$, its parent $p$ is $\le n$.
• Max Heap: for any node $n$, its parent $p$ is $\ge n$.

The Heap is an extremely efficient implementation of the Priority Queue abstract data type. In fact, priority queues are often simply called "heaps" regardless of their specific implementation [1].

A Priority Queue allows very similar operations compared to Queues, but with the difference that we can also assign a priority to the items, which could prioritize or de-prioritize the item based on its value.

Operations

Let's check the complexity of heaps' common operations:

Usage

Check the heap section in the Python cheatsheet.

References

• [1]: https://en.wikipedia.org/wiki/Heap_(data_structure)

1. Heapify is the process of converting a list into a heap. ↩