Build a Power-of-Two Max Heap in Java

Implement a d-ary max heap in Java with configurable power-of-two branching.

Introduction

30 Second Summary

When a shipping department processes thousands of packages, the highest-priority shipment needs to go out first. A heap is the data structure that makes this possible, always keeping the most urgent item ready at the top.

In this project, you will build a Power-of-Two Max Heap in Java from scratch. Your heap uses a configurable branching factor to store and retrieve priorities, letting you test how different tree shapes affect performance.

What You'll Build

You run your program, insert a handful of shipping priorities, and watch the terminal confirm that every pop returns the next-highest value regardless of how wide or narrow the tree is.

By the end of this project, you'll have:

  • A working insert operation where you add a value and watch it bubble up to its correct position, maintaining the max-heap property regardless of branching factor.
  • A working popMax operation where you remove the highest priority and watch the heap repair itself by sinking a replacement value down through up to 2^x children at each level.
  • Test output proving your heap works across wildly different tree shapes: a linear chain (x=0), a standard binary tree (x=1), an 8-way tree (x=3), and a 1024-way tree (x=10).
  • Secret Mission: Add a heap-property validator and a performance benchmark that reveals the insert-vs-popMax tradeoff as the branching factor grows.

Are there any prerequisites?

No prior Java experience is required. This guide walks you through installing the JDK and setting up your editor from scratch.

Before We Start

Before We Start...

Before we dive in, let's lock in what you're about to build and why it matters. This step is your chance to commit to the goal before any hands-on work begins.

Set Up Java and Antigravity IDE

Java programs need two things to go from source code to a running application: a compiler that translates your code into bytecode, and a runtime that executes it. Both come packaged together in the Java Development Kit (JDK).

In this step, you'll install Oracle JDK 25 and set up Antigravity IDE to recognize Java. This gives you a single workspace where you can write, compile, and run Java files.

In this step, get ready to:
  • Install Oracle JDK 25 on Windows.
  • Install the Language Support for Java extension in Antigravity IDE.
  • Confirm both java and javac are accessible from the integrated terminal.
Install Oracle JDK 25

The JDK contains both javac (the compiler) and java (the runtime). This project requires version 25 or higher.

  • Press the Windows key to open your search bar.
  • Type PowerShell and press Enter to open it.
  • Check if Java is already installed by running this command:
java -version

✔️ I see version 25 or higher

Your JDK is ready to go. Skip ahead to the next substep.

ⓧ I see an older version

You have an older JDK installed. The JDK 25 installer will install alongside your existing version without removing it.

  • Open the Oracle JDK Downloads page in your browser.
  • Select the Windows tab.
  • Download jdk-25_windows-x64_bin.exe.
  • Run the downloaded file.
  • Click Next through all installation prompts until the install completes.

Now point your system to the new JDK by setting environment variables.

  • Press the Windows key and type environment variables.
  • Click Edit the system environment variables.
  • Click Environment Variables.
  • Under System variables, click New.
  • Enter JAVA_HOME in the Variable name field.
  • Enter C:\Program Files\Java\jdk-25 in the Variable value field.
  • Click OK.
  • Under System variables, find and select Path.
  • Click Edit.
  • Click New.
  • Type %JAVA_HOME%\bin.
  • Click OK on all remaining dialogs to save your changes.

Environment variable changes only take effect in new terminal sessions.

  • Close PowerShell.
  • Reopen PowerShell using the same method as before.
  • Confirm the install by running:
java -version

You should see output that includes java version "25" followed by a patch number like 25.0.3.

ⓧ Command not found

Java is not installed on your machine yet. Let's install JDK 25 from Oracle.

  • Open the Oracle JDK Downloads page in your browser.
  • Select the Windows tab.
  • Download jdk-25_windows-x64_bin.exe.
  • Run the downloaded file.
  • Click Next through all installation prompts until the install completes.

Now tell Windows where to find the JDK by setting environment variables.

  • Press the Windows key and type environment variables.
  • Click Edit the system environment variables.
  • Click Environment Variables.
  • Under System variables, click New.
  • Enter JAVA_HOME in the Variable name field.
  • Enter C:\Program Files\Java\jdk-25 in the Variable value field.
  • Click OK.
  • Under System variables, find and select Path.
  • Click Edit.
  • Click New.
  • Type %JAVA_HOME%\bin.
  • Click OK on all remaining dialogs to save your changes.

Environment variable changes only take effect in new terminal sessions.

  • Close PowerShell.
  • Reopen PowerShell using the same method as before.
  • Confirm the install by running:
java -version

You should see output that includes java version "25" followed by a patch number like 25.0.3.

What is JAVA_HOME?

JAVA_HOME is an environment variable that tells other programs (like your IDE and build tools) where to find the JDK on your machine. Adding %JAVA_HOME%\bin to Path lets you run java and javac from any terminal window without typing the full path.

