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 $\leq n$ .
Max Heap: for any node $n$ , its parent $p$ is $\geq 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:

Operation	Time Complexity	Space Complexity	Syntax
Size	$O (1)$	$O (1)$	`len(heap)`
Heapify¹	$O (n)$	$O (n)$	`heapq.heapify(lst)`
Minimum	$O (l o g (n))$	$O (1)$	`min_heap[0]`
Maximum	$O (l o g (n))$	$O (1)$	`max_heap[0]`

Usage

Check the heap section in the Python cheatsheet.

References

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

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

algo-ds.com

Heaps

Operations

Usage

References