Heaps, Data Structures

Introduction to Heap

A heap is a specialized tree-based data structure that satisfies the heap property. It is widely used in computer science for tasks like implementing priority queues, heapsort, and algorithms requiring frequent access to the smallest or largest elements. Unlike a sorted structure, a heap is only partially ordered, prioritizing efficient operations over full sorting.

What is a Heap?

A heap is a complete binary tree, meaning all levels of the tree are fully filled except possibly the last, which is filled from left to right. Each node in a heap follows a specific hierarchical rule, known as the heap property, which ensures that operations like insertion, deletion, and peeking at the root are efficient. These operations generally have a time complexity of O(log n). Heaps are not just theoretical; they’re crucial in real-world applications like scheduling systems and optimization problems.

Definition and Properties

A heap is defined by two main characteristics:

1. Complete Binary Tree:
   
   Every level of the tree is fully filled except possibly the last, which is filled from left to right.

2. Heap Property:

   • In a Min-Heap, the value of each parent node is smaller than or equal to its children.
   • In a Max-Heap, the value of each parent node is larger than or equal to its children.

Because of these properties, heaps allow quick access to the smallest or largest element (depending on the type of heap).

Types of Heaps: Min-Heap and Max-Heap

Min-Heap:

The smallest element is always stored at the root of the tree. This type of heap maintains the condition that the value of each parent is less than or equal to its children. Min-heaps are commonly used in algorithms like Dijkstra’s shortest path and for merging sorted streams.

Max-Heap:

The largest element resides at the root in a Max-Heap. Here, the value of each parent is greater than or equal to its children. Max-heaps are frequently used in sorting algorithms (like heapsort) and scenarios requiring repeated access to the maximum element.

Both types of heaps leverage the heap property to ensure that insertions, deletions, and access to priority elements are efficient. The time complexity for these operations is typically O(log n).

Heap as a Complete Binary Tree

A heap is always represented as a complete binary tree, which ensures its structure is both efficient and predictable.

Complete Binary Tree Characteristics

1. Node Filling Order:
   
   In a complete binary tree, all levels are completely filled except possibly the last level. If the last level is not full, nodes are filled from left to right.

2. Efficient Representation:
   
   Heaps are typically stored in arrays for compactness. This representation eliminates the need for explicit parent-child pointers, making operations more efficient.

• The parent of a node at index i can be found at floor((i - 1) / 2).
• The left child of a node at index i is located at 2 * i + 1.
• The right child of a node at index i is at 2 * i + 2.

Visualization of Heaps

To better understand heaps, visualize them as trees:

Example Min-Heap (array: [1, 3, 5, 7, 9, 11]):

         1
       /   \
      3     5
     / \   / \
    7   9 11

In the above Min-Heap:

• The root (1) is the smallest element.
• Each parent node is smaller than its child nodes.

Example Max-Heap (array: [11, 9, 5, 7, 3, 1]):

         11
       /    \
      9      5
     / \    / \
    7   3  1

In this Max-Heap:

• The root (11) is the largest element.
• Each parent node is larger than its child nodes.

Applications of Heaps

Heaps are widely used in computer science for solving various problems efficiently.

Priority Queues

Heaps are the foundation for implementing priority queues, where elements are served based on their priority rather than their insertion order.

• In a Min-Heap, the smallest element has the highest priority.
• In a Max-Heap, the largest element has the highest priority. Operations like insert, delete, and peek are handled efficiently with a time complexity of O(log n).

Sorting (Heap Sort)

Heap Sort is an efficient comparison-based sorting algorithm that leverages the heap structure.

1. Build a Max-Heap (for ascending order).
2. Repeatedly extract the maximum element (root) and rebuild the heap.

Heap Sort has a time complexity of O(n log n) and is both in-place and non-recursive.

Graph Algorithms

Heaps are integral to many graph algorithms:

1. Prim's Algorithm:
   
   Used for finding the Minimum Spanning Tree (MST) of a graph. A Min-Heap is used to select the smallest edge at each step.

