Java代写：COMP410 Priority Queue / Binary Heap Implementation

发表于   |   分类于

代写数据结构中的Priority Queue以及Binary Heap.

Overview

You are going to build in Java a Priority Queue (PrQUE) ADT in Java. It will be done by building a minimum binary heap (BHEAP) with the numerically smallest priority at the root of the tree.

Instead of a single integer as heap element (as we have done in class) your heap will allow manipulation of more information. We represent this as a integer (for priority queue position) and a string (associated information). As elements move around in the heap, keep the associated information associated. We will do this with a element object that contains both (see Interfaces below).

Now that we have established that we are using a heap to produce a priority queue, don’t worry about the various namings we use in the code (which may mix up a bit the technical difference between PrQUE and BHEAP).

What to Hand-in

Hand in your code as per the instructions under Assignment 3 in Sakai.

Interfaces

For uniformity, to aid grading, you must write your program with these specific structures. Note that this time there are interfaces for both MinBinHeap and for EntryPair

Interface Heap_Interface

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package MinBinHeap_A3;

public interface Heap_Interface {
  /*
    Interface: The BHEAP will provide this collection of operations:

    insert
      in: an EntryPair object, containing the priority and string, 
          assume no duplicate priorities will be inserted 
      return: void
    delMin
      in: nothing
      return: void
    getMin
      in: nothing
      return: an element (an EntryPair object)
    size
      in: nothing
      return: integer 0 or greater
    build
      in: array of elements that need to be in the heap
      return: void
      (assume for a build that the bheap will start empty)
  */

  // ADT operations
  void insert(EntryPair entry);
  void delMin();
  EntryPair getMin();
  int size();
  void build(EntryPair [] entries);
  EntryPair[] getHeap();
}

Interface EntryPair_Interface

1
2
3
4
5
6
package MinBinHeap_A3;

public interface EntryPair_Interface {
  String getValue();
  int getPriority();
}

Classes

Class MinBinHeap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package MinBinHeap_A3;

public class MinBinHeap implements Heap_Interface {
  private EntryPair[] array; //load this array
  private int size;
  private static final int arraySize = 10000; //Everything in the array will initially 
                                              //be null. This is ok! Just build out 
                                              //from array[1]

  public MinBinHeap() {
    this.array = new EntryPair[arraySize];
    array[0] = new EntryPair(null, -100000); //0th will be unused for simplicity 
                                             //of child/parent computations...
                                             //the book/animation page both do this.
  }
    
  //Please do not remove or modify this method! Used to test your entire Heap.
  @Override
  public EntryPair[] getHeap() { 
    return this.array;
  }
}

Class EntryPair

1
2
3
4
5
6
7
8
9
10
11
12
13
14
package MinBinHeap_A3;

public class EntryPair implements EntryPair_Interface {
  public String value;
  public int priority;

  public EntryPair(String aValue, int aPriority) {
    value = aValue;
    priority = aPriority;
  }

  public String getValue() { return value; }
  public int getPriority() { return priority; }
}

Class MinBinHeap_Playground

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package MinBinHeap_A3;

public class MinBinHeap_Playground {
  public static void main(String[] args){
    //Add more tests as methods and call them here!!
    TestBuild();
  }
  
  public static void TestBuild(){ 
    // constructs a new minbinheap, constructs an array of EntryPair, 
    // passes it into build function. Then print collection and heap.
    MinBinHeap mbh= new MinBinHeap();
    EntryPair[] collection= new EntryPair[8];
    collection[0]=new EntryPair("i",3);
    collection[1]=new EntryPair("b",5);
    collection[2]=new EntryPair("c",1);
    collection[3]=new EntryPair("d",0);
    collection[4]=new EntryPair("e",46);
    collection[5]=new EntryPair("f",5);
    collection[6]=new EntryPair("g",6);
    collection[7]=new EntryPair("h",17);
    mbh.build(collection);
    printHeapCollection(collection);
    printHeap(mbh.getHeap(), mbh.size());
  }
  
  public static void printHeapCollection(EntryPair[] e) { 
    //this will print the entirety of an array of entry pairs you will pass 
    //to your build function.
    System.out.println("Printing Collection to pass in to build function:");
    for(int i=0;i < e.length;i++){
      System.out.print("("+e[i].value+","+e[i].priority+")\t");
    }
    System.out.print("\n");
  }
  
  public static void printHeap(EntryPair[] e,int len) { 
    //pass in mbh.getHeap(),mbh.size()... this method skips over unused 0th index....
    System.out.println("Printing Heap");
    for(int i=1;i < len+1;i++){
      System.out.print("("+e[i].value+","+e[i].priority+")\t");
    }
    System.out.print("\n");
  }
}

Class RunTests

1
2
3
4
5
6
7
8
9
package MinBinHeap_A3;
import gradingTools.comp410s17.assignment3.testcases.Assignment3Suite;

public class RunTests {
  public static void main(String[] args){ //runs Assignment 3 oracle tests
    Assignment3Suite.main(args);
  }

}

Notes on Operations

insert

Ordering is done based on the integer priorities in the elements that are inserted. Ignore the string for ordering. In the test data we use, the integer priorities in the elements will be unique – there will be no duplicate priorities.

getMin

This operation returns an element (the entire object, priority and data value). It does NOT alter the heap. The heap has the same elements in the same arrangement after as it did before. If getMin is done on an empty heap, return null.

delMin

This operation removes the root element (the entire object) from the heap. The size of the heap goes down by 1 (if the heap was not already empty). If delMin is done on an empty heap, treat it as a no-op… i.e., do nothing other than return void.

build

The build operation should start with an empty heap. It receives an array of element objects as input. The effect is to produce a valid heap that contains exactly those input elements. This means when done the heap will have both a proper structure and will exhibit heap order.

Build is not the same as doing an insert for every element in the array. It is the special O(N) operation from the text (and shown in class) that starts with placing all elements into the heap array with no regard to heap order, then bubbling up as needed.

size

The size operation simply returns the count of how many elements are in the heap. It should be 0 if the heap is empty, and always return a 0 or greater.

Testing and Output

For testing, use the animation page given in class to get test cases and examples of correct behavior. Make sure your code is doing the same.

Their is no specific output or format required for this assignment. We assume you will use the “print” capability provided (and potentially expand on it) to test your code beyond the scope of the oracle.

Furthermore, please note that just because the Oracle gives you 100, you are not guaranteed any specific grade on the assignment. We do try to put as many things as we can in there edge-case wise, but testing your programs is your responsibility. The main goal of the Oracle is to provide some direction. However, it is not the end-all be-all determiner of correctness. Please do not use this tool as a crutch.