Heap Tree

Here is the detailed explanation of Heap Tree:

• A heap tree is a specialized type of binary tree that satisfies the heap property: for every node, the value of its children is less than or equal to its own value.
• The heap property defines the relationship between parent and child nodes in the tree.

Types of heap trees:

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 at the root.

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 at the root.

Difference between Max and Min Heap Tree:

Here is the difference between Max and Min Heap Tree:

Conversion of Min Heap to Max Heap:

Given an array representation of min Heap, convert it to max Heap.

Examples: 

Input: arr[] = {3, 5, 9, 6, 8, 20, 10, 12, 18, 9}

               3
            /     \
          5       9
        /   \    /  \
      6     8  20   10
    /  \   /
12   18 9 

Output: arr[] = {20, 18, 10, 12, 9, 9, 3, 5, 6, 8}

           20
         /    \
      18      10
     /    \    /  \
  12     9  9    3
 /  \   /
5    6 8 

Input: arr[] = {3, 4, 8, 11, 13}
Output:  arr[] = {13, 11, 8, 4, 3}

Algorithm for converting a min heap to a max heap:

Start at the last non-leaf node of the heap (i.e., the parent of the last leaf node). For a binary heap, this node is located at the index floor((n – 1)/2), where n is the number of nodes in the heap.
For each non-leaf node, perform a “heapify” operation to fix the heap property. In a min heap, this operation involves checking whether the value of the node is greater than that of its children, and if so, swapping the node with the smaller of its children. In a max heap, the operation involves checking whether the value of the node is less than that of its children, and if so, swapping the node with the larger of its children.
Repeat step 2 for each of the non-leaf nodes, working your way up the heap. When you reach the root of the heap, the entire heap should now be a max heap.

Below is the implementation of the above approach in java:

// Java program to convert min Heap to max Heap
 
class GFG {
    // To heapify a subtree with root at given index
    static void MaxHeapify(int arr[], int i, int N)
    {
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int largest = i;
        if (l < N && arr[l] > arr[i])
            largest = l;
        if (r < N && arr[r] > arr[largest])
            largest = r;
        if (largest != i) {
            // swap arr[i] and arr[largest]
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            MaxHeapify(arr, largest, N);
        }
    }
 
    // This function basically builds max heap
    static void convertMaxHeap(int arr[], int N)
    {
        // Start from bottommost and rightmost
        // internal node and heapify all internal
        // nodes in bottom up way
        for (int i = (N - 2) / 2; i >= 0; --i)
            MaxHeapify(arr, i, N);
    }
 
    // A utility function to print a given array
    // of given size
    static void printArray(int arr[], int size)
    {
        for (int i = 0; i < size; ++i)
            System.out.print(arr[i] + " ");
    }
 
    // driver's code
    public static void main(String[] args)
    {
        // array representing Min Heap
        int arr[] = { 3, 5, 9, 6, 8, 20, 10, 12, 18, 9 };
        int N = arr.length;
 
        System.out.print("Min Heap array : ");
        printArray(arr, N);
 
        // Function call
        convertMaxHeap(arr, N);
 
        System.out.print("\nMax Heap array : ");
        printArray(arr, N);
    }
}

Output:

Min Heap array : 3 5 9 6 8 20 10 12 18 9 
Max Heap array : 20 18 10 12 9 9 3 5 6 8 

Check if a given Binary Tree is a Heap:

Given a binary tree, check if it has heap property or not, Binary tree needs to fulfill the following two conditions for being a heap – 

• It should be a complete tree (i.e. all levels except the last should be full).
• Every node’s value should be greater than or equal to its child node (considering max-heap).

Examples:

Input: 

Output: Given binary tree is a heap 

Input: 

Output: Given binary tree is not a heap

Applications of Heap Tree:

Priority Queues:

Heaps are often used to implement priority queues, where elements are stored with associated priorities. In a min-heap, the element with the smallest priority is at the root, while in a max-heap, the element with the highest priority is at the root. This allows for efficient insertion, deletion, and retrieval of elements with the highest or lowest priority.

Heap Sort:

Heap sort is a comparison-based sorting algorithm that builds a max-heap from the input array and repeatedly extracts the maximum element from the heap until the heap is empty. Heap sort has a time complexity of O(n log n), making it efficient for sorting large datasets.

Dijkstra’s Algorithm:

Dijkstra’s algorithm is a graph search algorithm used to find the shortest path between nodes in a graph with non-negative edge weights. It can be efficiently implemented using a priority queue based on a min-heap.

Advantages of heap tree:

Efficient Operations:

Heap trees support efficient insertion, deletion, and retrieval of the minimum or maximum element in O(log n) time complexity.

Space Efficiency:

Heap trees require less memory compared to other data structures like balanced binary search trees.

Ease of Implementation:

Implementing heap operations is relatively straightforward compared to other data structures.

Disadvantages of heap tree:

Lack of Flexibility:

Heap trees are limited to supporting only specific operations (e.g., insertion, deletion, retrieval of min/max element), making them less versatile than other data structures.

No Order Preservation:

Heap trees do not preserve the order of elements beyond satisfying the heap property, which may be a disadvantage in some applications.

Complexity:

While heap operations have efficient time complexity, implementing heap algorithms can sometimes be more complex compared to simpler data structures.