2. Dijkstra’s Algorithm:
   
   Used for finding the shortest path in a graph. A Min-Heap helps efficiently extract the node with the smallest tentative distance during each iteration.

These applications make heaps an essential part of algorithm design, particularly for tasks requiring efficient priority management and optimal selection strategies.

Fundamental Operations

Insertion in a Heap

The insertion operation in a heap involves adding a new element while maintaining the heap properties. Since a heap is a complete binary tree, the new element is always added at the next available position in the last level, ensuring the structure remains complete. However, this insertion may violate the heap property, requiring a process called Up-heapify (or Bubble-up) to restore the order.

Up-heapify (Bubble-up)

Up-heapify is the process of adjusting the position of the newly inserted element to maintain the heap property:

• In a Min-Heap, the parent node must be smaller than or equal to its children.
• In a Max-Heap, the parent node must be larger than or equal to its children.

The steps involved in up-heapify are:

1. Place the new element at the next available position (last level of the heap).
2. Compare the newly inserted element with its parent:
   • If the heap property is violated, swap the new element with its parent.
3. Repeat this process until the heap property is restored or the element becomes the root node.

The time complexity for up-heapify is O(log n) because the maximum height of the heap (a complete binary tree) is log n.

Example of Insertion

For a Min-Heap, consider inserting an element into the following heap:

Initial Heap:

       10  
      /  \  
    15    20  
   /  
  25  

Step 1: Insert 5 at the next available position (leftmost position in the last level).

       10  
      /  \  
    15    20  
   /  \  
  25   5  

Step 2: Perform up-heapify. Compare 5 with its parent (15) and swap.

       10  
      /  \  
     5    20  
   /  \  
  25   15  

Step 3: Compare 5 with its parent (10) and swap again.

        5  
      /  \  
     10   20  
   /  \  
  25   15  

Now the heap property is restored.

Maintaining Heap Properties

The key to maintaining heap properties during insertion is the up-heapify process, which ensures the parent-child relationships are adjusted appropriately. This guarantees the smallest (in a Min-Heap) or largest (in a Max-Heap) element remains at the root, and the tree remains a valid heap.

The insertion operation, combined with up-heapify, makes heaps efficient for dynamically managing priorities, ensuring that the root element is always accessible in O(1) time while maintaining the overall structure efficiently.

Deletion in a Heap

The deletion operation in a heap primarily involves removing the root element, which is the smallest (in a Min-Heap) or largest (in a Max-Heap) element. After removal, the heap property must be restored, which is achieved through a process called Down-heapify (or Bubble-down).

Removing the Root

Steps to remove the root from a heap:

1. Replace the root element with the last element in the heap (the rightmost element in the last level).
2. Remove the last element to maintain the complete binary tree structure.
3. Perform down-heapify to restore the heap property.

The time complexity for removing the root is O(log n) because the down-heapify operation traverses at most the height of the heap.

Down-heapify (Bubble-down)

Down-heapify adjusts the position of the new root element to maintain the heap property:

• In a Min-Heap, the parent must be smaller than or equal to its children.
• In a Max-Heap, the parent must be larger than or equal to its children.

Steps for down-heapify:

1. Compare the root element with its children.
2. Swap the root with the smaller child (for Min-Heap) or the larger child (for Max-Heap).
3. Repeat this process until the heap property is restored or the element reaches a leaf node.

Example of Deletion

For a Min-Heap, consider deleting the root element from the following heap:

Initial Heap:

       5  
      /  \  
    10    20  
   /  \  
  25   15  

Step 1: Replace the root (5) with the last element (15).

       15  
      /  \  
    10    20  
   /  \  
  25   15

Step 2: Remove the last element (15).

       15  
      /  \  
    10    20  
   /  
  25  

Step 3: Perform down-heapify. Compare 15 with its children (10 and 20) and swap with 10.

       10  
      /  \  
    15    20  
   /  
  25  

Step 4: Compare 15 with its new child (25). No swap is needed as the heap property is restored.

