A heap is a specialized tree-based data structure in computer science that satisfies the heap property. This is an abstract data type that can be visualized as a binary tree.
In a heap data structure, the heap property is primarily of two types:
- **Max-Heap**: In a max-heap, for any given node I, the value of I is greater than or equal to the values of its children.
Parent node value ≥ Child node values
- **Min-Heap**: In a min-heap, for any given node I, the value of I is less than or equal to the values of its children.
Parent node value ≤ Child node values
Heap data structures are mainly used to implement priority queues (efficiently finding or accessing the maximum OR minimum element of a queue), where elements with higher importance are prioritized before elements with lower importance. It has a wide range of applications such as load balancing, scheduling tasks in operating systems or in algorithms such as Heapsort and Dijkstra’s algorithm for finding the shortest path in a graph.
In the max-heap shown above, for any given node i.. the value of i is larger than or equal to the values of its children. It’s the opposite in a min-heap.
Here are some important operations in a binary heap and their time complexities:
- **insert**: Insert a new key. (O(logN))
- **getMax or getMin**: Returns the root. (O(1))
- **extractMax or extractMin**: Removes and returns the root. (O(logN))
- **deleteKey**: Deletes a key from the heap. (O(logN))