Back to Repositories

Validating Binary Heap Operations in williamfiset/Algorithms

This comprehensive test suite validates the implementation of a Binary Heap data structure, focusing on core heap operations and property maintenance. The tests verify both basic functionality and complex scenarios through systematic and randomized testing approaches.

Test Coverage Overview

The test suite provides extensive coverage of Binary Heap operations including:

Basic operations (isEmpty, size, peek, poll)
Heap property maintenance during insertions and removals
Heapify construction and validation
Duplicate element handling
Randomized testing for robustness

Implementation Analysis

The testing approach employs JUnit Jupiter framework with systematic validation patterns. It uses comparative testing against Java’s PriorityQueue implementation as a reference, ensuring behavioral consistency. The tests incorporate both deterministic and randomized test cases with multiple iterations.

Technical Details

Testing tools and configuration:

JUnit Jupiter for test execution
Google Truth for assertions
Custom utility methods for test data generation
Configurable test parameters (LOOPS = 100, MAX_SZ = 100)

Best Practices Demonstrated

The test suite exemplifies several testing best practices:

Comprehensive edge case coverage
Comparative testing with standard library implementation
Randomized testing for robust validation
Systematic property verification
Clear test method organization and naming

williamfiset/algorithms

src/test/java/com/williamfiset/algorithms/datastructures/priorityqueue/BinaryHeapTest.java

            
package com.williamfiset.algorithms.datastructures.priorityqueue;

import static com.google.common.truth.Truth.assertThat;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import org.junit.jupiter.api.*;

public class BinaryHeapTest {

  static final int LOOPS = 100;
  static final int MAX_SZ = 100;

  @BeforeEach
  public void setup() {}

  @Test
  public void testEmpty() {
    BinaryHeap<Integer> q = new BinaryHeap<>();
    assertThat(q.size()).isEqualTo(0);
    assertThat(q.isEmpty()).isTrue();
    assertThat(q.poll()).isNull();
    assertThat(q.peek()).isNull();
  }

  @Test
  public void testHeapProperty() {

    BinaryHeap<Integer> q = new BinaryHeap<>();
    Integer[] nums = {3, 2, 5, 6, 7, 9, 4, 8, 1};

    // Try manually creating heap
    for (int n : nums) q.add(n);
    for (int i = 1; i <= 9; i++) assertThat(q.poll()).isEqualTo(i);

    q.clear();

    // Try heapify constructor
    q = new BinaryHeap<>(nums);
    for (int i = 1; i <= 9; i++) assertThat(q.poll()).isEqualTo(i);
  }

  @Test
  public void testHeapify() {

    for (int i = 1; i < LOOPS; i++) {

      Integer[] lst = genRandArray(i);
      BinaryHeap<Integer> pq = new BinaryHeap<>(lst);

      PriorityQueue<Integer> pq2 = new PriorityQueue<>(i);
      for (int x : lst) pq2.add(x);

      assertThat(pq.isMinHeap(0)).isTrue();
      while (!pq2.isEmpty()) {
        assertThat(pq.poll()).isEqualTo(pq2.poll());
      }
    }
  }

  @Test
  public void testClear() {

    BinaryHeap<String> q;
    String[] strs = {"aa", "bb", "cc", "dd", "ee"};
    q = new BinaryHeap<>(strs);
    q.clear();
    assertThat(q.size()).isEqualTo(0);
    assertThat(q.isEmpty()).isTrue();
  }

  @Test
  public void testContainment() {

    String[] strs = {"aa", "bb", "cc", "dd", "ee"};
    BinaryHeap<String> q = new BinaryHeap<>(strs);
    q.remove("aa");
    assertThat(q.contains("aa")).isFalse();
    q.remove("bb");
    assertThat(q.contains("bb")).isFalse();
    q.remove("cc");
    assertThat(q.contains("cc")).isFalse();
    q.remove("dd");
    assertThat(q.contains("dd")).isFalse();
    q.clear();
    assertThat(q.contains("ee")).isFalse();
  }