Building a Heap

Constructing a heap from an unsorted array can be done in two ways: incremental insertion and optimal heap construction.

Incremental Insertion

This method involves inserting each element of the array into an initially empty heap, one at a time. After each insertion, the heap property is restored using up-heapify.

Steps:

1. Start with an empty heap.
2. Insert each element from the array sequentially.
3. Perform up-heapify for each insertion to maintain the heap property.

Time Complexity:

Incremental insertion has a time complexity of O(n log n) because each insertion takes O(log n) and there are n elements to insert.

Optimal Heap Construction Using Heapify

This is the most efficient way to build a heap from an unsorted array. It involves treating the array as a complete binary tree and applying down-heapify from the last non-leaf node to the root.

Steps:

1. Start by arranging the array as a complete binary tree.
2. Identify the last non-leaf node (at index n/2 - 1 in a zero-based array).
3. Perform down-heapify on each node from this index up to the root.

Time Complexity:

Optimal heap construction has a time complexity of O(n) due to the cumulative cost of down-heapify being proportional to the height of the nodes, which decreases as you move up the tree.

Both methods build a valid heap, but the optimal heap construction using heapify is significantly faster for large datasets, making it the preferred approach in most scenarios.

Heap Implementation in C++

A heap is a specialized tree-based data structure that satisfies the heap property. It is used for efficiently accessing the highest or lowest priority element. The heap can be implemented using an array or a dynamic array (e.g., vector in C++). Below, we will implement a Min-Heap using a C++ class. The key operations include insertion, deletion, and heapifying.

Creation of the Heap

To create a Min-Heap in C++, we need a class that will manage the heap structure. A heap can be efficiently implemented using a dynamic array (e.g., vector<int>). The class will contain private variables to store the heap and its size, and a constructor to initialize the heap.

#include <iostream>
#include <vector>
using namespace std;

class MinHeap {
private:
    vector<int> heap;  // Vector to store heap elements
    int size;          // Current size of the heap

public:
    MinHeap();  // Constructor to initialize the heap
};

Attributes Explanation

1. heap:
   
   This is a vector that will store the elements of the heap. A heap is a complete binary tree, and in this array-based representation, the elements are stored in such a way that the smallest (or largest) element can always be accessed quickly. The heap maintains the heap property, where each parent is smaller than or equal to its children in a Min-Heap.

2. size:
   
   This integer variable keeps track of the current number of elements in the heap. It helps in knowing where the next element will be inserted and allows us to perform heap operations effectively.

Constructor Explanation

The constructor MinHeap() is responsible for initializing the heap when a new MinHeap object is created.

MinHeap::MinHeap() {
    size = 0;  // Initialize size to 0 since the heap is empty initially
}

1. size = 0: When a heap is first created, it is empty. Therefore, the size is set to 0, indicating that there are no elements in the heap initially. The heap array (heap) will be dynamically resized as elements are added.

This constructor simply initializes the heap's size and sets it up for future operations. In the next steps, we will add more functionality to the class (such as inserting elements into the heap).

Operations on Heap

Operations on heaps are essential for efficiently managing priority queues. These operations include insertion, removal of the maximum element (root), and maintaining the heap property through heapify-up and heapify-down.

Insertion in Heap

When inserting an element into the heap, we add the element at the end of the heap array and then heapify-up to ensure the heap property is maintained. Heapify-up ensures that the parent of a node is always larger than or equal to the node in a Max-Heap.

Steps for insertion:

1. Add the new element at the end of the heap.
2. Compare the new element with its parent. If the parent is smaller, swap the two.
3. Continue this process until the heap property is restored (or the element becomes the root).

// Method to insert an element into the heap
void insert(int key) {
    heap.push_back(key);  // Add the new element at the end of the heap
    int index = size() - 1;
    heapifyUp(index);  // Restore the heap property by moving up
}

Time Complexity: O(log n)

• The insertion may require us to move up through the tree, which takes logarithmic time in terms of the number of elements.

