Exercises

Exercises 30.10 Exercises

1.

Implement the largestChildIndex(int currentIndex) function for a MaxHeap. Given an index for a value in the heap, it should return the index of the child that contains the largest value. If there are no children, return -1.

🔗

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

import MaxHeap;

#include <iostream>
using namespace std;

^^^!
template<typename T>
int MaxHeap<T>::largestChildIndex(int currentIndex) const {
  // your code here
}
===!

/*
 * Forcibly set heap to known state:
 *       100
 *      /   \
 *     50    60
 *    / \    /
 *   30 20  10
 */
// Built to take existing heap to avoid using copy ctor or assignment
void buildTestHeap(MaxHeap<int>& h) {
  delete[] h.data;
  h.heapSize = 6;
  h.capacity = 32;
  // Array intentionally has extra 200... not considered part of heap
  h.data = new int[32]{100, 50, 60, 30, 20, 10, 200};
}

TEST_CASE("largestChildIndex") {
  MaxHeap<int> h;
  buildTestHeap(h); // 100 50 60 30 20 10

INFO(h.toString());
  REQUIRE(h.largestChildIndex(0) == 2);
  REQUIRE(h.largestChildIndex(1) == 3);
  REQUIRE(h.largestChildIndex(2) == 5);
  REQUIRE(h.largestChildIndex(3) == -1);
  REQUIRE(h.largestChildIndex(4) == -1);
  REQUIRE(h.largestChildIndex(5) == -1);
}

Hint.

The index may have one or no valid children. You need to sanity check the indexes of the children to decide if they are valid.

🔗

2.

Implement the add(int value) function for a MaxHeap. This function should insert a new value into the heap while maintaining the max-heap property.

🔗

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

import MaxHeap;

#include <iostream>
using namespace std;

^^^!
template<typename T>
void MaxHeap<T>::add(const T& value) {
    if(heapSize == capacity)
        grow();

// your code here
}
===!

TEST_CASE("addTest1") {
  MaxHeap<int> h;
  buildTestHeap(h); // 100 50 60 30 20 10

INFO(h.toString());

h.add(15);
  REQUIRE(h.heapSize == 7);
  REQUIRE(h.data[2] == 60);
  REQUIRE(h.data[6] == 15);
}

TEST_CASE("addTest2") {
  MaxHeap<int> h;
  buildTestHeap(h); // 100 50 60 30 20 10

INFO(h.toString());

h.add(75);
  REQUIRE(h.heapSize == 7);
  REQUIRE(h.data[2] == 75);
  REQUIRE(h.data[6] == 60);
}

TEST_CASE("addTest3") {
  MaxHeap<int> h;
  buildTestHeap(h); // 100 50 60 30 20 10

INFO(h.toString());

h.add(15);
  h.add(75);
  REQUIRE(h.heapSize == 8);
  REQUIRE(h.data[1] == 75);
  REQUIRE(h.data[3] == 50);
  REQUIRE(h.data[7] == 30);
}

TEST_CASE("addTest4") {
  MaxHeap<int> h;
  buildTestHeap(h); // 100 50 60 30 20 10

INFO(h.toString());

h.add(15);
  h.add(15);
  h.add(15);
  h.add(200);
  REQUIRE(h.heapSize == 10);
  REQUIRE(h.data[0] == 200);
  REQUIRE(h.data[1] == 100);
  REQUIRE(h.data[4] == 50);
  REQUIRE(h.data[9] == 20);
}

Hint.

The new value should be inserted at the end and then swap up until either it reaches index 0 or it is smaller than its parent.

🔗

3.

Implement the removeMax() function for a MaxHeap. This function should remove and return the maximum value from the heap while maintaining the max-heap property.

🔗

You will want to use the largestChildIndex function you implemented in a previous exercise. Copy and paste it into this problem.

🔗

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

import MaxHeap;

#include <iostream>
using namespace std;

^^^!

// Paste your largestChildIndex function here

template<typename T>
T MaxHeap<T>::removeMax() {
  if (heapSize == 0)
    throw std::logic_error("removeTop in empty heap");

// your code here
}
===!

TEST_CASE("remove1") {
  MaxHeap<int> h;
  buildTestHeap(h); // 100 50 60 30 20 10

INFO(h.toString());

int temp = h.removeMax();
  REQUIRE(temp == 100);
  REQUIRE(h.data[0] == 60);
  REQUIRE(h.data[2] == 10);
  REQUIRE(h.heapSize == 5);
}

TEST_CASE("remove2") {
  MaxHeap<int> h;
  buildTestHeap(h); // 100 50 60 30 20 10

INFO(h.toString());

h.removeMax();
  int temp = h.removeMax();
  REQUIRE(temp == 60);
  REQUIRE(h.data[0] == 50);
  REQUIRE(h.data[1] == 30);
  REQUIRE(h.data[3] == 20);
  REQUIRE(h.heapSize == 4);
}

TEST_CASE("removeAll") {
  MaxHeap<int> h;
  buildTestHeap(h); // 100 50 60 30 20 10

INFO(h.toString());

h.removeMax();
  h.removeMax();
  REQUIRE(h.removeMax() == 50);
  REQUIRE(h.removeMax() == 30);
  REQUIRE(h.removeMax() == 20);
  REQUIRE(h.removeMax() == 10);
  REQUIRE(h.heapSize == 0);
}

🔗

You have attempted of activities on this page.

🔗

Prev Top Next