Building Heap from Array

Introduction to Heaps and Heap Data Structure

Navi.

A Heap is a specialized tree-based data structure that satisfies the Heap property: in a Max Heap, the value of each node is greater than or equal to the values of its children, while in a Min Heap, the value of each node is less than or equal to the values of its children. Heaps are often used to implement priority queues, where the element with the highest (or lowest) priority is always at the root of the heap.

Heaps have several important properties:

  1. Complete Binary Tree: A Heap is always a complete binary tree, meaning that all levels of the tree, except possibly the last one, are completely filled, and all nodes in the last level are as far left as possible.
  2. Heap Property: In a Max Heap, the value of each node is greater than or equal to the values of its children. In a Min Heap, the value of each node is less than or equal to the values of its children.
  3. Efficient Operations: Heaps support efficient operations such as insertion, deletion, and finding the maximum (or minimum) element, all with a time complexity of O(log n), where n is the number of elements in the heap.

Heaps have a wide range of applications, including:

  • Priority Queues: Heaps are commonly used to implement priority queues, where the element with the highest (or lowest) priority is always at the root of the heap.
  • Heap Sort: Heaps can be used to implement the Heap Sort algorithm, which is an efficient comparison-based sorting algorithm.
  • Job Scheduling: Heaps can be used to schedule jobs or tasks based on their priority or deadline.
  • Huffman Coding: Heaps are used in the construction of Huffman trees, which are used for data compression.
  • k-Largest/Smallest Elements: Heaps can be used to efficiently find the k-largest or k-smallest elements in an array.

Building a Heap from an Array

The process of building a Heap from an array is called Heap Construction or Heapification. The idea is to convert the given array into a valid Heap, either a Max Heap or a Min Heap, depending on the application.

The algorithm for building a Heap from an array is as follows:

  1. Start with the last non-leaf node (the parent of the last node) in the array.
  2. Apply the Heapify operation on this node to ensure that it satisfies the Heap property.
  3. Repeat step 2 for all the non-leaf nodes in the array, starting from the last non-leaf node and moving towards the root (the first element in the array).

The Heapify operation is a recursive procedure that ensures that a subtree rooted at a given node satisfies the Heap property. It works as follows:

  1. Find the index of the largest (or smallest, for a Min Heap) element among the node, its left child, and its right child.
  2. If the largest (or smallest) element is not the node itself, swap the node with the largest (or smallest) child.
  3. Recursively call the Heapify operation on the subtree rooted at the swapped node.

The time complexity of building a Heap from an array is O(n), where n is the number of elements in the array. This is because the Heapify operation takes O(log n) time for each non-leaf node, and there are approximately n/2 non-leaf nodes in the array.

Here‘s the pseudocode for building a Max Heap from an array:

