CSC1020 Homework 12 - Heaps
Visualization
A heap can be thought of as a binary tree, but unlike a Binary Search Tree, a heap is not globally sorted.
Instead, a heap maintains a relationship between every parent and its children:
- In a MaxHeap, every parent has priority over its children, so the largest element is at the root.
- In a MinHeap, every parent has priority over its children, so the smallest element is at the root.
There is no required ordering between siblings or between nodes in different branches of the tree.
A heap is also always a Complete Tree. Each level is filled from left to right before a new level is started.
Adding to a Heap
When adding a new element to the Heap, place it in the next available
position in the complete tree. Because the heap is backed by an ArrayList,
this means adding the new element to the end of the list.
After insertion, the element may violate the heap-order property. It must therefore bubble up toward the root.
Compare the new element with its parent. If the new element has higher priority than its parent, swap the two elements. Continue until either:
- the element no longer has higher priority than its parent; or
- the element reaches the root.
The meaning of "higher priority" is determined by the compare(E a, E b)
method described below. This allows the same heap algorithm to work for both
MinHeap and MaxHeap.
Removing from a Heap
Elements are removed from the top of the Heap using the poll() method.
When the root is removed:
- Save the root value so it can be returned.
- Move the final element in the backing
ArrayListto the root. - Repeatedly compare that element with its children.
- If both children exist, determine which child has higher priority.
- If the higher-priority child also has higher priority than the current element, swap them and continue.
- Stop when the element has priority over its children or when it has no children.
If the heap is empty, poll() returns null.
Implementation of a Heap
A Heap is often implemented as an array- or list-backed priority queue.
Although its behavior can be visualized as a binary tree, the parent/child
relationships are represented using indexes in the backing structure.
For this assignment, you will implement the following hierarchy:

Heap Interface
Create the interface:
public interface Heap<E extends Comparable<? super E>>
The Heap interface must define these methods:
-
boolean offer(E item)— adds an element to the heap.nullis not permitted. Offeringnullmust throw aNullPointerException.- Duplicate elements are not permitted. An element is considered a duplicate
when
equals()reports that it is equal to an element already stored in the heap. - Return
truewhen the element is added. - Return
falsewhen the element is rejected as a duplicate.
-
E poll()— removes and returns the highest-priority element.- Return
nullif the heap is empty.
- Return
-
boolean isEmpty()— returnstrueif the heap contains no elements. -
int size()— returns the number of elements currently stored in the heap.
AbstractHeap
Create the abstract class:
public abstract class AbstractHeap<E extends Comparable<? super E>>
implements Heap<E>
AbstractHeap must use an ArrayList<E> as its backing structure and contain
the following fields:
private static final int INITIAL_CAPACITY = 10;
private final ArrayList<E> data;
The no-argument constructor initializes data using INITIAL_CAPACITY.
The class must implement:
offer(E item)poll()isEmpty()size()
It must also define:
protected abstract int compare(E a, E b);
The compare() method defines which of two elements has higher heap priority:
- a positive result means
ahas higher priority thanb; 0means neither has higher priority;- a negative result means
ahas lower priority thanb.
AbstractHeap must also contain this private helper:
private void swap(int a, int b)
which swaps the two elements in data at indexes a and b.
ArrayList Representation
When elements are stored in the heap, they are placed in the ArrayList in
complete-tree order.
For an element at index i:
parent = (i - 1) / 2
left child = 2 * i + 1
right child = 2 * i + 2
These relationships are what allow the heap to behave like a binary tree without storing explicit node objects.
For example, suppose the backing ArrayList stores:
| A | B | C | D | E | F | G | H |
The root node is A at index 0. The left child of A is B and the right child is C.
The parent of C, at index 2, is:
(2 - 1) / 2 = 0
so A is its parent.
The parent of H, at index 7, is:
(7 - 1) / 2 = 3
so D is its parent.
The tree representation is:

MinHeap and MaxHeap
Create these two concrete subclasses:
public class MaxHeap<E extends Comparable<? super E>>
extends AbstractHeap<E>public class MinHeap<E extends Comparable<? super E>>
extends AbstractHeap<E>
Each class implements the inherited compare(E a, E b) method to define
priority.
For a MaxHeap, the element with the larger natural-order value has higher
priority. As a result, poll() returns elements from largest to smallest.
For a MinHeap, the element with the smaller natural-order value has higher
priority. As a result, poll() returns elements from smallest to largest.
The bubbling algorithms in AbstractHeap must depend on compare() rather
than directly assuming that larger or smaller values have higher priority.