Heap Data Structure

Board Infinity -

What is Heap Data Structure?

In a Heap, a unique type of tree-based data structure, in which the tree is a complete binary tree.

Heap Data Structure Operations

  • Heapify: A technique for making a heap out of an array.
  • Insertion: The process of inserting an element into an existing heap with time complexity O.
  • Deletion: The process of deleting the top element of the heap or the element with the highest priority, then organizing the heap and returning the element with time complexity O.
  • Peek: To inspect or locate the heap's most recent constituent (max or min element for max and min heap).

Types of Heap Data Structure

Normally, there can be two types of Heaps:

  1. Max-Heap: In a Max-Heap, the key at the root node must be greater than the keys at all of its descendants. The same property must be true for all subtrees in that Binary Tree.
  2. Min-Heap: In a Min-Heap, the key at the root node must be the smallest of all the keys at its descendants. The same property must be true for all subtrees in that Binary Tree.

Min Heap and Max Heap Implementation in C++

Max Heap construction algorithm

  1. Add a new node to the end of the heap.
  2. Give the node a new value.
  3. Compare this child node's value to that of its parent.
  4. If the value of parent is less than the value of child, switch them.
  5. Steps 3 and 4 should be repeated until Heap property holds.

Syntax

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>
using namespace std;
// Data structure to store a max-heap node
struct PriorityQueue
{
private:
    // vector to store heap elements
    vector<int> A;
    // return parent of `A[i]`
    // don't call this function if `i` is already a root node
    int PARENT(int i) {
        return (i - 1) / 2;
    }
    // return left child of `A[i]`
    int LEFT(int i) {
        return (2*i + 1);
    }
    // return right child of `A[i]`
    int RIGHT(int i) {
        return (2*i + 2);
    }
    // Recursive heapify-down algorithm.
    // The node at index `i` and its two direct children
    // violates the heap property
    void heapify_down(int i)
    {
        // get left and right child of node at index `i`
        int left = LEFT(i);
        int right = RIGHT(i);
        int largest = i;
        // compare `A[i]` with its left and right child
        // and find the largest value
        if (left < size() && A[left] > A[i]) {
            largest = left;
        }
        if (right < size() && A[right] > A[largest]) {
            largest = right;
        }
        // swap with a child having greater value and
        // call heapify-down on the child
        if (largest != i)
        {
            swap(A[i], A[largest]);
            heapify_down(largest);
        }
    }
    // Recursive heapify-up algorithm
    void heapify_up(int i)
    {
        // check if the node at index `i` and its parent violate the heap property
        if (i && A[PARENT(i)] < A[i])
        {
            // swap the two if heap property is violated
            swap(A[i], A[PARENT(i)]);
            // call heapify-up on the parent
            heapify_up(PARENT(i));
        }
    }
public:
    // return size of the heap
    unsigned int size() {
        return A.size();
    }
    // Function to check if the heap is empty or not
    bool empty() {
        return size() == 0;
    }
    // insert key into the heap
    void push(int key)
    {
        // insert a new element at the end of the vector
        A.push_back(key);
        // get element index and call heapify-up procedure
        int index = size() - 1;
        heapify_up(index);
    }
    // Function to remove an element with the highest priority (present at the root)
    void pop()
    {
        try {
            // if the heap has no elements, throw an exception
            if (size() == 0)
            {
                throw out_of_range("Vector<X>::at() : "
                        "index is out of range(Heap underflow)");
            }
            // replace the root of the heap with the last element
            // of the vector
            A[0] = A.back();
            A.pop_back();
            // call heapify-down on the root node
            heapify_down(0);
        }
        // catch and print the exception
        catch (const out_of_range &oor) {
            cout << endl << oor.what();
        }
    }
    // Function to return an element with the highest priority (present at the root)
    int top()
    {
        try {
            // if the heap has no elements, throw an exception
            if (size() == 0)
            {
                throw out_of_range("Vector<X>::at() : "
                        "index is out of range(Heap underflow)");
            }
            // otherwise, return the top (first) element
            return A.at(0);        // or return A[0];
        }
        // catch and print the exception
        catch (const out_of_range &oor) {
            cout << endl << oor.what();
        }
    }
};
// Max Heap implementation in C++
int main()
{
    PriorityQueue pq;
    // Note: The element's value decides priority
    pq.push(3);
    pq.push(2);
    pq.push(15);
    cout << "Size is " << pq.size() << endl;
    cout << pq.top() << " ";
    pq.pop();
    cout << pq.top() << " ";
    pq.pop();
    pq.push(5);
    pq.push(4);
    pq.push(45);
    cout << endl << "Size is " << pq.size() << endl;
    cout << pq.top() << " ";
    pq.pop();
    cout << pq.top() << " ";
    pq.pop();
    cout << pq.top() << " ";
    pq.pop();
    cout << pq.top() << " ";
    pq.pop();
    cout << endl << boolalpha << pq.empty();
    pq.top();    // top operation on an empty heap
    pq.pop();    // pop operation on an empty heap
    return 0;
}