function buildHeap(arr):
    n = length of arr
    startIdx = (n // 2) - 1 # Index of the last non-leaf node

    for i from startIdx downto 0:
        heapify(arr, n, i)

function heapify(arr, n, i):
    largest = i # Initialize largest as root
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        swap arr[i] and arr[largest]
        heapify(arr, n, largest)

Here‘s the implementation of building a Max Heap from an array in various programming languages:

C++:
“`cpp
#include
using namespace std;

void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int l = 2 i + 1; // left = 2i + 1
int r = 2 i + 2; // right = 2i + 2

// If left child is larger than root
if (l < n && arr[l] > arr[largest])
    largest = l;

// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
    largest = r;

// If largest is not root
if (largest != i) {
    swap(arr[i], arr[largest]);
    // Recursively heapify the affected sub-tree
    heapify(arr, n, largest);
}

}

void buildHeap(int arr[], int n) {
// Index of last non-leaf node
int startIdx = (n / 2) – 1;

// Perform reverse level order traversal
// from last non-leaf node and heapify
// each node
for (int i = startIdx; i >= 0; i--) {
    heapify(arr, n, i);
}

}

int main() {
int arr[] = {1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17};
int n = sizeof(arr) / sizeof(arr[0]);

buildHeap(arr, n);

// Final Heap:
//              17
//            /    \
//          15      13
//         /  \     / \
//        9     6  5   10
//       / \   / \
//      4   8 3   1

return 0;

}


Python:
```python
def heapify(arr, n, i):
    largest = i  # Initialize largest as root
    l = 2 * i + 1  # left = 2*i + 1
    r = 2 * i + 2  # right = 2*i + 2

    # If left child is larger than root
    if l < n and arr[l] > arr[largest]:
        largest = l

    # If right child is larger than largest so far
    if r < n and arr[r] > arr[largest]:
        largest = r

    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        # Recursively heapify the affected sub-tree
        heapify(arr, n, largest)

def buildHeap(arr, n):
    # Index of last non-leaf node
    startIdx = (n // 2) - 1

    # Perform reverse level order traversal
    # from last non-leaf node and heapify
    # each node
    for i in range(startIdx, -1, -1):
        heapify(arr, n, i)

if __name__ == ‘__main__‘:
    arr = [1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17]
    n = len(arr)
    buildHeap(arr, n)

    # Final Heap:
    #              17
    #            /    \
    #          15      13
    #         /  \     / \
    #        9     6  5   10
    #       / \   / \
    #      4   8 3   1

Java:

public class GfG {
    // To heapify a subtree rooted with node i which is
    // an index in arr[]. N is size of heap
    static void heapify(int arr[], int n, int i) {
        int largest = i; // Initialize largest as root
        int l = 2 * i + 1; // left = 2*i + 1
        int r = 2 * i + 2; // right = 2*i + 2

        // If left child is larger than root
        if (l < n && arr[l] > arr[largest])
            largest = l;

        // If right child is larger than largest so far
        if (r < n && arr[r] > arr[largest])
            largest = r;

        // If largest is not root
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }

    // Function to build a Max-Heap from the given array
    static void buildHeap(int arr[], int n) {
        // Index of last non-leaf node
        int startIdx = (n / 2) - 1;

        // Perform reverse level order traversal
        // from last non-leaf node and heapify
        // each node
        for (int i = startIdx; i >= 0; i--) {
            heapify(arr, n, i);
        }
    }

    public static void main(String[] args) {
        int arr[] = {1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17};
        int n = arr.length;
        buildHeap(arr, n);

        // Final Heap:
        //              17
        //            /    \
        //          15      13
        //         /  \     / \
        //        9     6  5   10
        //       / \   / \
        //      4   8 3   1
    }
}

Heap Representation and Operations

Heaps are commonly represented using an array. The root of the heap is stored at index 0, and the children of the node at index i are stored at indices 2*i+1 (left child) and 2*i+2 (right child). The parent of the node at index i is stored at index (i-1)/2.

The main operations that can be performed on a Heap are:

  1. Heapify: As discussed earlier, the Heapify operation ensures that a subtree rooted at a given node satisfies the Heap property.
  2. Insert: Adding a new element to the Heap while maintaining the Heap property.
  3. Extract Max/Min: Removing the maximum (or minimum) element from the Heap, which is always at the root.
  4. Decrease/Increase Key: Decreasing (or increasing) the value of a node in the Heap and then restoring the Heap property.

The time complexity of these operations is O(log n), where n is the number of elements in the Heap.

Practical Applications of Heap Data Structure

Heaps have a wide range of practical applications, including:

  1. Priority Queues: Heaps are commonly used to implement priority queues, where the element with the highest (or lowest) priority is always at the root of the heap.
  2. Heap Sort: Heaps can be used to implement the Heap Sort algorithm, which is an efficient comparison-based sorting algorithm with a time complexity of O(n log n).
  3. Job Scheduling: Heaps can be used to schedule jobs or tasks based on their priority or deadline.
  4. Huffman Coding: Heaps are used in the construction of Huffman trees, which are used for data compression.
  5. k-Largest/Smallest Elements: Heaps can be used to efficiently find the k-largest or k-smallest elements in an array.

Comparison with Other Data Structures

Heaps are often compared to other tree-based data structures, such as Binary Search Trees (BSTs):

  1. Structure: Heaps are always complete binary trees, while BSTs can have an arbitrary structure.
  2. Heap Property: Heaps satisfy the Heap property (either Max Heap or Min Heap), while BSTs satisfy the Binary Search Tree property.
  3. Operations: Heaps support efficient operations like Insert, Extract Max/Min, and Decrease/Increase Key in O(log n) time, while BSTs support efficient operations like Search, Insert, and Delete in O(log n) time.
  4. Applications: Heaps are primarily used for implementing priority queues and sorting algorithms, while BSTs are more versatile and can be used for a wider range of applications, such as searching, range queries, and predecessor/successor operations.

Advanced Topics and Variations

While the basic Heap data structure is widely used, there are also several advanced topics and variations that are worth exploring:

  1. Binomial Heaps: Binomial Heaps are a type of Heap that are particularly efficient for implementing mergeable priority queues.
  2. Fibonacci Heaps: Fibonacci Heaps are a more advanced version of Heaps that can perform certain operations, such as Decrease Key, even more efficiently than regular Heaps.
  3. Leftist Heaps: Leftist Heaps are a type of Heap that are optimized for the Extract Min operation, making them useful for certain applications.
  4. Skew Heaps: Skew Heaps are a self-adjusting version of Leftist Heaps that can be implemented more efficiently.

These advanced topics and variations can be useful in specific scenarios and can provide even more efficient implementations of Heap-based algorithms and data structures.

Conclusion

In this article, we have explored the concept of Heaps and the process of building a Heap from an array. We have covered the key properties of Heaps, the Heap Building algorithm, the array representation of Heaps, and the various operations that can be performed on Heaps. We have also discussed the practical applications of Heaps, as well as the comparison of Heaps with other data structures, such as Binary Search Trees.

Heaps are a fundamental data structure in computer science and are widely used in a variety of algorithms and applications, from priority queues to sorting and optimization problems. Understanding the principles of Heap construction and the associated time complexities is crucial for designing efficient and scalable solutions to many real-world problems.

By mastering the concepts presented in this article, you will be well-equipped to tackle a wide range of problems that involve Heaps and Heap-based algorithms. Happy coding!

Did you like this post?

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

No votes so far! Be the first to rate this post.