- Binary heap
- Is a complete binary tree (binary tree that has all intermediate nodes with 2 children except last level where keys are aligned to left).
- Max binary heap – Root element is greater than the left and the right children recursively to all nodes.
- Min binary heap – Root element is smaller than the left and right children recursively to all nodes.
- Good link on basics of heap – http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm
- As binary heap is a complete binary tree, it can be represented in an array using level order traversal.
- More details http://quiz.geeksforgeeks.org/array-representation-of-binary-heap/
- If the parent node is stored at index i, the left child can be calculated by 2 * i + 1 and right child by 2 * i + 2.
- Operations
- Get top – Min / Max.
- Insert
- Delete.
- Heapify – When changing the structure by insertion or deletion, it’s important to heapfiy the tree so that binary heap constraints are not violated.
- Details of heapification http://quiz.geeksforgeeks.org/heap-sort/
- Java implementation of priority queue using maxmin binary heap is available with Google Guava library
- Applications of binary heap
- Heap sort an array (O(nLogn) time complexity)
- Used for implementing priority queues.
Check the heap sort implementation in java.