Papers #1 - Binomial Heaps, Jean Vuillemin, 1978

Title: A Data Structure for Manipulating Priority Queues
Authors: Jean Vuillemin
Year: 1978
Length: 6 pages
Citation: Communications of the ACM, April 1978, 309-315
Paper: https://dl.acm.org/doi/abs/10.1145/359460.359478

Abstract: A data structure is described which can be used for representing a collection of priority queues. The primitive operations are insertion, deletion, union, update, and search for an item of earliest priority.

Welcome to our first TAOCP Papers meetup!

TAOCP Papers is an irregular series of meetups on papers on algorithms and data structures related to TAOCP

These could be papers mentioned in TAOCP - like today's selection - or papers that expand on a topic Knuth has covered in TAOCP

The Papers meetup will typically be scheduled on weekdays at 7p New York time - the format is much the same as the main TAOCP meetup - we'll read a bit and discuss - and repeat

It's expected the portions we discuss at a time will be much smaller than couple pages since papers tend to be more dense than a text like TAOCP - it's quite possible some papers may need more than one session

Our regular Saturday afternoon TAOCP meetup continues with no change

************** FAQ **************

• Are we supposed to read the paper before the meetup?
  --- No. We assume - just like for our regular TAOCP meetup - that everyone's reading the paper for the first time during the meetup. If you've read the paper or are familiar with the topic, any knowledge and insight you offer is much appreciated.

• Do I need advanced computer science knowledge to attend?
  --- No. You don't need any computer science or programming knowledge to participate. Any interest even peripheral or simple curiosity is good enough reason to just hang out with us.

• Will I need to stay for the entire meeting?
  --- No. You may join at any time. You may leave at any time - and rejoin if you wish. All meetups are recorded and available on our YouTube channel for later viewing.

• Is it hard?
  --- It's not easy. For any of us. How hard you find it will depend on your level of interest and willingness to engage and ask questions to clarify the material. We feel no matter how difficult the material, it is made easier with focused reading, reflection and discussion in a relaxed setting with a group.

**************************************

Today's paper on binomial heaps - called binomial queues in the paper - is one of the "new ways to represent priority queues" that Knuth mentions in 5.2.3 Sorting by Selection

Along with Fibonacci heaps they are implemented in Knuth's Stanford GraphBase library for graph algorithms development

Supplementary Resources:

• Binomial heaps are based on binomial trees which are covered in 7.2.1.3 Generating all combinations, TAOCP Volume 4A, Combinatorial Algorithms, Part 1

• Binomial heaps are the subject of a lecture on 15 Apr 2021 in CS166, Data Structures, Spring 2021 at Stanford - accompanied by an excellent set of slides at https://web.stanford.edu/class/cs166

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:

7:00 - 7:10 Meet and greet
7:10 - 8:00 Read and discuss a bit at a time

• A Data Structure for Manipulating Priority Queues (pp.309-314)
  --- 1 Introduction (p.309)
  --- Priority queue operations, INSERT, DELETE, MIN, UPDATE, UNION (pp.309-310)
  --- 2 Binomial Trees and Forests, Fig 1, 2, 3 (pp.310-311)
  --- 3 Binomial Queues (p.311)
  --- UNION algorithm, Fig 4, 5 (p.311)
  --- INSERT algorithm (pp.311-312)
  --- DELETE algorithm, Fig 6, 7 (p.312)

8:00 - 8:10 Break
8:10 - 9:00 Continue reading and discussing
--- UPDATE algorithm (pp.312-313)
--- 4 Implementation of Binomial Forests as Binary Trees, Fig 8 (p.313)
--- UNION pseudocode (pp.313-314)
--- DELETE/EXTRACTMIN pseudocode (p.314)