Data Structures and Algorithms in Java A Project-Based Approach

A heap is a tree-based data structure that’s designed to quickly return the maximum or minimum of its items. Like a search tree, it maintains a special ordering among its nodes, and takes advantage of the hierarchical nature of binary trees to perform its operations in O(log n) time. Heaps are the primary implementation of the priority queue abstract data type. Like the first-in-first-out queues we studied in Chapter 13, a priority queue supports operations to insert and remove elements, but also maintains an ordering among its items. Polling the queue returns the next item according to the underlying ordering, rather than strictly returning items in FIFO order. Priority queues are used in applications that need to continually fetch the “next” item of a dynamic set that may change over time. A common application is ordering events by time in a simulation program.