The Heap Data Structure
Overview
- Resembles a binary tree when drawn.
- Is ordered based on minimum or maximum values.
- A custom comparable can be used in Java for other comparisons.
- In the context of min or max, either the min or the max respectively is at the root.
- Can be represented as an array as well.
- The tree is near full except for missing nodes in the lowest level on the right-hand side.
- The height of a heap is log(n), where n is the number of the nodes in the tree.
- Relational indices can be calculated for parent nodes and their children.
- Elements can be user-defined data types and structures, or user-defined data structures.
When to use heaps
- When you need to sort a list (heap sort)
- When using priority queues.
- When there is a priority associated with a custom sorting comparable
- When the level of a given node is important.
- This is known as leveling.
- When data is coming in and you want to sort it along the way
Heapification
Heapification is when a heap is rearranged to maintain the heap property1. In the context of a max heap, this means that each node is greater than all of its children.
The HeapSort Algorithm
This algorithm utilizes a binary head, or a heap whose nodes each have two children nodes (with the possible exception of the penultimate level). The steps2 are as follows:
- Build a max heap from the input data.
- Replace the root of the heap (which happens to contain the largest item) with the last item of the heap.
- Reduce the size of the heap by 1, then heapify the root of the tree.
- Repeat steps 1-3 as long as the size of the heap is >1.
Once the algorithm breaks, the input data will be sorted!
Time Complexity
| Operation | Time Complexity |
|---|---|
| Heapify | O(log(n)) |
| Insert | O(log(n)) |
| Delete | O(log(n)) |
| Building a Heap | Simple Bound: O(n log(n)) |
| Building a Heap | Tight Bound3 : O(n) |
Heap Review
Check out GeeksforGeek’s Heap Quiz to review heap-related properties and concepts.