Install the Language Support for Java extension

Antigravity IDE needs a language extension to understand Java syntax, highlight errors, and offer code completions.

  • Press Cmd+Space (macOS) or the Windows key (Windows) to open your search bar.
  • Type Antigravity and press Enter to open it.
  • Open the Extensions panel by pressing Ctrl+Shift+X.
  • Type Language Support for Java in the search box.
  • Find the result by Red Hat and click Install.

Wait for the installation to complete. You should see a notification confirming the extension is active.

What does this extension do?

The Language Support for Java extension uses the Eclipse JDT Language Server under the hood. It provides syntax highlighting, real-time error detection, code completion, and the ability to run Java files directly from the editor.

Extension not appearing in search?

Make sure you're searching for the exact name: Language Support for Java. The publisher should show as Red Hat. If the extension still does not appear, check that your Antigravity IDE is connected to the internet.

help me find and install the Language Support for Java extension in Antigravity IDE

Verify Java in the integrated terminal

The final check confirms that Antigravity IDE's terminal can find both the Java runtime and the compiler.

  • Open the integrated terminal in Antigravity IDE by pressing Ctrl+`.

Before you run the next command, what do you expect to see if the JDK was installed correctly?

  • Check the Java runtime by running this command:
java -version

You should see output that includes java version "25.0.3" (or a similar 25.x patch version).

  • Check the Java compiler by running this command:
javac -version

You should see javac 25.0.3 (or a similar 25.x patch version).

Seeing 'command not found' or an older version?

If the terminal cannot find java or javac, your JAVA_HOME or Path variables may not be set correctly. Close Antigravity IDE completely and reopen it so the terminal picks up the updated environment variables.

If you still see an older version number, double-check that JAVA_HOME points to C:\Program Files\Java\jdk-25 and that %JAVA_HOME%\bin appears in your Path variable.

help me fix java -version not working in my Antigravity IDE terminal after installing JDK 25

Your Java environment is ready. Next up, you'll use it to build the heap skeleton with the index math that powers every array-based tree.

Build the Heap Skeleton with Index Math

Your Java environment is ready to go. Now it's time to build the core data structure.

Every array-based heap encodes its tree structure through index math rather than explicit pointers between nodes. Getting these formulas right is the foundation everything else builds on.

In this step, get ready to:
  • Define the heap class with fields and a constructor.
  • Add parent/child index formulas that encode the tree structure.
  • Compile and run the program to confirm everything works.
Create the project folder and heap class

Before writing code, you need a dedicated folder on your Desktop to keep the project organized.

  • Switch to the integrated terminal in Antigravity IDE by pressing Ctrl+`.
  • Move to your Desktop and create a project folder by running these commands:
cd ~/Desktop
mkdir power-of-two-heap
cd power-of-two-heap
  • Confirm you are inside the new folder by running:
pwd

You should see a path ending in power-of-two-heap.

  • Open this folder in Antigravity IDE by clicking File in the top menu bar.
  • Click Open Folder.
  • Navigate to your Desktop, select the power-of-two-heap folder, and click Open.

The Explorer sidebar on the left now shows your empty project folder.

  • In the Explorer sidebar, click the New File icon (a page with a plus sign).
  • Name the file PowerOfTwoMaxHeap.java and press Enter.

The file opens in the editor. Now paste the class skeleton into it.

  • Copy the following code into PowerOfTwoMaxHeap.java:
import java.util.ArrayList;

public class PowerOfTwoMaxHeap {

    // Backing array that stores heap elements
    private final ArrayList<Integer> heap;
    // The exponent x (each parent has 2^x children)
    private final int childExponent;
    // Actual number of children per node (2^childExponent)
    private final int numChildren;

    public PowerOfTwoMaxHeap(int childExponent) {
        if (childExponent < 0) {
            throw new IllegalArgumentException("childExponent must be non-negative");
        }
        this.childExponent = childExponent;
        // Bitwise left shift: 1 << x computes 2^x
        this.numChildren = 1 << childExponent;
        this.heap = new ArrayList<>();
    }
}

What does this code do?

  • ArrayList<Integer> heap is a dynamically-sized array that stores the heap's data. No manual resizing needed.
  • childExponent stores the raw exponent value (the x in 2^x).
  • numChildren is computed as 1 << childExponent. The << operator shifts the bit pattern of 1 left by childExponent positions, which is the bitwise way to calculate powers of two.
  • The constructor validates that the exponent is non-negative. A negative exponent would be meaningless for a branching factor.
  • Save the file with Ctrl+S.
  • Compile the file to confirm there are no syntax errors by running this in the terminal:
javac PowerOfTwoMaxHeap.java

If the command produces no output, the file compiled successfully. A PowerOfTwoMaxHeap.class file now exists in your folder.