  @Test
  public void testContainmentRandomized() {

    for (int i = 0; i < LOOPS; i++) {

      List<Integer> randNums = genRandList(100);
      PriorityQueue<Integer> PQ = new PriorityQueue<>();
      BinaryHeap<Integer> pq = new BinaryHeap<>();
      for (int j = 0; j < randNums.size(); j++) {
        pq.add(randNums.get(j));
        PQ.add(randNums.get(j));
      }

      for (int j = 0; j < randNums.size(); j++) {

        int randVal = randNums.get(j);
        assertThat(pq.contains(randVal)).isEqualTo(PQ.contains(randVal));
        pq.remove(randVal);
        PQ.remove(randVal);
        assertThat(pq.contains(randVal)).isEqualTo(PQ.contains(randVal));
      }
    }
  }

  public void sequentialRemoving(Integer[] in, Integer[] removeOrder) {

    assertThat(in.length).isEqualTo(removeOrder.length);

    BinaryHeap<Integer> pq = new BinaryHeap<>(in);
    PriorityQueue<Integer> PQ = new PriorityQueue<>();
    for (int value : in) PQ.offer(value);

    assertThat(pq.isMinHeap(0)).isTrue();

    for (int i = 0; i < removeOrder.length; i++) {

      int elem = removeOrder[i];

      assertThat(pq.peek()).isEqualTo(PQ.peek());
      assertThat(pq.remove(elem)).isEqualTo(PQ.remove(elem));
      assertThat(pq.size()).isEqualTo(PQ.size());
      assertThat(pq.isMinHeap(0)).isTrue();
    }

    assertThat(pq.isEmpty()).isTrue();
  }