Heapify-Up (Bubble-Up)

The heapifyUp method is used during the insertion process to maintain the heap property. It compares the inserted element with its parent, and if necessary, swaps them.

// Helper method to move the inserted element up to restore the heap property
void heapifyUp(int index) {
    // If the current index is valid and the parent is smaller than the current element
    if (index && heap[parent(index)] < heap[index]) {
        // Swap the current element with the parent
        swap(heap[index], heap[parent(index)]);

        // Recursively move up the heap to restore the property
        heapifyUp(parent(index));
    }
}

Time Complexity: O(log n)

• Since this operation moves up through the tree, the time complexity is logarithmic.

Removing the Maximum Element (Root Removal)

When removing the root element (the maximum element in a Max-Heap), we replace it with the last element in the heap and then perform heapify-down to maintain the heap property.

Steps for removal:

1. Replace the root element with the last element in the heap.
2. Remove the last element.
3. Perform heapify-down from the root to restore the heap property by ensuring the largest element is at the root.

// Method to remove the root (maximum element) from the heap
void removeMax() {
    if (isEmpty()) {
        cout << "Heap is empty\n";
        return;
    }

    // If only one element exists, simply remove it
    if (size() == 1) {
        heap.pop_back();
        return;
    }

    // Replace root with the last element in the heap
    heap[0] = heap.back();
    heap.pop_back();  // Remove the last element

    // Restore the heap property by down-heapifying from the root
    heapifyDown(0);
}

Time Complexity: O(log n)

• The down-heapify operation moves down the tree, so the time complexity is logarithmic.

Heapify-Down (Bubble-Down)

The heapifyDown method is used when the root element is removed. It compares the root with its children and swaps it with the larger child to maintain the heap property.

// Helper method to move the element down to restore the heap property
void heapifyDown(int index) {
    int left = leftChild(index);
    int right = rightChild(index);

    int largestChild = index;  // Assume the largest is the current node

    // Check if left child exists and is greater than the current node
    if (left < size() && heap[left] > heap[index])
        largestChild = left;

    // Check if right child exists and is greater than the current largest child
    if (right < size() && heap[right] > heap[largestChild])
        largestChild = right;

    // If the largest child is not the current node, swap and continue down-heapifying
    if (largestChild != index) {
        swap(heap[index], heap[largestChild]);
        heapifyDown(largestChild);  // Recursively down-heapify
    }
}

Time Complexity: O(log n)

• Since this operation moves down through the tree, the time complexity is logarithmic.

Helper Functions

These methods help manage the structure of the heap and facilitate heap operations such as finding the parent or child of a node.

// Helper method to find the parent index of a node
int parent(int index) { 
    return (index - 1) / 2; 
}

// Helper method to find the left child index of a node
int leftChild(int index) { 
    return (2 * index + 1); 
}

// Helper method to find the right child index of a node
int rightChild(int index) { 
    return (2 * index + 2); 
}

Size and Empty Check

These methods check the size of the heap and whether the heap is empty.

// Get the size of the heap
int size() { 
    return heap.size(); 
}

// Check if the heap is empty
bool isEmpty() { 
    return size() == 0; 
}

Print the Heap

To print the elements of the heap, we simply iterate through the heap and print each element.

// Method to print the elements of the heap
void printHeap() {
    for (int i = 0; i < size(); i++)
        cout << heap[i] << " ";
    cout << "\n";
}

The operations described above allow you to insert elements, remove the maximum element, and maintain the heap property. By breaking the heap operations into manageable helper functions like heapifyUp, heapifyDown, and removeMax, the heap remains efficient and easy to understand. The time complexities for each of these operations are logarithmic, making the heap a powerful tool for priority-based operations.

Building a Heap

There are two primary methods to construct a heap from an unsorted array: incremental insertion and optimal heap construction using heapify. Each method has its own approach to arranging the elements to satisfy the heap property.

Incremental Insertion

