2 Improve priority queues: d-way heaps

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.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.4 Priority, min-heap and max-heap

2.5.5 Advanced variant: d-ary heap

2.6 How to implement a heap

2.6.1 BubbleUp

2.6.2 PushDown

2.6.3 Insert

2.6.4 Top

2.6.5 Update

2.6.6 Dealing with Duplicates

2.6.7 Heapify

2.6.8 Beyond API methods: contains

2.6.9 Performance recap

2.6.10 From Pseudo-code to implementation

2.7 Use case: find the k largest elements

2.7.1 The right data structure…

2.7.2 … and the right use

2.7.3 Coding it up

2.8 More use-cases

2.8.1 Minimum distance in graphs: Dijkstra

2.8.2 Beyond Dijkstra: BFS, A*

2.8.3 More graphs: Prim's algorithm