Heap

A heap is a specialized tree-based data structure that satisfies the heap property: in a max-heap, for any given node I, the value of I is greater than or equal to the values of its children, while a min-heap has the value of I less than or equal to its children. Heaps are commonly implemented as arrays.

Common applications include:

• Priority queues
• Heap sort algorithm
• Finding kth largest/smallest elements
• Implementing efficient graph algorithms (Dijkstra's)

Time Complexities

• Insert element: O(log n)
• Delete element: O(log n)
• Get min/max element: O(1)
• Build heap from array: O(n)
• Heapify (fix heap property): O(log n)
• Search for element: O(n)