Seeing a compilation error?

  • Check that the filename is exactly PowerOfTwoMaxHeap.java. In Java, the filename must match the public class name.
  • Make sure you saved the file before running javac. Unsaved changes won't be picked up by the compiler.
  • Confirm your terminal is inside the power-of-two-heap folder by running pwd.

Why won't my Java file compile?

Add the parent and child index formulas

These two formulas are the heart of any array-based heap. They let you navigate the tree without storing any pointers.

  • In PowerOfTwoMaxHeap.java, find the closing } of the constructor. Add the following two methods below it, inside the class:
    private int getParentIndex(int index) {
        // In a d-ary heap: parent is at (i - 1) / d
        return (index - 1) / numChildren;
    }

    private int getChildIndex(int parentIndex, int childOffset) {
        // Children of node i start at d*i + 1, offset selects which child
        return numChildren * parentIndex + childOffset + 1;
    }

What do these formulas mean?

getParentIndex takes any node's array index and calculates where its parent lives. With 0-based indexing and d children per node, the parent is always at (index - 1) / d.

getChildIndex goes the other direction. Given a parent's index and which child you want (0th, 1st, 2nd, etc.), it returns that child's position. The first child of node i is at d*i + 1, and the childOffset selects which one.

These same formulas work for any branching factor, whether each node has 1 child, 2 children, 8 children, or 1024 children.

  • Save the file with Ctrl+S.
Add a main method and run the program

You need a main method to actually run the class and prove it works.

  • Below the getChildIndex method, add this main method inside the class:
    public static void main(String[] args) {
        // Create a binary heap (2^1 = 2 children per node)
        PowerOfTwoMaxHeap h1 = new PowerOfTwoMaxHeap(1);
        System.out.println("Created heap with 2 children per node");
        // Create a wider heap (2^3 = 8 children per node)
        PowerOfTwoMaxHeap h2 = new PowerOfTwoMaxHeap(3);
        System.out.println("Created heap with 8 children per node");
    }

What does this test?

The main method creates two heaps with different branching factors. One has 2 children per node (a standard binary heap). The other has 8 children per node (a much wider, shallower tree).

If both constructors run without throwing an exception, you know the class is wired up correctly.

  • Save the file with Ctrl+S.

Before you run the next command, what do you expect to see printed in the terminal?

  • Compile and run the program by running:
javac PowerOfTwoMaxHeap.java && java PowerOfTwoMaxHeap

You should see this output:

Created heap with 2 children per node
Created heap with 8 children per node

Not seeing the expected output?

  • If you see an error about class not found, make sure you are running the command from inside the power-of-two-heap folder where your .java file lives.
  • If you see a syntax error, check that the main method is inside the class braces but outside the constructor. Every method must sit between the opening { of the class and the final }.
  • If you see IllegalArgumentException, you may have accidentally passed a negative number to the constructor.

Why is my PowerOfTwoMaxHeap not compiling or running?

✔️ Awesome, I've got everything!

Great. Double check you saved PowerOfTwoMaxHeap.java and that both print lines appeared in your terminal.

ⓧ I'd like to double check the full code

Your file should contain these three sections in order. Scroll up to confirm each one is present:

  • The import, class declaration, three fields (heap, childExponent, numChildren), and the constructor with validation and 1 << childExponent.
  • The getParentIndex and getChildIndex helper methods.
  • The main method that creates two heaps (childExponent=1 and childExponent=3) and prints confirmation.

Make sure the final } closes the class after the main method.

Your heap class compiles, runs, and correctly creates heaps with different branching factors. Next up, you'll add the insert operation and watch values bubble up to their correct position.

Implement Insert with Swim-Up

Your heap class compiles and has the index math wired up. Now you need a way to actually put values into it.

Insert is the simpler of the two core heap operations. It appends a value to the end of the backing array, then swaps it upward until every parent is larger than its children. This "swim-up" process restores the heap property after each addition.

In this step, get ready to:
  • Write the insert and swim-up methods that maintain the max-heap property.
  • Add utility methods (peek, size, isEmpty) so you can observe the heap's state.
  • Test insert by watching the maximum value update after each insertion.
Add the insert and swim-up methods