In the incremental insertion method, we start with an empty heap and insert each element from the array one at a time. After each insertion, we apply heapify-up to maintain the heap property, which ensures that the parent node is always greater than or equal to the child node in a Max-Heap.

Steps:

1. Begin with an empty heap.
2. Insert each element from the array one by one into the heap.
3. After inserting each element, apply the heapify-up process to restore the heap property, ensuring that the new element is in the correct position within the heap.

// Method to build a heap using incremental insertion
void buildHeapIncremental(const vector<int>& arr) {
    for (int key : arr) {
        insert(key);  // Insert each element and restore the heap property
    }
}

Time Complexity:

The time complexity of the incremental insertion method is O(n log n). This is because each insertion requires O(log n) time to maintain the heap property, and since we perform the insertion for all n elements, the overall time complexity becomes O(n log n).

Optimal Heap Construction Using Heapify

The optimal heap construction method, also known as heapify, is a more efficient way to build a heap from an unsorted array. In this method, the array is first treated as a complete binary tree, and then heapify-down is applied starting from the last non-leaf node up to the root. This ensures that the heap property is maintained in the most efficient way possible.

Steps:

1. First, arrange the array elements as a complete binary tree.
2. Identify the last non-leaf node, which is located at index n/2 - 1 (in a zero-based array).
3. Starting from this node, apply heapify-down recursively for each node in reverse order, moving from the last non-leaf node up to the root, ensuring that the heap property is maintained at every step.

// Method to build a heap using optimal heapify
void buildHeapOptimal(const vector<int>& arr) {
    heap = arr;  // Copy the input array to the heap
    int n = size();

    // Start from the last non-leaf node and apply down-heapify
    for (int i = n / 2 - 1; i >= 0; --i) {
        heapifyDown(i);  // Restore heap property starting from the last non-leaf node
    }
}

Time Complexity:

The time complexity of optimal heap construction using heapify is O(n). This is because the cost of applying heapify-down is proportional to the height of the tree, and as you move up the tree, the height decreases. Thus, the total cost of heapifying all nodes is linear in terms of the number of elements, resulting in a time complexity of O(n).

Full Code Implementation of Heap in C++

A heap is a special tree-based data structure that satisfies the heap property. In a Max-Heap, for any given node, the value of the node is greater than or equal to the values of its children. This property ensures that the maximum element is always at the root. Heaps are commonly used in implementing priority queues, where the maximum or minimum element can be accessed in constant time.

Below is the full code implementation of a Max-Heap in C++ using an array. It includes the construction of the heap, insertion, removal of the maximum element (root), heapifying operations, and other utility methods.

#include <iostream>
#include <vector>
using namespace std;

class Heap {
private:
    vector<int> heap;  // Vector to store heap elements

    // Helper methods to get the parent, left child, and right child indices
    int parent(int index) { 
        return (index - 1) / 2; 
    }

    int leftChild(int index) { 
        return (2 * index + 1); 
    }

    int rightChild(int index) { 
        return (2 * index + 2); 
    }

    // Heapify-up (used for insert operation)
    void heapifyUp(int index) {
        // If the current index is valid and the parent is smaller than the current element
        if (index && heap[parent(index)] < heap[index]) {
            // Swap the current element with the parent
            swap(heap[index], heap[parent(index)]);
            // Recursively move up the heap to restore the property
            heapifyUp(parent(index));
        }
    }

    // Heapify-down (used for removeMax operation)
    void heapifyDown(int index) {
        int left = leftChild(index);
        int right = rightChild(index);

        int largestChild = index;  // Assume the largest is the current node

        // Check if left child exists and is greater than the current node
        if (left < size() && heap[left] > heap[index]) 
            largestChild = left;

        // Check if right child exists and is greater than the current largest child
        if (right < size() && heap[right] > heap[largestChild]) 
            largestChild = right;

        // If the largest child is not the current node, swap and continue down-heapifying
        if (largestChild != index) {
            swap(heap[index], heap[largestChild]);
            heapifyDown(largestChild);  // Recursively down-heapify
        }
    }

public:
    // Constructor
    Heap() {}

