Next:
Preface
Up:
Heap implementations and variations
Previous:
Heap implementations and variations
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 ...
Jesper Bojesen
Sat Apr 3 18:07:59 METDST 1999