A priority queue: the binary heap - Data Structures and Problem Solving Using Java - page 834

key concepts

binary heap The classic method used to implement priority queues. The binary
heap has two properties: structure and ordering. (808)
buildHeap operation The process of reinstating heap order in a complete tree,
which can be done in linear time by applying a percolate down routine to
nodes in reverse level order. (818)
complete binary tree A tree that is completely filled and has no missing nodes.
The heap is a complete binary tree, which allows representation by a simple
array and guarantees logarithmic depth. (809)
external sorting A form of sorting used when the amount of data is too large to
fit in main memory. (826)
heap-order property States that in a (min) heap, the item in the parent is never
larger than the item in a node. (810)
heapsort An algorithm based on the idea that a priority queue can be used to
sort in O ( N log N ) time. (823)
implicit representation Using an array to store a tree. (809)
max heap Supports access of the maximum instead of the minimum. (811)
multiway merge K -way merging that reduces the number of passes. The obvi-
ous implementation uses 2 K tapes. (829)
percolate down Deletion of the minimum involves placing the former last item
in a hole that is created at the root. The hole is pushed down the tree
through minimum children until the item can be placed without violating
the heap-order property. (816)
percolate up Implements insertion by creating a hole at the next available
location and then bubbling it up until the new item can be placed in it
without introducing a heap-order violation with the hole's parent. (814)
polyphase merge Implements a K -way merge with K + 1 tapes. (830)
replacement selection The length of the runs initially constructed can be larger
than the amount of available main memory. If we can store M objects in
main memory, then we can expect runs of length 2 M . (832)
run A sorted group in the external sort. At the end of the sort, a single run
remains. (827)

common errors

The trickiest part of the binary heap is the percolate down case in which
only one child is present. This case occurs rarely, so spotting an incorrect
implementation is difficult.

1.