2 Improving priority queues: d-way heaps

In the previous chapter we introduced some basic concepts about data structures and programming techniques, described the structure of this book, and hopefully raised your interest. You should now be aware of why developers need to know about data structures.

In this chapter, we will further develop those ideas and refine our narration. This chapter is meant to be a soft introduction to what is presented in this book; we have chosen a topic that should be familiar to readers with some background in algorithms, while providing a review of heaps along with some new insight on branching factors.

2.1 Structure of this chapter

2.2 The problem: Handling priority

2.2.1 Priority in practice: Bug tracking

2.3 Solutions at hand: Keeping a sorted list

2.3.1 From sorted lists to priority queues

2.4 Describing the data structure API: Priority queues

2.4.1 Priority queue at work

2.4.2 Priority matters: Generalize FIFO

2.5 Concrete data structures

2.5.1 Comparing performance

2.5.2 What’s the right concrete data structure?

2.5.3 Heap

2.5.5 Advanced variant: d-ary heap

2.6 How to implement a heap