When a new value enters the heap, it lands at the very end of the array. If it is larger than its parent, it does not belong there. The swim-up loop repeatedly swaps it with its parent until it finds a parent that is larger (or it reaches the root).

  • In PowerOfTwoMaxHeap.java, find the closing brace of getChildIndex. Add the following three methods directly below it:
    public void insert(int value) {
        // Append value to the end of the backing array
        heap.add(value);
        // Restore heap property by swimming up from the last position
        swimUp(heap.size() - 1);
    }

    private void swimUp(int index) {
        while (index > 0) {
            int parentIndex = getParentIndex(index);
            // If this node is larger than its parent, swap them
            if (heap.get(index) > heap.get(parentIndex)) {
                swap(index, parentIndex);
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    private void swap(int i, int j) {
        int temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }

What does this code do?

These three methods work together to implement the insert operation:

  • insert appends the new value at the end of the ArrayList, then triggers swim-up from that position.
  • swimUp compares the value at index with its parent. If the child is larger, it swaps up and repeats. The loop stops when the value finds a parent bigger than itself, or when it reaches index 0 (the root).
  • swap is a simple utility that exchanges two elements in the ArrayList by index.
  • Save PowerOfTwoMaxHeap.java.
  • Compile the file to verify there are no syntax errors by running:
javac PowerOfTwoMaxHeap.java

If the code compiles successfully, the command returns silently with no output. A .class file appears in the same directory.

Seeing a compiler error?

  • Check that swimUp and swap are placed inside the class body (between the class opening brace and the main method).
  • Make sure every opening brace has a matching closing brace. A misplaced } from the previous step can break everything below it.
  • Confirm getParentIndex is spelled exactly as it appears in your existing code. Java method names are case-sensitive.

Why isn't my Java file compiling after adding insert and swimUp?

Add utility methods for verification

You need a way to look at the heap's maximum value without removing it. The peek() method returns the root element (index 0), which is always the largest in a max-heap.

  • In PowerOfTwoMaxHeap.java, add the following methods directly below the swap method you just wrote:
    public int peek() {
        if (heap.isEmpty()) {
            throw new IllegalStateException("Heap is empty");
        }
        // Index 0 always holds the maximum in a max-heap
        return heap.get(0);
    }

    public int size() {
        return heap.size();
    }

    public boolean isEmpty() {
        return heap.isEmpty();
    }

What does this code do?

  • peek() returns the root (largest) value without modifying the heap. It throws an exception if the heap is empty so you get a clear error instead of a confusing IndexOutOfBoundsException.
  • size() and isEmpty() expose the ArrayList's length info. You will use these in the next step to drain the heap with popMax.
  • Save PowerOfTwoMaxHeap.java.
  • Compile again to confirm the new methods are syntactically correct:
javac PowerOfTwoMaxHeap.java

No output means success. You now have the building blocks to test insert visually.

Test insert with a binary heap

Time to prove insert actually works. You will replace the existing main method with one that inserts seven values and prints the current maximum after each insertion.

  • In PowerOfTwoMaxHeap.java, find the existing main method:
    public static void main(String[] args) {
        PowerOfTwoMaxHeap h1 = new PowerOfTwoMaxHeap(1);
        System.out.println("Created heap with 2 children per node");
        PowerOfTwoMaxHeap h2 = new PowerOfTwoMaxHeap(3);
        System.out.println("Created heap with 8 children per node");
    }
  • Replace the entire main method with this version that exercises insert and peek:
    public static void main(String[] args) {
        PowerOfTwoMaxHeap binaryHeap = new PowerOfTwoMaxHeap(1);
        int[] values = {10, 4, 15, 20, 0, 30, 2};
        for (int v : values) {
            binaryHeap.insert(v);
            System.out.println("Inserted " + v + " -> peek: " + binaryHeap.peek());
        }
    }

What does this code do?

This loop inserts values one at a time and prints the heap's maximum after each insertion. Because swim-up always moves the largest value to the root, peek() should reflect the running maximum across all values inserted so far.

  • Save PowerOfTwoMaxHeap.java.

Before you compile and run, think about what you expect. After inserting 10, 4, 15, 20, 0, 30, 2, what should peek return at each step?

  • Compile and run your program:
javac PowerOfTwoMaxHeap.java && java PowerOfTwoMaxHeap

You should see output like this:

Inserted 10 -> peek: 10
Inserted 4 -> peek: 10
Inserted 15 -> peek: 15
Inserted 20 -> peek: 20
Inserted 0 -> peek: 20
Inserted 30 -> peek: 30
Inserted 2 -> peek: 30

Every time a value larger than the current max is inserted, peek updates. When a smaller value arrives, the max stays the same. This confirms swim-up is correctly bubbling the largest value to the root.

Peek not showing the right maximum?

  • If peek always returns the most recently inserted value (not the max), check that your swimUp comparison uses > (greater than). Using < would build a min-heap instead.
  • If peek always returns the first value inserted (10), confirm swimUp actually swaps. Check that you call swap(index, parentIndex) and then set index = parentIndex to continue climbing.
  • If you see an IndexOutOfBoundsException, make sure swimUp starts at heap.size() - 1 (the last valid index after adding).

Help me debug why my heap's peek value isn't correct after inserts.

✔️ Awesome, I've got everything!

Great. Double check you have saved PowerOfTwoMaxHeap.java and your output matches the expected values above.

ⓧ I'd like to double check the full code

Your PowerOfTwoMaxHeap.java should now contain these sections in order. Scroll through your file and confirm each is present:

  • The import java.util.ArrayList statement and class declaration with three fields (heap, childExponent, numChildren).
  • The constructor that validates childExponent and initializes all fields.
  • getParentIndex and getChildIndex helper methods (from the previous step).
  • insert, swimUp, and swap methods (added in this step).
  • peek, size, and isEmpty utility methods (added in this step).
  • The updated main method that inserts seven values and prints peek after each.

Your heap can accept values and maintain a correct maximum. Next up, you will implement popMax to extract the largest value and repair the heap by sinking down through all those children.

Implement PopMax with Sink-Down

Your heap can receive values and bubble them up, but it cannot hand them back. The popMax operation removes the root (the largest value) and must repair the tree from the top down.

This is where the branching factor makes things interesting. After moving the last element to the root, you must compare it against all d children at each level to find the largest. One subtle trap: the last level of the tree is often partially filled, meaning a parent may have fewer than d actual children.

In this step, get ready to:
  • Write the popMax method that extracts the root and calls sinkDown.
  • Write the sinkDown method that pushes a misplaced root down through its children.
  • Hit a real bug, diagnose it, and fix it with a bounds check.
Add the popMax method

The pop operation has three jobs: save the max, patch the hole at index 0, and restore the heap property.

  • In PowerOfTwoMaxHeap.java, find the swap method.
  • Add the following popMax method directly above swap:
    public int popMax() {
        // Throw if nothing to pop
        if (heap.isEmpty()) {
            throw new IllegalStateException("Heap is empty");
        }
        // Save the max value at the root
        int max = heap.get(0);
        // Move the last element to the root position
        int lastIndex = heap.size() - 1;
        heap.set(0, heap.get(lastIndex));
        heap.remove(lastIndex);
        // Restore heap property by sinking the new root down
        if (!heap.isEmpty()) {
            sinkDown(0);
        }
        return max;
    }

What does this code do?

  • heap.get(0) grabs the maximum value (always at the root of a max heap).
  • The last element fills the root's empty slot. This preserves the array's contiguous structure.
  • sinkDown(0) will push that misplaced value down until it finds its correct position.
  • The if (!heap.isEmpty()) guard prevents sinking when the last element was just removed.
Add sinkDown without bounds checking

The sinkDown method loops through all children at each level, finds the largest, and swaps if needed. You are going to write an initial version that deliberately skips a crucial check.

  • Add the following sinkDown method directly below popMax:
    private void sinkDown(int index) {
        while (true) {
            int largestIndex = index;
            // Find the first child of this node
            int firstChild = getChildIndex(index, 0);

            // Loop through all children to find the largest
            for (int k = 0; k < numChildren; k++) {
                int childIndex = firstChild + k;
                if (heap.get(childIndex) > heap.get(largestIndex)) {
                    largestIndex = childIndex;
                }
            }

            // If no child is larger, heap property is satisfied
            if (largestIndex == index) {
                break;
            }
            // Swap with the largest child and continue sinking
            swap(index, largestIndex);
            index = largestIndex;
        }
    }

What does this code do?

Starting at the root, sinkDown looks at every child of the current node. If any child is larger, it swaps the current node with the largest child and repeats one level deeper.

The loop ends when no child is larger (the heap property holds) or when the node reaches the bottom of the tree. Notice there is no check for whether the child index actually exists in the array.

  • Save PowerOfTwoMaxHeap.java.
Run the heap and hit the crash

Now you need a way to call popMax so you can see whether sinkDown works.

  • In main, find the closing brace } of the for loop that inserts values.
  • Add this pop loop directly below it:
        System.out.println("\nPopping all values (should be descending):");
        while (!binaryHeap.isEmpty()) {
            System.out.println("  popMax: " + binaryHeap.popMax());
        }
  • Save PowerOfTwoMaxHeap.java.

Before you compile and run, think about what will happen. When sinkDown reaches the bottom of the tree, some parent nodes on the last level have fewer than 2 actual children. What do you think happens when the code tries to read a child index that does not exist in the array?

  • Compile and run by entering this command in the terminal:
javac PowerOfTwoMaxHeap.java && java PowerOfTwoMaxHeap

The program crashes with an IndexOutOfBoundsException. This is the most common bug in real heap implementations. The last level of a heap is almost always partially filled, so some parents have fewer than d children. Your code assumed every parent has exactly numChildren children and tried to access indices beyond the array's actual size.

Why does this crash happen?

Imagine a binary heap with 7 values. The tree has 3 levels. After a popMax, only 6 values remain. The last parent on level 2 now has only 1 child instead of 2.

When sinkDown tries to read the missing second child, it accesses an index beyond the ArrayList's size. Java throws an IndexOutOfBoundsException because that slot simply does not exist.

Fix sinkDown with the bounds check

The fix is a single condition: before comparing a child's value, confirm that child actually exists in the array.

  • In sinkDown, find this line inside the for loop:
                if (heap.get(childIndex) > heap.get(largestIndex)) {
  • Replace it with this line that adds the bounds check before the comparison:
                if (childIndex < heap.size() && heap.get(childIndex) > heap.get(largestIndex)) {

Why does this fix the crash?

Java evaluates && left to right. If childIndex < heap.size() is false, Java skips the second half entirely. This is called short-circuit evaluation.

Now when sinkDown reaches a partially-filled level, it only compares children that actually exist. No more reaching beyond the array.

  • Save PowerOfTwoMaxHeap.java.
  • Compile and run again:
javac PowerOfTwoMaxHeap.java && java PowerOfTwoMaxHeap

You should see the insert output followed by all values popping in descending order: 30, 20, 15, 10, 4, 2, 0.

Still seeing an exception?

  • Make sure you replaced the entire if condition, not just added text after the existing condition. The childIndex < heap.size() check must come before the &&.
  • Confirm there is no semicolon after the if condition. A stray semicolon turns the if into a no-op.
  • help me debug my sinkDown IndexOutOfBoundsException

✔️ Awesome, I've got everything!

Great. Double check you have saved PowerOfTwoMaxHeap.java and the program runs without exceptions.

ⓧ I'd like to double check the full code

Your PowerOfTwoMaxHeap.java should now contain these sections in order. Scroll up and confirm each one is present:

  • The class fields (heap, childExponent, numChildren) and the constructor.
  • getParentIndex and getChildIndex helper methods.
  • insert and swimUp methods.
  • popMax method that saves the root, moves last element to index 0, removes last position, calls sinkDown(0), and returns max.
  • sinkDown method with the childIndex < heap.size() bounds check inside the for loop.
  • swap, peek, size, and isEmpty utility methods.
  • main method that inserts {10, 4, 15, 20, 0, 30, 2}, prints peek after each insert, then pops all values in a while loop.

Your heap now supports both insert and popMax. Next up, you will stress-test this implementation across wildly different branching factors to prove it handles everything from a linear chain to a 1024-way tree.

Test Edge Cases Across Branching Factors

In the previous step, you implemented popMax with sink-down and fixed the IndexOutOfBoundsException that occurs on partially-filled levels. Your heap now correctly inserts and extracts the maximum for a binary tree (childExponent=1).

The real test of generality is whether the same index math holds for extreme branching factors. A heap with childExponent=0 forms a linear chain where every node has exactly one child. A heap with childExponent=10 creates an extremely flat tree with 1024 children per node. Testing both extremes proves your implementation is truly universal.

In this step, get ready to:
  • Test childExponent=0 (degenerate 1-child heap) and confirm correct descending output.
  • Test childExponent=3 (8-child heap) and childExponent=10 (1024-child heap) with larger datasets.
  • Test edge cases including single-element heaps and duplicate values.
Add test headers and the degenerate heap test

Your current main method only tests childExponent=1. You will restructure it into a labeled test suite, then add a test for the most extreme case: childExponent=0, where each node has exactly one child.

  • In PowerOfTwoMaxHeap.java, find the start of the main method.
  • Find this line:
        PowerOfTwoMaxHeap binaryHeap = new PowerOfTwoMaxHeap(1);
  • Add these three lines above it (a test suite header and a label for Test 1):
        System.out.println("=== Power-of-Two Max Heap Tests ===\n");

        // Test 1: Basic insert and popMax with x=1 (binary heap)
        System.out.println("--- Test 1: Binary heap (childExponent=1, 2 children per node) ---");

Now you will add Test 2 directly below the existing binary heap test. A heap with childExponent=0 computes 1 << 0 = 1 child per node. This creates a degenerate linked-list shape where every element is the sole child of the one above it.

  • Scroll to the end of the existing binary heap test (after the closing } of the while (!binaryHeap.isEmpty()) loop).
  • Add the Test 2 code below it:
        // Test 2: x=0 (1 child per node, degenerate linear chain)
        System.out.println("\n--- Test 2: Degenerate heap (childExponent=0, 1 child per node) ---");
        PowerOfTwoMaxHeap degenerateHeap = new PowerOfTwoMaxHeap(0);
        int[] values2 = {5, 3, 8, 1, 9};
        for (int v : values2) {
            degenerateHeap.insert(v);
        }
        System.out.println("Size: " + degenerateHeap.size());
        System.out.println("Popping all values (should be descending):");
        while (!degenerateHeap.isEmpty()) {
            System.out.println("  popMax: " + degenerateHeap.popMax());
        }

What does this test prove?

With childExponent=0, the parent formula (index - 1) / 1 simplifies to index - 1. Each node is the direct parent of the next. Swim-up becomes a simple linear scan upward, and sink-down always compares against exactly one child.

If the index math has an off-by-one error, this degenerate shape is where it surfaces first.

  • Save PowerOfTwoMaxHeap.java.
  • Compile and run by entering this in the terminal:
javac PowerOfTwoMaxHeap.java && java PowerOfTwoMaxHeap

You should see Test 1 output (the binary heap from the previous step) followed by Test 2 popping values in descending order: 9, 8, 5, 3, 1.

Test 2 values not in descending order?

  • Confirm you passed 0 (zero) to the constructor, not the letter O or a negative number.
  • Check that your getParentIndex formula uses numChildren (not childExponent) in the division.
  • Why is my degenerate heap test producing wrong results?
Add wide and very wide heap tests

Now you will test in the opposite direction. A heap with childExponent=3 gives each parent 8 children, and childExponent=10 gives each parent 1024 children. These extremely flat trees stress the sink-down operation because it must compare against many children at each level.

  • Add Test 3 below Test 2 in the main method:
        // Test 3: x=3 (8 children per node)
        System.out.println("\n--- Test 3: Wide heap (childExponent=3, 8 children per node) ---");
        PowerOfTwoMaxHeap wideHeap = new PowerOfTwoMaxHeap(3);
        for (int i = 1; i <= 20; i++) {
            wideHeap.insert(i);
        }
        System.out.println("Inserted 1 through 20. Peek: " + wideHeap.peek());
        System.out.println("First 5 pops:");
        for (int i = 0; i < 5; i++) {
            System.out.println("  popMax: " + wideHeap.popMax());
        }

What does this test prove?

With 8 children per node, inserting 1 through 20 creates a tree that is only 2 levels deep (the root holds up to 8 children, and each of those holds up to 8 more). Swim-up only needs 1-2 swaps per insert. Pop-max, however, must compare 8 children at each level to find the largest.

  • Add Test 4 directly below Test 3:
        // Test 4: x=10 (1024 children per node)
        System.out.println("\n--- Test 4: Very wide heap (childExponent=10, 1024 children per node) ---");
        PowerOfTwoMaxHeap veryWideHeap = new PowerOfTwoMaxHeap(10);
        for (int i = 0; i < 5000; i++) {
            veryWideHeap.insert(i);
        }
        System.out.println("Inserted 5000 elements. Peek: " + veryWideHeap.peek());
        System.out.println("First 3 pops:");
        for (int i = 0; i < 3; i++) {
            System.out.println("  popMax: " + veryWideHeap.popMax());
        }

Why 1024 children per node?

With 1024 children, 5000 elements fit in just 2 levels (root + one layer of children covers 1025 nodes, a second layer covers over a million). Insert is nearly O(1) because the tree is so shallow. Pop-max must scan all 1024 children of the root to find the new maximum, making it expensive per level but with very few levels to traverse.

  • Save PowerOfTwoMaxHeap.java and compile and run:
javac PowerOfTwoMaxHeap.java && java PowerOfTwoMaxHeap

Test 3 should show the first 5 pops as 20, 19, 18, 17, 16. Test 4 should show peek as 4999 and first 3 pops as 4999, 4998, 4997.

Seeing incorrect pop order for wide heaps?

  • Verify your sinkDown loop iterates from k = 0 to k < numChildren (not k <= numChildren).
  • Check that the bounds guard childIndex < heap.size() is still in place. Without it, the program would crash rather than produce wrong results.
  • Why is my wide heap returning values in the wrong order?
Add edge-case tests and run the full suite

Two edge cases commonly break heap implementations: a single-element heap (where pop leaves the array empty and sink-down must not run) and duplicate values (where equal elements must all survive without being lost during swaps).

  • Add Test 5 and the closing message below Test 4 in main:
        // Test 5: Edge cases
        System.out.println("\n--- Test 5: Edge cases ---");
        PowerOfTwoMaxHeap edgeHeap = new PowerOfTwoMaxHeap(2);
        edgeHeap.insert(42);
        System.out.println("Single element peek: " + edgeHeap.peek());
        System.out.println("Single element popMax: " + edgeHeap.popMax());
        System.out.println("Is empty after pop: " + edgeHeap.isEmpty());

        PowerOfTwoMaxHeap dupHeap = new PowerOfTwoMaxHeap(1);
        dupHeap.insert(5);
        dupHeap.insert(5);
        dupHeap.insert(5);
        System.out.println("\nDuplicates test (three 5s):");
        while (!dupHeap.isEmpty()) {
            System.out.println("  popMax: " + dupHeap.popMax());
        }

        System.out.println("\n=== All tests passed! ===");

What do these edge cases check?

  • The single-element test verifies that popMax handles the if (!heap.isEmpty()) guard correctly. Without it, calling sinkDown on an empty array would crash.
  • The duplicates test proves that equal values coexist in the heap without corrupting each other. All three 5s must pop successfully.
  • Save PowerOfTwoMaxHeap.java.

Before you run this final compile, predict: do you think all five test configurations will produce values in descending order with no crashes?

  • Compile and run the full test suite:
javac PowerOfTwoMaxHeap.java && java PowerOfTwoMaxHeap

You should see all five tests produce correct descending output, ending with === All tests passed! ===. The single-element test prints Is empty after pop: true, and the duplicates test pops three 5s successfully.

Seeing an exception on the single-element test?

  • Verify that your popMax method includes the guard if (!heap.isEmpty()) before calling sinkDown(0). After popping the only element, the array is empty and sink-down must be skipped.
  • Check that you remove the last element with heap.remove(lastIndex) after setting index 0, not before.
  • My single-element or duplicates test is crashing. Help me debug.

✔️ Awesome, I've got everything!

Great. Double check you have saved PowerOfTwoMaxHeap.java and all five tests produce correct output.

ⓧ I'd like to double check the full code

Your PowerOfTwoMaxHeap.java file should contain the following sections in order. Scroll up and confirm each is present:

  • The import java.util.ArrayList statement and class declaration with fields (heap, childExponent, numChildren) and constructor.
  • The getParentIndex and getChildIndex helper methods.
  • The insert and swimUp methods.
  • The popMax and sinkDown methods (with the childIndex < heap.size() bounds check).
  • The swap, peek, size, and isEmpty utility methods.
  • The main method with the suite header, Test 1 (binary heap), Test 2 (degenerate heap), Test 3 (wide heap), Test 4 (very wide heap), Test 5 (edge cases), and the closing message.

Your heap now handles branching factors from 1 to 1024 with no crashes and correct results every time. You have a fully tested, general-purpose power-of-two max heap. Next up, the Secret Mission challenges you to validate the heap property programmatically and benchmark the insert-vs-popMax tradeoff across branching factors.

Secret mission

Benchmark and Validate the Heap Property

Your heap passes all the tests, but can you prove the heap property holds programmatically? And can you measure the insert-vs-popMax tradeoff as the branching factor grows? Add a validator and a benchmark to find out.

Clean Up Your Resources

Clean Up Your Resources

This project runs entirely locally, so there are no ongoing costs. Decide whether to keep your resources available, pause them to come back later, or delete them entirely.

Resources you used:

  • PowerOfTwoMaxHeap.java file (your heap implementation).
  • Oracle JDK 25 (Java compiler and runtime).
  • Language Support for Java extension in Antigravity IDE.

Keep everything running

No action needed. Choose this if you plan to keep building Java projects or want to revisit your heap implementation.

  • Your PowerOfTwoMaxHeap.java file stays where you saved it.
  • JDK 25 remains installed and available for any future Java work.
  • The Language Support for Java extension continues to provide syntax highlighting and error detection in Antigravity IDE.

Pause - I'll come back to this later

Shut down any running processes to free up memory. Your files and tools stay installed for when you return.

  • Close any terminal sessions running your Java program.
  • Close the PowerOfTwoMaxHeap.java tab in Antigravity IDE to free editor memory.
  • JDK 25 and the Java extension remain installed for when you come back.

Delete - I don't want to use this again

Remove all project resources and installed tools to start fresh.

  • Delete the PowerOfTwoMaxHeap.java file. On macOS/Linux, run the command below from the folder containing the file:
rm PowerOfTwoMaxHeap.java
  • On Windows, run this in the same folder instead:
del PowerOfTwoMaxHeap.java
  • Uninstall Oracle JDK 25 by opening Windows Settings, selecting Apps, then Installed apps. Find Java(TM) SE Development Kit 25 in the list and click Uninstall.
  • Remove the Language Support for Java extension by opening the Extensions panel in Antigravity IDE (Ctrl+Shift+X), finding Language Support for Java, and clicking Uninstall.
  • Remove the JAVA_HOME environment variable and the %JAVA_HOME%\bin entry from your system PATH if you no longer need Java.

Nice Work!

Nice Work!

You just built a complete Power-of-Two Max Heap data structure in Java from scratch. This is the same kind of priority queue structure used in production systems like the Walmart Shipping Department benchmark, and you implemented it from raw index arithmetic all the way to tested, running code.

You've learned how to:

  • Implement insert and popMax operations using swim-up and sink-down, with the correct parent/child index formulas for a d-ary heap stored in a 0-based array.
  • Derive and apply the bitwise shift operator to compute powers of two, translating the mathematical branching factor 2^x into efficient Java code with 1 << childExponent.
  • Test a data structure across wildly different configurations (from a linear chain at x=0 to a 1024-way tree at x=10), handling edge cases like single elements, duplicates, and partially-filled levels.
  • Secret Mission: Added a heap-property validator and a performance benchmark revealing the insert-vs-popMax tradeoff as branching factor grows.

Ready to quiz yourself?