What is a heap?

A heap is a special tree-based data structure that satisfies the heap property. This property states that for any given node (except the root), the value of the node's key must be in a specific relation to the value of its parent's key. There are two main types of heaps:

• Max-heap: The key value of each node is greater than or equal to the key values of its children. The maximum element is at the root.
• Min-heap: The key value of each node is less than or equal to the key values of its children. The minimum element is at the root.

Heaps are usually implemented as arrays, which allows efficient access to elements and operations. The relationship between parents and children in the array is as follows:

• For an element with index i (starting from 0), its left child is at index 2i + 1.
• Its right child is at index 2i + 2.
• Its parent is at index floor((i - 1) / 2).

Main operations on heaps:

• Insert: Adding a new element. Time complexity O(log n), where n is the number of elements.
• Extract-Max / Extract-Min: Removing and returning the maximum (in max-heap) or minimum (in min-heap) element. Time complexity O(log n).
• Heapify: Transforming an arbitrary array into a heap. Time complexity O(n).

Heaps are used in sorting algorithms (e.g., heapsort), priority queues, and shortest path algorithms (e.g., Dijkstra's algorithm).