Donate. I desperately need donations to survive due to my health

Get paid by answering surveys Click here

Click here to donate

Remote/Work from Home jobs

Need some explanation on adding to a Binary Heap (priority queue)

I'm having trouble understanding how to add and swap nodes using a priority queue on a binary heap. Below I've provided two pictures of my assignment. I need help on assignment 2 on using push.

assignment1

assignment2

This is the code I have so far:

  import java.util.*;

public class BinaryHeap<T extends Comparable <T> > implements HeapInterface<T>{
    int capacity;
    ArrayList<T> heap;
    int last;
    int minOrMax;
  public BinaryHeap(int initial_capacity, boolean max){
      heap = new ArrayList<T>(initial_capacity);
      for (int i = 0; i < initial_capacity; i++){
          heap.add(i, null);
      }
      last = (int) heap.get(0);
      if(max){
          minOrMax = 1;
      }
      else{
          minOrMax = -1;
      }


  }

  public void push(T entry){
      int current = last ++;
      heap.set(last, entry);
      int parent = current/2;
      while(parent != 0 && entry.compareTo(heap.get(parent))*minOrMax > 0){

I'm mostly following the assignment word for word, so feel free to correct me if any of the code elsewhere seems incorrect. If you've read the instructions for the push function, can you explain it to me?

I know to add onto a binary heap you always add at the end of the heap and its left based. If it's not in order, then you swap based on whether it's a max or min heap. But I don't understand what the instructions are saying exactly.

Comments