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