  @Test
  public void testRemoving() {

    Integer[] in = {1, 2, 3, 4, 5, 6, 7};
    Integer[] removeOrder = {1, 3, 6, 4, 5, 7, 2};
    sequentialRemoving(in, removeOrder);

    in = new Integer[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
    removeOrder = new Integer[] {7, 4, 6, 10, 2, 5, 11, 3, 1, 8, 9};
    sequentialRemoving(in, removeOrder);

    in = new Integer[] {8, 1, 3, 3, 5, 3};
    removeOrder = new Integer[] {3, 3, 5, 8, 1, 3};
    sequentialRemoving(in, removeOrder);

    in = new Integer[] {7, 7, 3, 1, 1, 2};
    removeOrder = new Integer[] {2, 7, 1, 3, 7, 1};
    sequentialRemoving(in, removeOrder);

    in = new Integer[] {32, 66, 93, 42, 41, 91, 54, 64, 9, 35};
    removeOrder = new Integer[] {64, 93, 54, 41, 35, 9, 66, 42, 32, 91};
    sequentialRemoving(in, removeOrder);
  }

  @Test
  public void testRemovingDuplicates() {

    Integer[] in = new Integer[] {2, 7, 2, 11, 7, 13, 2};
    BinaryHeap<Integer> pq = new BinaryHeap<>(in);

    assertThat(pq.peek()).isEqualTo(2);
    pq.add(3);

    assertThat(pq.poll()).isEqualTo(2);
    assertThat(pq.poll()).isEqualTo(2);
    assertThat(pq.poll()).isEqualTo(2);
    assertThat(pq.poll()).isEqualTo(3);
    assertThat(pq.poll()).isEqualTo(7);
    assertThat(pq.poll()).isEqualTo(7);
    assertThat(pq.poll()).isEqualTo(11);
    assertThat(pq.poll()).isEqualTo(13);
  }

  @Test
  public void testRandomizedPolling() {

    for (int i = 0; i < LOOPS; i++) {

      int sz = i;
      List<Integer> randNums = genRandList(sz);
      PriorityQueue<Integer> pq1 = new PriorityQueue<>();
      BinaryHeap<Integer> pq2 = new BinaryHeap<>();

      // Add all the elements to both priority queues
      for (Integer value : randNums) {
        pq1.offer(value);
        pq2.add(value);
      }

      while (!pq1.isEmpty()) {

        assertThat(pq2.isMinHeap(0)).isTrue();
        assertThat(pq1.size()).isEqualTo(pq2.size());
        assertThat(pq1.peek()).isEqualTo(pq2.peek());
        assertThat(pq1.contains(pq1.peek())).isEqualTo(pq2.contains(pq2.peek()));

        Integer v1 = pq1.poll();
        Integer v2 = pq2.poll();

        assertThat(v1).isEqualTo(v2);
        assertThat(pq1.peek()).isEqualTo(pq2.peek());
        assertThat(pq1.size()).isEqualTo(pq2.size());
        assertThat(pq2.isMinHeap(0));
      }
    }
  }

  @Test
  public void testRandomizedRemoving() {

    for (int i = 0; i < LOOPS; i++) {

      int sz = i;
      List<Integer> randNums = genRandList(sz);
      PriorityQueue<Integer> pq1 = new PriorityQueue<>();
      BinaryHeap<Integer> pq2 = new BinaryHeap<>();

      // Add all the elements to both priority queues
      for (Integer value : randNums) {
        pq1.offer(value);
        pq2.add(value);
      }

      Collections.shuffle(randNums);
      int index = 0;

      while (!pq1.isEmpty()) {

        int removeNum = randNums.get(index++);

        assertThat(pq2.isMinHeap(0)).isTrue();
        assertThat(pq1.size()).isEqualTo(pq2.size());
        assertThat(pq1.peek()).isEqualTo(pq2.peek());
        pq1.remove(removeNum);
        pq2.remove(removeNum);
        assertThat(pq1.peek()).isEqualTo(pq2.peek());
        assertThat(pq1.size()).isEqualTo(pq2.size());
        assertThat(pq2.isMinHeap(0)).isTrue();
      }
    }
  }

  @Test
  public void testPQReusability() {

    List<Integer> SZs = genUniqueRandList(LOOPS);

    PriorityQueue<Integer> PQ = new PriorityQueue<>();
    BinaryHeap<Integer> pq = new BinaryHeap<>();

    for (int sz : SZs) {

      pq.clear();
      PQ.clear();

      List<Integer> nums = genRandList(sz);
      for (int n : nums) {
        pq.add(n);
        PQ.add(n);
      }

      Collections.shuffle(nums);

      for (int i = 0; i < sz / 2; i++) {

        // Sometimes add a new number into the BinaryHeap
        if (0.25 < Math.random()) {
          int randNum = (int) (Math.random() * 10000);
          PQ.add(randNum);
          pq.add(randNum);
        }

        int removeNum = nums.get(i);

        assertThat(pq.isMinHeap(0)).isTrue();
        assertThat(PQ.size()).isEqualTo(pq.size());
        assertThat(PQ.peek()).isEqualTo(pq.peek());

        PQ.remove(removeNum);
        pq.remove(removeNum);

        assertThat(PQ.peek()).isEqualTo(pq.peek());
        assertThat(PQ.size()).isEqualTo(pq.size());
        assertThat(pq.isMinHeap(0)).isTrue();
      }
    }
  }

  static Integer[] genRandArray(int sz) {
    Integer[] lst = new Integer[sz];
    for (int i = 0; i < sz; i++) lst[i] = (int) (Math.random() * MAX_SZ);
    return lst;
  }

  // Generate a list of random numbers
  static List<Integer> genRandList(int sz) {
    List<Integer> lst = new ArrayList<>(sz);
    for (int i = 0; i < sz; i++) lst.add((int) (Math.random() * MAX_SZ));
    return lst;
  }

  // Generate a list of unique random numbers
  static List<Integer> genUniqueRandList(int sz) {
    List<Integer> lst = new ArrayList<>(sz);
    for (int i = 0; i < sz; i++) lst.add(i);
    Collections.shuffle(lst);
    return lst;
  }
}