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

Have the PriorityQueue support decreaseKey as follows: Define a nested
class that implements PriorityQueue.Position . The binary heap will be
represented by an array of objects, in which each object stores a data item
and its index. Each PriorityQueue.Position object stores a reference
back to the corresponding object in the array.

21.30

references

The binary heap was first described in the context of heapsort in [8]. The
linear-time buildHeap algorithm is from [4]. Precise results on the number of
comparisons and data movements used by heapsort in the best, worst, and
average case are given in [7]. External sorting is discussed in detail in [6].
Exercise 21.18 is solved in [5]. Exercise 21.19 is solved in [2]. Exercise 21.20
is solved in [3]. Treaps are described in [1].

1.

C. Aragon and R. Seidel, “Randomized Search Trees,” Algorithmica 16
(1996), 464-497.

2.

M. D. Atkinson, J. R. Sack, N. Santoro, and T. Strothotte, “Min-Max
Heaps and Generalized Priority Queues,” Communications of the ACM 29
(1986), 996-1000.

3.

Y. Ding and M. A. Weiss, “The k-d Heap: An Efficient Multi-dimensional
Priority Queue,” Proceedings of the Third Workshop on Algorithms and
Data Structures (1993), 302-313.

4.

R. W. Floyd, “Algorithm 245: Treesort 3,” Communications of the ACM 7
(1964), 701.

5.

D. B. Johnson, “Priority Queues with Update and Finding Minimum
Spanning Trees,” Information Processing Letters 4 (1975), 53-57.

6.

D. E. Knuth, The Art of Computer Programming. Vol. 3: Sorting and
Searching , 2nd ed., Addison-Wesley, Reading, MA, 1998.

R. Schaffer and R. Sedgewick, “The Analysis of Heapsort,” Journal of
Algorithms 14 (1993), 76-100.

7.

J. W. J. Williams, “Algorithm 232: Heapsort,” Communications of the
ACM 7 (1964), 347-348.

8.