Search code examples
javatreeheapswapmax-heap

Need Help Counting number of swaps in a MaxHeap


I'm currently working on a project where I have to create a max heap. I'm currently using my textbooks version of the heap which somewhat looks like:

public MaxHeap(int initialCapacity) {
    if (initialCapacity < DEFAULT_CAPACITY)
        initialCapacity = DEFAULT_CAPACITY;
    else
        checkCapacity(initialCapacity);

    @SuppressWarnings("unchecked")
    T[] tempHeap = (T[]) new Comparable[initialCapacity + 1];
    heap = tempHeap;
    lastIndex = 0;
    initialized = true;
}

public T getMax() {
    checkInitialization();
    T root = null;
    if (!isEmpty())
        root = heap[1];
    return root;
}

public boolean isEmpty() {
    return lastIndex < 1;
}

public int getSize() {
    return lastIndex;
}

public void clear() {
    checkInitialization();
    while (lastIndex > -1) {
        heap[lastIndex] = null;
        lastIndex--;
    }
    lastIndex = 0;
}

public void add(T newEntry) {
    checkInitialization();
    int newIndex = lastIndex + 1;
    int parentIndex = newIndex / 2;
    while ((parentIndex > 0) && newEntry.compareTo(heap[parentIndex]) > 0) {
        heap[newIndex] = heap[parentIndex];
        newIndex = parentIndex;
        parentIndex = newIndex / 2;
    }
    heap[newIndex] = newEntry;
    lastIndex++;
    ensureCapacity();
}

public int getSwaps()
{
    return swaps;
}

public T removeMax() {
    checkInitialization();
    T root = null;
    if (!isEmpty()) {
        root = heap[1];
        heap[1] = heap[lastIndex];
        lastIndex--;
        reheap(1);
    }
    return root;
}

private void reheap(int rootIndex) {
    boolean done = false;
    T orphan = heap[rootIndex];
    int leftChildIndex = 2 * rootIndex;

    while (!done && (leftChildIndex <= lastIndex)) {
        int largerChildIndex = leftChildIndex;
        int rightChildIndex = leftChildIndex + 1;
        if ((rightChildIndex <= lastIndex) && heap[rightChildIndex].compareTo(heap[largerChildIndex]) > 0) {
            largerChildIndex = rightChildIndex;
        }
        if (orphan.compareTo(heap[largerChildIndex]) < 0) {
            heap[rootIndex] = heap[largerChildIndex];
            rootIndex = largerChildIndex;
            leftChildIndex = 2 * rootIndex;
        } else
            done = true;
    }
    heap[rootIndex] = orphan;

}

Am I supposed to count the swaps in multiple places and print the total amount and if so where would i count them? I had previously tried to just enumerate swaps++ in the add method but i don't think that is the proper way of doing it.


Solution

  • You have to count the swap in both the add(T newEntry) method and reHeap method which is called from removeMax mathod.

    In reHeap you start from the top and as you call it from removeMax where after removing the max(in Max Heap case) you replace the root with the last element and then you need to balance the heap. So the heap recursively goes down till the last level to balance which may require swap.

    EDIT:

    Add the swap inside following code block of reHeap:

    if (orphan.compareTo(heap[largerChildIndex]) < 0) {
            heap[rootIndex] = heap[largerChildIndex];
            rootIndex = largerChildIndex;
            leftChildIndex = 2 * rootIndex;
            // increment the swap here as inside this block of reHeap only swap takes place.
            swap++
     }