O'Reilly logo

Introduction to the Art of Programming Using Scala by Mark C. Lewis

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required