Binary heap

• 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
  • com.google.common.collect.MinMaxPriorityQueue (API doc)
  • org.apache.commons.collections.BinaryHeap (API doc)
• Applications of binary heap
  • Heap sort an array (O(nLogn) time complexity)
  • Used for implementing priority queues.

Check the heap sort implementation in java.