I am trying to improve the quality of my code as well as trying to study the Heap
data structure. I have implemented a minHeap (Heap in which minimum value nodes have higher priority). Ref: link1, link2, link3. This is the commented code:
#include <iostream>
#include <vector>
#include <limits>
// Class for throwing `out of range` exceptions
class OutofRange
{
std::string error = "The index is out of range.";
public:
OutofRange()
{
}
std::string what()
{
return error;
}
};
// Class for MinHeap. The `arr` holds the heap elements. The `capacity` indicates total
// allocated space for the heap. The `length` indicates size of the heap.
template<typename T>
class MinHeap
{
T* arr;
size_t capacity;
size_t length;
public:
MinHeap(size_t);
T get_min();
void heapify(int);
void insert(T);
T delete_min();
T delete_by_index(int);
void print_heap();
};
// Constructor for the heap
template<typename T>
MinHeap<T>::MinHeap(size_t n)
{
arr = new T[n];
capacity = n;
length = 0;
}
// Return the minimum node (root)
template<typename T>
T MinHeap<T>::get_min()
{
if(length > 0)
{
return arr[0];
}
else
{
std::cout << "Error: Invalid access" << std::endl;
throw OutofRange{};
}
}
// Function to put a node at the right position if it has the possibility to move up
// in the heap
template<typename T>
void MinHeap<T>::heapify(int start)
{
for(int i = start; i > 0; i = (i - 1) / 2)
{
if(arr[i] < arr[(i - 1) / 2])
{
std::swap(arr[i], arr[(i - 1) / 2]);
}
else
{
return;
}
}
}
// Inserts nodes to heap
template<typename T>
void MinHeap<T>::insert(T data)
{
// Check if capacity is reached
if(length == capacity)
{
std::cout << "Error: Heap capacity reached" << std::endl;
return;
}
// Insert the node
arr[length] = data;
this -> heapify(length);
length++;
}
// Deletes the minimum value node (root)
template<typename T>
T MinHeap<T>::delete_min()
{
// Check if heap has any elements/ nodes
if(length == 0)
{
std::cout << "Error: Invalid Access" << std::endl;
throw OutofRange{};
}
// Replace minimum node (root) with the last node
T del_min = arr[0];
std::swap(arr[0], arr[length - 1]);
arr[length - 1] = (T)NULL;
length--;
// Bring the new root to correct position based on value
for(size_t i = 0; i < length - 1 && length > 0;)
{
int min_child;
if(2 * i + 1 > length - 1)
{
break;
}
if(2 * i + 2 > length - 1)
{
min_child = 2 * i + 1;
}
else
{
min_child = arr[2 * i + 1] <= arr[2 * i + 2] ? 2 * i + 1 : 2 * i + 2;
}
if(arr[i] > arr[min_child])
{
std::swap(arr[i], arr[min_child]);
}
i = min_child;
}
return del_min;
}
// Deletes a node by index
template<typename T>
T MinHeap<T>::delete_by_index(int index)
{
int del_val = arr[index];
T min_val = std::numeric_limits<T>::min();
arr[index] = min_val;
this -> heapify(index);
this -> delete_min();
return del_val;
}
// Print the heap
template<typename T>
void MinHeap<T>::print_heap()
{
std::cout << "The Min Heap: " << std::endl;
if(length == 0)
{
std::cout << "Empty" << std::endl;
}
for(size_t i = 0; i < length; i++)
{
std::cout << arr[i] << "\t";
}
std::cout << std::endl;
}
int main()
{
try
{
MinHeap<int> h1{10};
int del_val;
std::vector<int> input = {35, 33, 42, 10, 14, 19, 27, 44, 26, 31};
// Insert input values to the heap
for(size_t i = 0; i < input.size(); i++)
{
h1.insert(input[i]);
h1.print_heap();
}
// Check if minimum value/ highest priority can be accessed
std::cout << "Current Root: " << h1.get_min() << std::endl;
// Delete by index test case
del_val = h1.delete_by_index(2);
std::cout << "Delete by index: " << del_val << std::endl;
h1.print_heap();
// Delete the minimum value
for(size_t i = 0; i < input.size(); i++)
{
del_val = h1.delete_min();
std::cout << "Deleted value: " << del_val << std::endl;
h1.print_heap();
}
// Uncomment to test exception in deletion if delete_by_index test case is not present.
//del_val = h1.delete_min();
//std::cout << "Deleted value: " << del_val << std::endl;
// Uncomment to test exception in accessing minimum value(root)
//h1.get_min();
}
// Catch the out of range exceptions
catch(OutofRange& e)
{
std::cout << e.what() << std::endl;
}
return 0;
}
Are heaps used for data types other than numeric? Even though my implementation uses templates, it does depend on
numeric_limits
. I am assuming that if the data type is not numeric, it can converted to a custom data type like shown below:struct custom_type { T val; int priority; custom_type(T v, int p) { val = v; priority = p; } // Overloads for comparison operators which utilize priority field. /* ------- ------- */ };
Is there a better way to handle
out of range
errors without using exceptions and not returning a value such asINT_MAX
,INT_MIN
or zero?What could be other possible improvements in the code?
std::make_heap
et al. are pretty good. \$\endgroup\$