Heaps

  • Tree structure with heap property: If p is parent of c, then key of p is ⇐ key of c (min-heap) or key of p >= key of c (max-heap).
  • Max. efficient implementation of priority queue.
  • Useful if element with highest/lowest value needs to be removed
  • Number of nodes is at least $n = 2h + 1$
  • Perfect balanced tree $h = ceil(log_2(n+1))$
  • PriorityQueue in Java

Implementation data structure

* Array for a binary heap

// i:0 => 0
// i:1 => 0
// i:2 => 1 => 0
// i:3 => 1 => 0
// i:4 => 2 => 1 => 0
// i:5 => 2 => 1 => 0
// i:6 => 3 => 1 => 0
// i:7 => 3 => 1 => 0
// i:8 => 4 => 2 => 1 => 0
// i:9 => 4 => 2 => 1 => 0
// i:10 => 5 => 2 => 1 => 0
//       0
//       |
//       1
//      / \
//     /   \
//    2     3
//   / \   / \
//  4   5 6   7
// parent
protected int parentIndex(int i) {
  return i / 2;
}