Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching, Third Edition

Chapter Nine. Priority Queues and Heapsort

Many applications require that we process records with keys in order, but not necessarily in full sorted order and not necessarily all at once. Often, we collect a set of records, then process the one with the largest key, then perhaps collect more records, then process the one with the current largest key, and so forth. An appropriate data structure in such an environment supports the operations of inserting a new element and deleting the largest element. Such a data structure is called a priority queue. Using priority queues is similar to using queues (delete the oldest) and stacks (delete the newest), but implementing them efficiently is more challenging. The priority queue is the most important example ...