Efficient Heaps for RAM model

• Implemented in arrays such that:

  • parent(I)=I/2
  • left(I)=2I
  • right(I)=2I+1

• Use Floyd’s algorithm rather than repeated adds to improve the instruction count.

• Use binary heaps and not d-ary heaps as d-ary heaps are inefficient because of more comparisons.

Previous slide

Next slide

Back to first slide

View graphic version