VV-ISTIC-TP4/exercises/heap.md

Testing the heap property

A binary heap is a data structure that contains comparable objects and it is able to efficiently return the lowest element. This data structure relies on a binary tree to keep the insertion and deletion operations efficient. It is the base of the Heapsort algorithm.

Implement a BinaryHeap class with the following interface:

class BinaryHeap<T> {

    public BinaryHeap(Comparator<T> comparator) { ... }

    public T pop() { ... }

    public T peek() { ... }

    public void push(T element) { ... }

    public int count() { ... }

}

A BinaryHeap instance is created using a Comparator object that represents the ordering criterion between the objects in the heap. pop returns and removes the minimum object in the heap. If the heap is empty it throws a NotSuchElementException. peek similar to pop, returns the minimum object but it does not remove it from the BinaryHeap. push adds an element to the BinaryHeap. count returns the number of elements in the BinaryHeap.

With the help of jqwik create a test that generates random inputs for your heap and ensures that the element returned by pop every time it is invoked is the minimum of the remaining elements in the heap.

NOTE:

• Do not use any existing implementation, write your own code.
• Use the provided project template as a starting point.
• In the project you can launch the tests with mvn test.
• You may reuse your binary heap code from the previous practical assignment.