Heap implementations and variations

Jesper Bojesen

October 1998
DIKU
University of Copenhagen

• Contents
• Preface
• Heaps - A Priority queue data structure
  • The Heap data structure
  • Implicit Heaps
    • Insert element.- The siftup procedure
    • Delete max element.- The siftdown procedure
  • A note on terminology
  • Building a heap
  • Heapsort
• The MinMax Heap. A double ended priority queue
  • The siftup procedure
  • The siftdown procedure
  • Comparison of the Min-Max and the basic heaps.
• Dynamic Heaps. A flexible priority queue
  • The data structure
  • Performance of the dynamic heap
• Tuning the cache behavior of implicit heaps. D-heaps
  • Motivation.- Performance of the implicit heap
  • Analysis
  • Programming considerations
  • Performance of D-heaps
• The External Heapsort
  • The data structure of external heaps
  • The external siftdown procedure
  • The internal cost of external heaps
  • Implementing the external heapsort
    • Making the external heapsort practical.
    • Performance tuning. Improving the constants
      • Avoiding merges
      • Tuning the page size
    • Heaps with holes
      • The heap property
  • Performance of the external heapsort
  • External heaps as priority queues
  • Summary
    • A Hackers guide to (external) heap configurations.
    • What external heaps can not do
• B-heaps
  • The data structure
  • Node refill strategy
  • Selecting the fanout
  • The insert operation
• Heap lab users guide
  • Makefile and directory structure
    • Top level make rules
    • How to move heaplab to a new machine
  • How to add a new heap implementation
    • Driver programs
      • build_driver.cc
      • sort_driver.cc
      • count_driver.cc
      • debug_driver.cc
      • pq_driver.cc
    • Useful scripts
      • sortdrive.sh
      • pqdrive.sh
      • speedup.sh
  • Heap implementations
    • basic/
    • minmax/
    • dynamic/
    • basic3/-4/-8/
    • extsort1/
    • extsort3/
    • extpq/
    • exthole/
• References
• About this document ...