2 Improve priority queues: d-way heaps

This chapter covers

  • Solving a problem: 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 have 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 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 on algorithms, providing a review of heaps together with some new insight on branching factors.

2.1 Structure of this chapter

2.4.2 Priority Matters: Generalize FIFO

2.5.1 Comparing performance

2.5.2 What’s the right concrete data structure?

2.5.5 Advanced variant: d-ary heap

2.6 How to implement a heap

2.6.2 PushDown

2.6.3 Insert

2.6.4 Top

2.6.5 Update

sitemap