Output:

Size is 3
15 3
Size is 4
45 5 4 2
true
Vector::at() : index is out of range(Heap underflow)
Vector::at() : index is out of range(Heap underflow)

write your code here: Coding Playground

Min Heap construction algorithm

In the Min Heap construction algorithm, we expect the child node's value to be less than the parent node's value.

Syntax:

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>
using namespace std;
// Data structure to store a min-heap node
struct PriorityQueue
{
private:
    // vector to store heap elements
    vector<int> A;
    // return parent of `A[i]`
    // don't call this function if `i` is already a root node
    int PARENT(int i) {
        return (i - 1) / 2;
    }
    // return left child of `A[i]`
    int LEFT(int i) {
        return (2*i + 1);
    }
    // return right child of `A[i]`
    int RIGHT(int i) {
        return (2*i + 2);
    }
    // Recursive heapify-down algorithm.
    // The node at index `i` and its two direct children
    // violates the heap property
    void heapify_down(int i)
    {
        // get left and right child of node at index `i`
        int left = LEFT(i);
        int right = RIGHT(i);
        int smallest = i;
        // compare `A[i]` with its left and right child
        // and find the smallest value
        if (left < size() && A[left] < A[i]) {
            smallest = left;
        }
        if (right < size() && A[right] < A[smallest]) {
            smallest = right;
        }
        // swap with a child having lesser value and
        // call heapify-down on the child
        if (smallest != i)
        {
            swap(A[i], A[smallest]);
            heapify_down(smallest);
        }
    }
    // Recursive heapify-up algorithm
    void heapify_up(int i)
    {
        // check if the node at index `i` and its parent violate the heap property
        if (i && A[PARENT(i)] > A[i])
        {
            // swap the two if heap property is violated
            swap(A[i], A[PARENT(i)]);
            // call heapify-up on the parent
            heapify_up(PARENT(i));
        }
    }
public:
    // return size of the heap
    unsigned int size() {
        return A.size();
    }
    // Function to check if the heap is empty or not
    bool empty() {
        return size() == 0;
    }
    // insert key into the heap
    void push(int key)
    {
        // insert a new element at the end of the vector
        A.push_back(key);
        // get element index and call heapify-up procedure
        int index = size() - 1;
        heapify_up(index);
    }
    // Function to remove an element with the lowest priority (present at the root)
    void pop()
    {
        try {
            // if the heap has no elements, throw an exception
            if (size() == 0)
            {
                throw out_of_range("Vector<X>::at() : "
                        "index is out of range(Heap underflow)");
            }
            // replace the root of the heap with the last element
            // of the vector
            A[0] = A.back();
            A.pop_back();
            // call heapify-down on the root node
            heapify_down(0);
        }
        // catch and print the exception
        catch (const out_of_range &oor) {
            cout << endl << oor.what();
        }
    }
    // Function to return an element with the lowest priority (present at the root)
    int top()
    {
        try {
            // if the heap has no elements, throw an exception
            if (size() == 0)
            {
                throw out_of_range("Vector<X>::at() : "
                        "index is out of range(Heap underflow)");
            }
            // otherwise, return the top (first) element
            return A.at(0);        // or return A[0];
        }
        // catch and print the exception
        catch (const out_of_range &oor) {
            cout << endl << oor.what();
        }
    }
};
// Min Heap implementation in C++
int main()
{
    PriorityQueue pq;
    // Note: The element's value decides priority
    pq.push(3);
    pq.push(2);
    pq.push(15);
    cout << "Size is " << pq.size() << endl;
    cout << pq.top() << " ";
    pq.pop();
    cout << pq.top() << " ";
    pq.pop();
    pq.push(5);
    pq.push(4);
    pq.push(45);
    cout << endl << "Size is " << pq.size() << endl;
    cout << pq.top() << " ";
    pq.pop();
    cout << pq.top() << " ";
    pq.pop();
    cout << pq.top() << " ";
    pq.pop();
    cout << pq.top() << " ";
    pq.pop();
    cout << endl << boolalpha << pq.empty();
    pq.top();    // top operation on an empty heap
    pq.pop();    // pop operation on an empty heap
    return 0;
}

Output:

Size is 3
2 3
Size is 4
4 5 15 45
true
Vector::at() : index is out of range(Heap underflow)
Vector::at() : index is out of range(Heap underflow)

write your code here: Coding Playground

Time complexity

push() and pop() takes O(log(n)) time.

peek() and size() and isEmpty() takes O(1) time.