A Practical Guide to Data Structures and Algorithms using Java

PriorityQueue

Chapter 25

Binary He ap Data Structure

package collection.priority

AbstractCollection<E> implements Collection<E>

↑

BinaryHeap<E> implements PriorityQueue<E>, Tracked<E>

Uses: TrackedArray (Chapter 14)

Used By: Heap sort (Sections 11.4.3 and 15.5.3), TaggedBinaryHeap (Section 49.8.2)

Strengths: The binary heap makes efficient usage of space, especially if the number of elements

to be held in the priority queue is known when the heap is allocated. The binary heap offers locators

that track elements regardless of what mutations are made.

Weaknesses: As with all priority queue data structures, to find an element (without the use of

a locator)