    // Destructor
    ~Heap() {}

    // Get the size of the heap
    int size() { 
        return heap.size(); 
    }

    // Check if the heap is empty
    bool isEmpty() { 
        return size() == 0; 
    }

    // Insert a new element into the heap
    void insert(int key) {
        heap.push_back(key);  // Add the new element at the end of the heap
        int index = size() - 1;
        heapifyUp(index);  // Restore the heap property by moving up
    }

    // Get the maximum element (root) from the heap
    int getMax() {
        if (isEmpty()) {
            cout << "Heap is empty\n";
            return -1;
        }
        return heap[0];
    }

    // Remove the maximum element (root) from the heap
    void removeMax() {
        if (isEmpty()) {
            cout << "Heap is empty\n";
            return;
        }

        // If only one element exists, simply remove it
        if (size() == 1) {
            heap.pop_back();
            return;
        }

        // Replace root with the last element in the heap
        heap[0] = heap.back();
        heap.pop_back();  // Remove the last element

        // Restore the heap property by down-heapifying from the root
        heapifyDown(0);
    }

    // Print the elements of the heap
    void printHeap() {
        for (int i = 0; i < size(); i++)
            cout << heap[i] << " ";
        cout << "\n";
    }

    // Build a heap from an unsorted array using incremental insertion
    void buildHeapIncremental(const vector<int>& arr) {
        for (int key : arr) {
            insert(key);  // Insert each element and restore the heap property
        }
    }

    // Build a heap using optimal heapify
    void buildHeapOptimal(const vector<int>& arr) {
        heap = arr;  // Copy the input array to the heap
        int n = size();

        // Start from the last non-leaf node and apply down-heapify
        for (int i = n / 2 - 1; i >= 0; --i) {
            heapifyDown(i);  // Restore heap property starting from the last non-leaf node
        }
    }
};

// Main function to test the Heap implementation
int main() {
    Heap maxHeap;

    // Insert elements into the heap
    maxHeap.insert(10);
    maxHeap.insert(20);
    maxHeap.insert(5);
    maxHeap.insert(30);
    maxHeap.insert(15);

    // Print the heap elements
    cout << "Max Heap after insertions: ";
    maxHeap.printHeap();

    // Remove the maximum element (root)
    maxHeap.removeMax();
    cout << "Max Heap after removing max element: ";
    maxHeap.printHeap();

    // Build a heap from an unsorted array using incremental insertion
    vector<int> arr = {40, 30, 20, 50, 10, 60};
    maxHeap.buildHeapIncremental(arr);
    cout << "Max Heap after building using incremental insertion: ";
    maxHeap.printHeap();

    // Build a heap using optimal heapify
    vector<int> arr2 = {10, 20, 30, 40, 50, 60};
    maxHeap.buildHeapOptimal(arr2);
    cout << "Max Heap after building using optimal heapify: ";
    maxHeap.printHeap();

    return 0;
}

This code demonstrates the full implementation of a Max-Heap in C++. It includes various operations like insertion, removal of the maximum element, heapify-up, heapify-down, as well as methods to build the heap using both incremental insertion and optimal heapify.

Key Points of the Code:

• Heap Operations: The insert function adds an element to the heap and restores the heap property using heapifyUp. The removeMax function removes the root (maximum element) and restores the heap using heapifyDown.
• Building a Heap: Two methods for building the heap from an unsorted array are provided: incremental insertion (buildHeapIncremental) and optimal heap construction (buildHeapOptimal).
• Helper Functions: The parent, leftChild, and rightChild functions are used to find the indices of the parent and children of a given node.

Time Complexity:

• Insertion: O(log n) due to the heapifyUp operation.
• Removing Max: O(log n) due to the heapifyDown operation.
• Building Heap Incrementally: O(n log n) because each insertion takes O(log n) time.
• Building Heap Using Heapify: O(n) because it performs heapify in a bottom-up manner.