TAOCP #35 - Priority Queues

Top Of The Heap!

We saw in TAOCP #34 how a heap - a tree with of keys K_1, ..., K_N with the heap condition

--------------------- K_⌊j/2⌋ >= K_j for 1 <= ⌊j/2⌋ < j <= N -------------------

may be used to sort the keys in a guaranteed worst case time of O(N * log(N))

This time we look at priority queues - another application where heaps shine

Priority queues are convenient data structures for whenever data arrives in an unpredictable way but has to be processed in a known priority order. Priority may be time or distance or some measure of the importance of the key. This implies data once stored must be retrieved in order of its priority.

A heap may be used as the base data structure for a priority queue - thus providing insertion and deletion in O(log(n)) time

We look at leftist trees as another representation for priority queues - these offer constant time insertion and deletion at the cost of increased memory

Knuth compares these two choices and a balanced tree representation - and lists a bunch of alternatives found up through the 1990s

He concludes by saying

-------------- "Many new ways to represent priority queues have been discovered since ... Programmers now have a large menu of options to ponder, besides simple lists, heaps, leftist or balanced trees ... Not all of these methods will survive the test of time" --------------

We'll do some exercises

This event will be recorded and posted to YouTube as a public video at https://www.youtube.com/channel/UCHOHy9Rjl3MlEfZ2HI0AD3g

Keep the conversation going!

Facebook: https://www.facebook.com/groups/678335496099220
IRC ##taocp: https://webchat.freenode.net/##taocp

Agenda:

2:00 - 2:10 Meet and greet
2:10 - 3:00 Read and discuss couple pages at a time from Chapter 5, Sorting (along with MMIX Supplement)

• 5.2.3 Sorting by Selection (pp.148-152)
  --- Largest in, first out (pp.148-149)
  --- A linked representation for priority queues (pp.149-150)
  --- Comparison of priority queue techniques, Fig 27 (pp.150-152)

• 5.2.3 Exercises - Sorting by Selection (pp.155-158)
  --- Exercise 15 - Prime numbers table without division (p.156)
  --- Exercise 16 - Add a key to a heap (p.156)
  --- Exercise 29 - Polynomial multiplication (p.157)
  --- Exercise 31 - Priority deque (p.157)
  --- Exercise 33 - Merge leftist tree priority queues (p.157)
  --- Exercise 36 - LRU page replacement (p.158)

3:00 - 3:10 Break
3:10 - 4:00

• Exercises
  --- Volume 3 (pp.155-158)
  --- MMIX Supplement (pp.89)
• Shoot the breeze

Note on MMIX and MIX:

The MMIX is a hypothetical computer designed by Knuth. It is a successor to MIX which is still referred to in all printings of Vols. 1-3 of TAOCP. MMIX is significantly different from MIX. In order to use MMIX instead of MIX now means having to supplement TAOCP with two primary sources.

The first supplement is Fascicle 1, MMIX, a booklet written by Knuth describing the computer and its assembly programming language. It replaces Sections 1.3 and 1.4 of Chapter 1, Basic Concepts. The section numbers in the fascicle have a prime (') suffix to distinguish them from the originals, e.g. fascicle section 1.3.1' replaces TAOCP section 1.3.1.

The second supplement is The MMIX Supplement by Martin Ruckert that has MMIX versions of all programs and content in TAOCP that currently refer to the older MIX computer. It uses the same section numbers as in TAOCP with page references and text snippets from TAOCP to help sync the MMIX version of the content with its location in TAOCP.