A Concise Introduction to Data Structures using Java

Chapter 10

Heaps

The heap data structure provides fast search, insertion, and deletion by limiting the type of searches and deletions it will do. Like binary search trees, heaps are binary trees, but they allow a looser relationship between elements in order to guarantee their height is always O(logn).

10.1 Priority Queue Interface and Array-Based Heaps

Priority queues and heaps are closely related because heaps are often used as the underlying data structure for the priority queue interface. However, other structures may be used to implement priority queues, and heaps have purposes beyond just implementing the priority queue interface.

Priority Queue Interface

A priority queue is an ordered structure in which items are removed in priority order ...