Heaps in C++ | DSA in C++ - Software Development PDF Download

Introduction

Heaps are a fundamental data structure in computer science used to efficiently manage and organize data. They are particularly useful for tasks such as finding the largest or smallest elements in a collection or implementing priority queues. In this article, we will explore the concept of heaps, their properties, and how to implement them in C++.

What is a Heap?

Types of Heaps

There are two main types of heaps: max heap and min heap.

• Max Heap: In a max heap, the value of each node is greater than or equal to the values of its children. The maximum value is present at the root.
• Min Heap: In a min heap, the value of each node is less than or equal to the values of its children. The minimum value is present at the root.

Operations on Heaps

Heaps support the following basic operations:

• Insertion: Adding an element to the heap.
• Deletion: Removing an element from the heap.
• Peek: Viewing the value of the root element without removing it.

Implementing a Heap in C++

To implement a heap in C++, we can use the STL (Standard Template Library) 'priority_queue' container or build our own heap structure using an array.
Using 'priority_queue':

#include <queue>

#include <iostream>

int main() {

    std::priority_queue<int> maxHeap;

    maxHeap.push(5);

    maxHeap.push(3);

    maxHeap.push(8);

    maxHeap.push(2);

    while (!maxHeap.empty()) {

        std::cout << maxHeap.top() << " ";

        maxHeap.pop();

    }

    return 0;

}

Output:

8 5 3 2

Explanation:

• We include the '<queue>' and '<iostream>' header files.
• We create a 'priority_queue' named 'maxHeap' to store integers.
• We insert elements into the heap using the 'push()' function.
• We retrieve and remove elements from the heap using the 'top()' and pop() functions.

Implementing a heap using an array:

#include <iostream>

#include <vector>

void heapify(std::vector<int>& arr, int n, int i) {

    int largest = i;

    int left = 2 * i + 1;

    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])

        largest = left;

    if (right < n && arr[right] > arr[largest])

        largest = right;

    if (largest != i) {

        std::swap(arr[i], arr[largest]);

        heapify(arr, n, largest);

    }

}

void buildHeap(std::vector<int>& arr) {

    int n = arr.size();

    for (int i = n / 2 - 1; i >= 0; i--)

        heapify(arr, n, i);

}

int main() {

    std::vector<int> arr = {5, 3, 8, 2};

    buildHeap(arr);

    for (int num : arr)

        std::cout << num << " ";

    return 0;

}

Output:

8 5 3 2

Explanation:

• We include the '<iostream>' and '<vector>' header files.
• We define the 'heapify()' function to maintain the heap property by comparing the node with its children and swapping if necessary.
• We define the 'buildHeap()' function to build the heap from an array by repeatedly calling 'heapify()' starting from the last non-leaf node.
• We create a vector named 'arr' with the elements we want to form a heap.
• We call the 'buildHeap()' function to convert the vector into a heap.
• We print the elements of the heap.

Sample Problems and Solutions

Problem 1: Find the kth smallest element in an array using a min heap.

#include <queue>

#include <iostream>

int findKthSmallest(std::vector<int>& arr, int k) {

    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    for (int num : arr) {

        minHeap.push(num);

        if (minHeap.size() > k)

            minHeap.pop();

    }

    return minHeap.top();

}

int main() {

    std::vector<int> arr = {5, 8, 2, 1, 6};

    int k = 3;

    int kthSmallest = findKthSmallest(arr, k);

    std::cout << "The kth smallest element is: " << kthSmallest;

    return 0;

}

Output:

The kth smallest element is: 5

Explanation:

• We include the '<queue>' and '<iostream>' header files.
• We define the 'findKthSmallest()' function that takes an array 'arr' and an integer k as parameters.
• We create a min heap 'minHeap' using 'priority_queue' with the elements from the array.
• We maintain the heap size equal to 'k' by removing the largest elements if the heap size exceeds 'k'.
• We return the top element of the min heap, which is the kth smallest element.

Conclusion

Heaps are versatile data structures that offer efficient solutions for various problems such as finding extremal elements and implementing priority queues. In this article, we introduced the concept of heaps, discussed their types and operations, and provided examples of implementing heaps in C++. By understanding and applying heaps, you can enhance your problem-solving capabilities in the field of data structures and algorithms.