Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
Introduction
The heap data structure is a binary tree-based data structure that satisfies the heap property. It is commonly used to implement priority queues. In this article at OpenGenus, we will explore how to implement the heap data structure in C++ using principles of object-oriented programming (OOP) and templates.
Table of Contents:
OOP Concepts
What is a Heap?
Real-Life Applications of Heap
Heap Implementation in C++ using Templates
Advantages of Heap
Conclusion
Complete Code of Heap in C++ using Templates
OOP Concepts
Before we dive into the implementation of the heap data structure using templates, let's briefly review the OOP concepts that we'll utilize:
Encapsulation:
Encapsulation involves bundling data and methods together into a single unit, known as a class. It allows us to hide the internal implementation details and provide a clean interface for interacting with the class.
Inheritance:
Inheritance is the process of creating a new class from an existing class. It allows the new class to inherit the properties and methods of the existing class, promoting code reuse and modularity.
Polymorphism:
Polymorphism enables objects of different classes to be treated as objects of a common superclass. It allows for code flexibility and extensibility by providing a way to perform different actions based on the object's type.
Abstraction:
Abstraction involves hiding the complex implementation details and exposing only the essential features to the user. It simplifies the usage of a class or data structure by providing a high-level interface.
What is a Heap?
A heap is a complete binary tree that satisfies the heap property. The heap property differs depending on whether it is a min-heap or a max-heap.
In a min-heap, for any given node, the value of that node is less than or equal to the values of its children. The smallest element in the heap is stored at the root node.
In a max-heap, for any given node, the value of that node is greater than or equal to the values of its children. The largest element in the heap is stored at the root node.
Heaps are commonly used to implement priority queues, where the highest priority element can be efficiently extracted.
Real-Life Applications of Heap
Heaps have a variety of applications in computer science and real-world scenarios. Here are a few instances where heaps are used:
Priority Queues:
Heaps are often used to implement priority queues, where elements with higher priority are dequeued before elements with lower priority. Priority queues are used in various applications such as task scheduling, job queues, and event-driven simulations.
Dijkstra's Algorithm:
Dijkstra's algorithm, used to find the shortest path in a graph, utilizes a min-heap to efficiently extract the node with the smallest distance.
Heap Sort:
Heap sort is an efficient sorting algorithm that leverages the heap data structure to sort an array of elements in ascending or descending order.
Memory Management:
Heaps are used in memory management systems to allocate and deallocate memory dynamically. The heap data structure manages the free memory blocks and tracks their availability.
Heap Implementation in C++ using Templates
To implement a heap in C++ using templates, we can create a Heap class that encapsulates the heap-related operations. The class will include methods to insert elements into the heap, extract the top element, and check if the heap is empty.
Let's define the Heap class with templates and its member variables:
template <typename T>
class Heap {
private:
std::vector<T> heapArray;
void heapifyUp(int index);
void heapifyDown(int index);
public:
Heap();
void insert(const T& value);
T extractTop();
void remove(const T& value);
bool isEmpty();
};
The Heap class is defined with the template parameter typename T, which allows us to use the Heap class with different data types. The class has a private member variable heapArray, which is a vector to store the elements of the heap.
Next, let's implement the constructor, which initializes an empty heap:
template <typename T>
Heap<T>::Heap() {
heapArray.push_back(T()); // Insert a placeholder element at index 0
}
The constructor adds a placeholder element at index 0 to maintain consistency with 1-based indexing.
Now, let's implement the insert method to insert an element into the heap:
template <typename T>
void Heap<T>::insert(const T& value) {
heapArray.push_back(value);
heapifyUp(heapArray.size() - 1);
}
The insert method adds the element to the end of the heapArray and performs a heapify-up operation to restore the heap property.
Next, let's implement the heapifyUp and heapifyDown methods, which are responsible for maintaining the heap property:
template <typename T>
void Heap<T>::heapifyUp(int index) {
int parentIndex = index / 2;
while (index > 1 && heapArray[index] < heapArray[parentIndex]) {
std::swap(heapArray[index], heapArray[parentIndex]);
index = parentIndex;
parentIndex = index / 2;
}
}
template <typename T>
void Heap<T>::heapifyDown(int index) {
int leftChildIndex = 2 * index;
int rightChildIndex = 2 * index + 1;
int smallestIndex = index;
if (leftChildIndex < heapArray.size() && heapArray[leftChildIndex] < heapArray[smallestIndex]) {
smallestIndex = leftChildIndex;
}
if (rightChildIndex < heapArray.size() && heapArray[rightChildIndex] < heapArray[smallestIndex]) {
smallestIndex = rightChildIndex;
}
if (smallestIndex != index) {
std::swap(heapArray[index], heapArray[smallestIndex]);
heapifyDown(smallestIndex);
}
}
The heapifyUp method compares the value at the current index with its parent and swaps them if necessary to restore the heap property. It continues this process until the element reaches its correct position or becomes the root.
The heapifyDown method compares the value at the current index with its children and swaps it with the smallest child if necessary to maintain the heap property. It continues this process recursively until the element reaches its correct position or becomes a leaf node.
Next, let's implement the extractTop method to extract the top element (root) of the heap:
template <typename T>
T Heap<T>::extractTop() {
if (isEmpty()) {
throw std::out_of_range("Heap is empty");
}
T top = heapArray[1];
heapArray[1] = heapArray.back();
heapArray.pop_back();
heapifyDown(1);
return top;
}
The extractTop method returns the top element of the heap (root), which is the smallest element in a min-heap. It replaces the root with the last element in the heap, removes the last element, and performs a heapify-down operation to restore the heap property.
Finally, let's implement the isEmpty method to check if the heap is empty:
template <typename T>
bool Heap<T>::isEmpty() {
return heapArray.size() == 1;
}
The isEmpty method checks if the heapArray contains only the placeholder element (size 1) and returns true if it does.
To include the delete operation in the Heap implementation, we added the remove method. Here's the implementation:
template <typename T>
void Heap<T>::remove(const T& value) {
auto it = std::find(heapArray.begin(), heapArray.end(), value);
if (it == heapArray.end()) {
throw std::out_of_range("Element not found in the heap");
}
int index = std::distance(heapArray.begin(), it);
heapArray[index] = heapArray.back();
heapArray.pop_back();
if (index > 1 && heapArray[index] < heapArray[index / 2]) {
heapifyUp(index);
} else {
heapifyDown(index);
}
}
The remove method searches for the specified value in the heap using std::find. If the value is found, it replaces it with the last element in the heap, removes the last element, and performs either a heapify-up or heapify-down operation based on the updated element's position.
Finally, let's implement the isEmpty method to check if the heap is empty:
template <typename T>
bool Heap<T>::isEmpty() {
return heapArray.size() == 1;
}
The isEmpty method checks if the heapArray contains only the placeholder element (size 1) and returns true if it does.
Advantages of Heap
Efficient Priority Queue: Heaps provide an efficient implementation of a priority queue, allowing quick access to the highest (or lowest) priority element.
Efficient Heap Sort: Heap sort leverages the heap data structure to achieve efficient sorting in-place, making it suitable for large datasets.
Memory Management: Heaps are used in memory management systems to allocate and deallocate memory dynamically, ensuring efficient memory utilization.
Event Scheduling: Heaps are employed in event-driven simulations and scheduling algorithms to manage events based on their scheduled time.
Conclusion
The heap data structure is a powerful tool for managing priority-based operations efficiently. By understanding the principles behind the heap data structure and implementing it using OOP concepts and templates in C++, programmers can create robust applications that require efficient management of elements with priority.
The use of templates makes the Heap class generic, enabling it to handle different data types in a type-safe manner. This flexibility allows programmers to use the Heap class with integers, floating-point numbers, custom objects, or any other compatible data type.
Complete Code of Heap in C++ using Templates
Here is the complete code of the Heap class using templates in C++:
#include <iostream>
#include <vector>
#include <stdexcept>
template <typename T>
class Heap {
private:
std::vector<T> heapArray;
void heapifyUp(int index);
void heapifyDown(int index);
public:
Heap();
void insert(const T& value);
T extractTop();
void remove(const T& value);
bool isEmpty();
};
template <typename T>
Heap<T>::Heap() {
heapArray.push_back(T()); // Insert a placeholder element at index 0
}
template <typename T>
void Heap<T>::insert(const T& value) {
heapArray.push_back(value);
heapifyUp(heapArray.size() - 1);
}
template <typename T>
void Heap<T>::heapifyUp(int index) {
int parentIndex = index / 2;
while (index > 1 && heapArray[index] < heapArray[parentIndex]) {
std::swap(heapArray[index], heapArray[parentIndex]);
index = parentIndex;
parentIndex = index / 2;
}
}
template <typename T>
void Heap<T>::heapifyDown(int index) {
int leftChildIndex = 2 * index;
int rightChildIndex = 2 * index + 1;
int smallestIndex = index;
if (leftChildIndex < heapArray.size() && heapArray[leftChildIndex] < heapArray[smallestIndex]) {
smallestIndex = leftChildIndex;
}
if (rightChildIndex < heapArray.size() && heapArray[rightChildIndex] < heapArray[smallestIndex]) {
smallestIndex = rightChildIndex;
}
if (smallestIndex != index) {
std::swap(heapArray[index], heapArray[smallestIndex]);
heapifyDown(smallestIndex);
}
}
template <typename T>
T Heap<T>::extractTop() {
if (isEmpty()) {
throw std::out_of_range("Heap is empty");
}
T top = heapArray[1];
heapArray[1] = heapArray.back();
heapArray.pop_back();
heapifyDown(1);
return top;
}
template <typename T>
void Heap<T>::remove(const T& value) {
auto it = std::find(heapArray.begin(), heapArray.end(), value);
if (it == heapArray.end()) {
throw std::out_of_range("Element not found in the heap");
}
int index = std::distance(heapArray.begin(), it);
heapArray[index] = heapArray.back();
heapArray.pop_back();
if (index > 1 && heapArray[index] < heapArray[index / 2]) {
heapifyUp(index);
} else {
heapifyDown(index);
}
}
template <typename T>
bool Heap<T>::isEmpty() {
return heapArray.size() == 1;
}
With this implementation of the Heap class using templates, you can now create Heap objects with any desired data type, such as Heap<int>, Heap<double>, or Heap<std::string>. The class provides efficient operations to insert elements, extract the top element, and check if the heap is empty.
Here are two examples demonstrating the usage of the Heap class with different data types:
Example 1: Heap of Integers
#include <iostream>
#include "Heap.h" // Assuming the Heap class is implemented in a separate header file
int main() {
// Create a Heap of integers
Heap<int> integerHeap;
// Insert elements into the Heap
integerHeap.insert(10);
integerHeap.insert(5);
integerHeap.insert(7);
integerHeap.insert(15);
// Delete an element from the Heap
integerHeap.remove(7);
// Extract and print the top element
std::cout << "Top element: " << integerHeap.extractTop() << std::endl;
// Check if the Heap is empty
if (integerHeap.isEmpty()) {
std::cout << "Heap is empty" << std::endl;
} else {
std::cout << "Heap is not empty" << std::endl;
}
return 0;
}
In this example, we create a Heap of integers (Heap<int>) and perform various operations on it. We insert elements into the Heap (10, 5, 7, 15), delete an element (7) using the remove method, extract the top element (which should be the next smallest value due to the min-heap property), and check if the Heap is empty.
Example 2: Heap of Strings
#include <iostream>
#include <string>
#include "Heap.h" // Assuming the Heap class is implemented in a separate header file
int main() {
// Create a Heap of strings
Heap<std::string> stringHeap;
// Insert elements into the Heap
stringHeap.insert("apple");
stringHeap.insert("banana");
stringHeap.insert("orange");
stringHeap.insert("grape");
// Delete an element from the Heap
stringHeap.remove("orange");
// Extract and print the top element
std::cout << "Top element: " << stringHeap.extractTop() << std::endl;
// Check if the Heap is empty
if (stringHeap.isEmpty()) {
std::cout << "Heap is empty" << std::endl;
} else {
std::cout << "Heap is not empty" << std::endl;
}
return 0;
}
In this example, we create a Heap of strings (Heap<std::string>) and perform operations on it. We insert elements into the Heap ("apple", "banana", "orange", "grape"), delete an element ("orange") using the remove method, extract the top element (which should be the lexicographically next smallest string due to the min-heap property), and check if the Heap is empty.
Both examples demonstrate how the Heap class can be used with different data types by specifying the desired data type within the template brackets (Heap<int> and Heap<std::string>). This flexibility allows us to work with various data types and utilize the efficient operations provided by the Heap class, including inserting elements, extracting the top element, deleting a specific element, and checking if the heap is empty.
