Starting from:
$30

$24

36C-3 HW3 Solution

In this program you will implement a priority queue with an underlying binary
heap implementation. There are multiple objectives of this assignment:
1. strengthen your knowledge of JSON,
2. strengthen your understanding of automated testing,
3. understand and implement a binary heap,
4. introduce greedy algorithms using a toy application (Volleyball team se-
lection).
This program consists of three parts:
1. creating a priority queue with an underlying binary heap implementation
(you will complete the files priorityqueue.cpp and priorityqueue.h),
2. build a binary heap given a sequence of instructions (you will complete
the file buildheap.cxx),
3. use your priority queue to construct a greedy algorithm to pick "fair" 2-
person teams from a list of Volleyball players.

    Build Teams
The contents of BuildExample.json, an example of a JSON file of operations,
is as follows:
```
{
  "Op01": {
    "key": 3019,
    "operation": "insert"
  },
  "Op02": {
    "key": 1500,
    "operation": "insert"
  },
  "Op03": {
    "key": 1334,
    "operation": "insert"
  },
  "Op04": {
    "key": 4119,
    "operation": "insert"
  },
  "Op05": {
    "operation": "removeMin"
  },
  "Op06": {
    "key": 2199,
    "operation": "insert"
  },
  "Op07": {
    "operation": "removeMin"
  },
  "Op08": {
    "operation": "removeMin"
  },
  "Op09": {
    "key": 4180,
    "operation": "insert"
  },
  "Op10": {
    "key": 4586,
    "operation": "insert"
  },
  "metadata": {
    "maxHeapSize": 4,
    "numOperations": 10
  }
}
```
After running build heap, my output using std::cout << jsonObj.dump(2)
on the result is:
```
{
  "1": {
    "key": 3019.0,
    "leftChild": "2",
    "rightChild": "3",
    "value": [0, 0]
  },
  "2": {
    "key": 4119.0,
    "leftChild": "4",
    "parent": "1",
    "value": [0, 0]
  },
  "3": {
    "key": 4180.0,
    "parent": "1",
    "value": [0, 0]
  },
  "4": {
    "key": 4586.0,
    "parent": "2",
    "value": [0, 0]
  },
  "metadata": {
    "maxHeapSize": 4,
    "numOperations": 10,
    "size": 4
  }
}
```

    Create Teams

Use your priority queue to implement the above greedy algorithm

1. Pick a 2-person team with a win percentage as close to 50% as possible.
2. For each of the two players in the 2-person team picked in part 1, remove
all data of other 2-person teams that contain at least one of these players.
That is, every player must be assigned to exactly one team.
3. Go to step 1 if fewer than n 2-person teams have been created.

Your input files will be look like this, which is the contents of CreateTeamsExample.json:
```
{
  "metadata": {
    "numPlayers": 4
  },
  "teamStats": [
    {
      "playerOne": 0,
      "playerTwo": 1,
      "winPercentage": 55.11
    },
    {
      "playerOne": 0,
      "playerTwo": 2,
      "winPercentage": 29.748
    },
    {
      "playerOne": 0,
      "playerTwo": 3,
      "winPercentage": 14.872
    },
    {
      "playerOne": 1,
      "playerTwo": 2,
      "winPercentage": 53.724
    },
    {
      "playerOne": 1,
      "playerTwo": 3,
      "winPercentage": 95.86
    },
    {
      "playerOne": 2,
      "playerTwo": 3,
      "winPercentage": 65.498
    }
  ]
}
```

The final teams are stored in a JSON object and printed to stdout:
```
{
  "teams": [
    [1, 2],
    [0, 3]
  ]
}
```

More products