Heap Implementation

Theory

When you pop, since you swap the last leave node to the top, you need to bubbleDown() from the top node

• This takes $O(logn)$

When you insert, since you add from the bottom, you need to bubbleUp

• This takes $O(logn)$

When heapify (forming a heap from the array). You have to bubbleDown from the last non-leave node ($\frac{n - 1}{2}$) to the root (i = 0).

• This takes $O(nlogn)$

Implementation

package datastructures;


import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class HeapQueue<T> implements Heap<T> {
  private List<T> elements;

  private Comparator<T> comparator;

  public HeapQueue(Comparator<T> comparator) {
    elements = new ArrayList<>();
    this.comparator = comparator;
  }

  public HeapQueue(List<T> elements, Comparator<T> comparator) {
    this.elements = new ArrayList<>(elements);
    this.comparator = comparator;
    for (var i = getLastNonLeaveNode(elements.size()); i >= 0; i--) {
      bubbleDown(i);
    }
  }

  @Override
  public T peek() {
    if (elements.isEmpty()) {
      throw new IndexOutOfBoundsException();
    }
    return elements.get(0);
  }

  @Override
  public T pop() {
    if (elements.isEmpty()) {
      throw new IllegalStateException();
    }

    T removedItem = peek();
    swap(0, elements.size() - 1);
    elements.remove(elements.size() - 1);

    bubbleDown(i);
    return removedItem;
  }

  @Override
  public void insert(T element) {
    elements.add(element);
    bubbleUp(elements.size() - 1);
  }

  private void bubbleUp(int currentIndex) {
    int parentIndex = getParentIndex(currentIndex);

    if (currentIndex == 0 || comparator.compare(elements.get(currentIndex), elements.get(parentIndex)) < 0) {
      return;
    }

    swap(currentIndex, parentIndex);
    bubbleUp(parentIndex);
  }


  private void bubbleDown(int currentIndex) {
    int leftChildIndex = getLeftChildIndex(currentIndex);
    int rightChildIndex = getRightChildIndex(currentIndex);
    int largestIndex = currentIndex;

    if (leftChildIndex < elements.size() && comparator.compare(elements.get(leftChildIndex), elements.get(largestIndex)) > 0) {
      largestIndex = leftChildIndex;
    }

    if (rightChildIndex < elements.size() && comparator.compare(elements.get(rightChildIndex), elements.get(largestIndex)) > 0) {
      largestIndex = rightChildIndex;
    }

    if (largestIndex != currentIndex) {
      swap(currentIndex, largestIndex);
      bubbleDown(largestIndex);
    }
  }

  private void swap(int firstIndex, int secondIndex) {
    T temp = elements.get(secondIndex);
    elements.set(secondIndex, elements.get(firstIndex));
    elements.set(firstIndex, temp);
  }

  private int getLeftChildIndex(int index) {
    return 2 * index + 1;
  }

  private int getRightChildIndex(int index) {
    return 2 * index + 2;
  }

  private int getLastNonLeaveNode(int length) {
    return (length - 1) / 2;
  }

  private int getParentIndex(int currentIndex) {
    return (currentIndex - 1) / 2;
  }
}

package datastructures;


public interface Heap<T> {
  T peek();
  T pop();
  void insert(T element);
}

Thread Safe version

@ThreadSafe
public class SynchronisedHeapQueue<T> extends HeapQueue<T>{
  public SynchronisedHeapQueue(Comparator<T> comparator) {
    super(comparator);
  }

  public SynchronisedHeapQueue(List<T> elements, Comparator<T> comparator) {
    super(elements, comparator);
  }

  @Override
  public synchronized T peek() {
    return super.peek();
  }

  @Override
  public synchronized T pop() {
    return super.pop();
  }

  @Override
  public synchronized void insert(T element) {
    super.insert(element);
  }
}