Back to Repositories

Testing MaxHeap Data Structure Operations in javascript-algorithms

This test suite validates the implementation of a MaxHeap data structure in JavaScript, focusing on core heap operations including insertion, removal, and heap property maintenance. The tests ensure proper heapification both upwards and downwards while maintaining the max heap invariant.

Test Coverage Overview

The test suite provides comprehensive coverage of MaxHeap operations.

Key functionality tested includes:

Empty heap initialization
Element addition with upward heapification
Element removal with downward heapification
Right branch heapification verification

Edge cases covered include empty heap operations and multiple element insertions/removals.

Implementation Analysis

The testing approach uses Jest’s describe/it pattern to organize test cases logically by functionality. Each test case validates specific heap operations through state verification and element ordering checks.

Technical patterns include:

State verification after each operation
Sequential operation chaining
String representation validation
Heap property maintenance checks

Technical Details

Testing tools and setup:

Jest testing framework
ES6 module import/export
Expect assertions for validation
toBe() matcher for strict equality checks
toString() method for heap structure verification

Best Practices Demonstrated

The test suite exemplifies high-quality testing practices through clear test organization and thorough validation.

Notable practices include:

Isolated test cases for specific functionality
Progressive complexity in test scenarios
Comprehensive state validation
Clear test descriptions
Systematic operation verification

trekhleb/javascript-algorithms

src/data-structures/heap/__test__/MaxHeapAdhoc.test.js

            
import MaxHeap from '../MaxHeapAdhoc';

describe('MaxHeapAdhoc', () => {
  it('should create an empty max heap', () => {
    const maxHeap = new MaxHeap();

    expect(maxHeap).toBeDefined();
    expect(maxHeap.peek()).toBe(undefined);
    expect(maxHeap.isEmpty()).toBe(true);
  });

  it('should add items to the heap and heapify it up', () => {
    const maxHeap = new MaxHeap();

    maxHeap.add(5);
    expect(maxHeap.isEmpty()).toBe(false);
    expect(maxHeap.peek()).toBe(5);
    expect(maxHeap.toString()).toBe('5');

    maxHeap.add(3);
    expect(maxHeap.peek()).toBe(5);
    expect(maxHeap.toString()).toBe('5,3');

    maxHeap.add(10);
    expect(maxHeap.peek()).toBe(10);
    expect(maxHeap.toString()).toBe('10,3,5');

    maxHeap.add(1);
    expect(maxHeap.peek()).toBe(10);
    expect(maxHeap.toString()).toBe('10,3,5,1');

    maxHeap.add(1);
    expect(maxHeap.peek()).toBe(10);
    expect(maxHeap.toString()).toBe('10,3,5,1,1');

    expect(maxHeap.poll()).toBe(10);
    expect(maxHeap.toString()).toBe('5,3,1,1');

    expect(maxHeap.poll()).toBe(5);
    expect(maxHeap.toString()).toBe('3,1,1');

    expect(maxHeap.poll()).toBe(3);
    expect(maxHeap.toString()).toBe('1,1');
  });

  it('should poll items from the heap and heapify it down', () => {
    const maxHeap = new MaxHeap();

    maxHeap.add(5);
    maxHeap.add(3);
    maxHeap.add(10);
    maxHeap.add(11);
    maxHeap.add(1);

    expect(maxHeap.toString()).toBe('11,10,5,3,1');

    expect(maxHeap.poll()).toBe(11);
    expect(maxHeap.toString()).toBe('10,3,5,1');

    expect(maxHeap.poll()).toBe(10);
    expect(maxHeap.toString()).toBe('5,3,1');

    expect(maxHeap.poll()).toBe(5);
    expect(maxHeap.toString()).toBe('3,1');

    expect(maxHeap.poll()).toBe(3);
    expect(maxHeap.toString()).toBe('1');

    expect(maxHeap.poll()).toBe(1);
    expect(maxHeap.toString()).toBe('');

    expect(maxHeap.poll()).toBe(undefined);
    expect(maxHeap.toString()).toBe('');
  });

  it('should heapify down through the right branch as well', () => {
    const maxHeap = new MaxHeap();

    maxHeap.add(3);
    maxHeap.add(12);
    maxHeap.add(10);

    expect(maxHeap.toString()).toBe('12,3,10');

    maxHeap.add(11);
    expect(maxHeap.toString()).toBe('12,11,10,3');

    expect(maxHeap.poll()).toBe(12);
    expect(maxHeap.toString()).toBe('11,3,10');
  });
});