2 Improving priority queues: d-way heaps


This chapter covers

  • Solving the problem of serving tasks based on priority
  • Using priority queues to solve our problem
  • Implementing a priority queue with a heap
  • Introducing and analyzing d-way heaps
  • Recognizing use cases where heaps improve performance

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