Heap Basics

Heap is a tree data structure with a hierarchical collection of nodes. In a Max Heap is usually a Binary Tree where the parent node data value is always greater than its child nodes at all levels. Conversely in a Min Heap is usually a Binary Tree where the parent node data value is always lesser than its child nodes at all levels.

The diagram below shows a Max Heap:

Types of Heaps

•	Max Heap (described above).
•	Min Heap (described above).
•	Binary Heap: Heap based on Binary Tree.
•	N-ary Heap : Heap based on N-ary Tree.
•	Binomial Heap : It’s a collection of binomial trees.
•	Fibonacci Heap : A specific structured heap that is optimized for operations such as decrease-key.

Use cases for Heaps

When your algorithm needs to access maximum or minimum element very quickly.

Used for implementing Priority Queues.

Used in Heapsort Algorithm.

While looking for kth largest or smallest element.

Time Complexity of Heap data Structure

Following table shows time complexity metrics for Heap operations:

Operation	Complexity
Insert operation.	O(log n)
Remove/Delete operation.	O(log n)
Get Max element (Max Heap).	O(1)

Heap in Java JDK API.

Java API provides PriorityQueue which is implemented by a Heap. It can be used as both Max Heap and Min Heap based on Comparator provided to the constructor while instantiating the PriorityQueue. Below code challenges provide a custom Heap implementation.