Introduction to Heaps

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property. The heap property states that for a max heap, the value of each node is greater than or equal to the values of its children. Likewise, for a min heap, the value of each node is less than or equal to the values of its children.

Heaps are commonly used to implement priority queues, which are data structures that allow efficient access to the element with the highest priority. The underlying heap structure ensures that the highest-priority element is always at the root of the tree, making it easy to retrieve.

Heapify and Build Heap

To maintain the heap property, two key operations are performed on heaps:

• Heapify: This operation ensures that a given node and its subtree satisfy the heap property. It compares the node with its children and swaps values if necessary to maintain the heap property.
• Build Heap: This operation builds a heap from an unordered array of elements. It starts from the first non-leaf node and repeatedly calls the heapify operation to ensure that all nodes satisfy the heap property.

Let's take a look at an example of heapify and build heap operations in C++:

xxxxxxxxxx

}

#include <iostream>

#include <vector>

using namespace std;

​

// Function to heapify a subtree rooted at index i

// n is the size of the heap

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

    int largest = i; // Initialize largest as root

    int left = 2 * i + 1;

    int right = 2 * i + 2;

​

    // If left child is larger than root

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

        largest = left;

​

    // If right child is larger than largest so far

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

        largest = right;

​

    // If largest is not root

    if (largest != i) {

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

​

        // Recursively heapify the affected sub-tree

        heapify(arr, n, largest);

    }

}

​

// Function to build a max heap