Introduction to the Art of Programming Using Scala

Chapter 32

Binary Heaps

Back in chapter 26 we looked at the priority queue Abstract Data Type (ADT). In that chapter, the implementation that was written used a sorted linked-list. While it was easy to write, this implementation has the downside of an O(n) enqueue method. This gives overall performance that is O(n2) for the size of the queue. In this chapter we will look at a different implementation that provides O(log(n)) performance for both enqueue and dequeue, the heap.

32.1 Binary Heaps

There are quite a few different styles of heaps. A common theme is that they have a tree structure. The simplest, and probably most broadly used, is the binary heap. As the name implies, it is based on a binary tree type of structure where each node can ...