CSCI H343 Data Structures Fall 2023

Lab 5: Binomial Heaps

Overview

In this lab you are going to complete the code for binomial queue, by implementing the isHeap() method in the BinomialHeap and BinomialQueue classes and the insert() and merge() methods in the BinomialQueue class.

Please review the lecture notes here before you start.

Support Code and Submission

Problem Set

Problem 1: BinomialHeap

The following is an excerpt from the BinomialHeap class:

class BinomialHeap<K> {
    K key;
    int height;
    PList<BinomialHeap<K>> children;
    BiPredicate<K, K> lessEq;

    BinomialHeap<K> link(BinomialHeap<K> other) {
        // ...
    }

    boolean isHeap() {
        // ...
    }
}

Problem 2: BinomialQueue

The following is an excerpt from the BinomialQueue class:

public class BinomialQueue<K> {
    PList<BinomialHeap<K>> forest;
    BiPredicate<K, K> lessEq;

    public BinomialQueue(BiPredicate<K, K> le) {
        // ...
    }

    public void push(K key) {
        // ...
    }

    public K pop() {
        // ...
    }

    public boolean isHeap() {
        // ...
    }

    static <K> PList<BinomialHeap<K>>
        insert(BinomialHeap<K> n, PList<BinomialHeap<K>> ns) {
        // ...
    }

    static <K> PList<BinomialHeap<K>>
        merge(PList<BinomialHeap<K>> ns1, PList<BinomialHeap<K>> ns2) {
        //...
    }
}

Problem 3: Testing

Create tests in StudentTest.java which thoroughly test the public push and pop methods of the BinomialQueue.