Shubham Gautam

Heap Data Structure

Heap Data Structure is a special case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly. Min-Heap − Where the value of the root node is less than or equal to either of its children. Max-Heap − Where the value of the root node is greater than or equal to either of its children.

What are Complete Binary Trees?

Complete binary trees are structured such that:

  1. Fully Filled Levels: Each level is completely filled, with the possible exception of the last level. This ensures a dense and balanced tree structure. Complete Binary Tree
  2. Left-Filled Last Level: The last level is filled from left to right, which might not be fully complete, maintaining the tree’s integrity.
  3. Sequential Arrangement: Elements are arranged sequentially without gaps, adhering to the parent-child index relationship, crucial for representing the tree as an array.
  4. No Empty Spaces: True complete binary trees don’t have empty spaces in their array representation, making each position meaningful.

Incorrect Array Representation: Incomplete binary tree

Correct Array Representation: Binary Tree Array

  1. Foundation for Heaps: This well-ordered structure is essential for forming heaps, ensuring they meet the necessary criteria for max-heap or min-heap in data structure, based on the heap property.

Types of Heap Data Structure

1. Min-heap:

  • In a min-heap, each node is smaller than its child nodes.
  • The root of a min-heap is the smallest element in the heap.

The provided image shows a min-heap example: the root 5 is smaller than its children 8 and 6, and node 8 is smaller than its children 10 and 15, confirming the min-heap structure.

Min heap in data structure

2. Max-heap

  • In a max-heap, each node is greater than its child nodes.
  • The root of a max-heap is the largest element in the heap.

The provided image illustrates a max-heap example: the root 15 is greater than its children 10 and 8, and node 10 is greater than its children 6 and 5, confirming the max-heap structure.

Max heap in data structure

Heap Data Structure Operations

Every data structure has some operations like insertion, deletion associated with them. Heaps are no different, and there are many operations that can be performed on heap data structures. We will be discussing these operations over a max-heap since the same operations can be applied to a min-heap also.

Heapify

Heapify process for a binary tree involves transforming an array into a max-heap in data structure by ensuring every parent node is larger than its children. Consider the steps using the array 10, 8, 5, 15, 6:

  1. Visualize the Array as a Complete Binary Tree: Convert the array elements into tree nodes, maintaining the structure of a complete binary tree.Visualizing a complete Binary TreeThis tree isn’t a max-heap yet since node 8 is smaller than its child 15.
  2. Heapify the Tree: Compare parent nodes with their children, swapping the parent with the larger child if the parent is smaller. Repeat this until every node follows the max-heap property.Start with node 8, comparing it with children 15 and 6. Swap 8 with the larger child, 15.Swapping in max heapContinue heapifying up the tree. Since 15 (now a parent) is larger than 10, swap them to maintain the max-heap property.Max heap swapping elements

Heapification works bottom-up, ensuring all children are heapified before their parents. This recursive approach, starting from the lowest sub-trees, optimizes comparisons and adheres to a time complexity of O(logn) per node, due to the tree’s height determining the maximum swap operations.

Insertion in Heap

To insert elements into a heap and build a max-heap from the array 10, 8, 5, 15, 6, follow these optimized steps:

  1. Start with the First Element: Insert 10 as the root. This forms the beginning of your heap. Insertion in heap - first element
  2. Insert the Second Element: Add 8. Since 10 > 8, no swap is needed. The heap property is maintained. Insertion in heap - second element
  3. Continue Adding Elements: Insert 5 next, keeping the tree structure. Insertion in heap - third element
  4. Insert 15 and Adjust: Adding 15 requires adjustments. Swap 15 with 8, then 15 with 10 to maintain the max-heap property, demonstrating the “bubbling up” process where elements find their correct position.
    • After first swap: Insertion in heap - swapping element
    • After second swap: Insertion in heap - swapping element 1
  5. Add the Final Element: Place 6 in the heap, comparing it with its parent to ensure the heap’s integrity. Insertion in heap - Adding last element

This insertion process involves comparing each new element with its parent and swapping if necessary, ensuring the max-heap condition is always met. The “bubbling up” ensures elements are positioned correctly, maintaining the heap structure. While comparisons depend on the tree’s height, leading to a potential O(nlogn) complexity, optimizing with heapify can reduce this by reordering the heap in a bottom-up manner after all elements are added, improving efficiency.

Deletion from Heap

Let us consider the following max-heap that we created in the last step-

Insertion and Deletion in Heap

To delete the elements from a heap, we follow the under-given steps –

  1. Search for the element to be deleted and swap it with the last element in the heap, let’s say we want to delete 10-Swapping element in max heapHere, we have swapped the position of 10 with the last element that is 6
  2. Remove the element from the tree –Deletion in max heapBut now, the remaining heap is not a max-heap anymore. So, as the next step, we should heapify it once again.
  3. Heapify the tree again-Heapify tree in data structureHere, we have once again heapified the given tree to form a max-heap.

Thus, we have successfully removed 10 from the heap.

Peek

The Peek operation in heap data structures retrieves the topmost value— the maximum in a Max Heap or the minimum in a Min Heap—without modifying the heap. This is done by accessing the root node’s value, typically stored at the beginning of the underlying array or the top of the tree structure representing the heap.

Implementation of Heap

1. C

int size = 0;
 
//function to swap the values
void swap(int *a, int *b)
{
 int temp = *b;
 *b = *a;
 *a = temp;
}
 
//function to heapify the tree
void heapify(int array[], int size, int i)
{
 if (size == 1){
   printf("Only one element in the heap");
 }
 else{
   int largest = i;
  
   // Finding the left and the right child
   int l = 2 * i + 1;
   int r = 2 * i + 2;
 
   //Setting the largest out of root, left child & right child
   if (l < size && array[l] > array[largest])
     largest = l;
   if (r < size && array[r] > array[largest])
     largest = r;
  
   // If index is not equal to largest, perform swap
   if (largest != i){
     swap(&array[i], &array[largest]);
     heapify(array, size, largest);
   }
 }
}
 
//function to insert elements in the heap
void insert(int array[], int newNum){
 //checking if it is the first element
 if (size == 0){
   array[0] = newNum;
   size += 1;
 }
 else{
   array[size] = newNum;
   size += 1;
   for (int i = size / 2 - 1; i >= 0; i--)
     //heapifying the tree
     heapify(array, size, i);
 }
}
 
//function to delete from heap
void deleteRoot(int array[], int num)
{
 int i;
 for (i = 0; i < size; i++)
   //search if element is present in the heap
   if (num == array[i])
     break;
  //swapping the last element with the root element
 swap(&array[i], &array[size - 1]);
 size -= 1;
 
 for (int i = size / 2 - 1; i >= 0; i--)
   //heapifying the tree once again
   heapify(array, size, i);
}

2. C++

#include <bits/stdc++.h>
#include <vector>
using namespace std;
 
//function to heapify the tree
void heapify(vector<int> &heap, int i){
 int size = heap.size();
 int largest = i;
 
 // Finding the left and the right child
 int l = 2 * i + 1;
 int r = 2 * i + 2;
 
 //Setting the largest out of root, left child & right child
 if (l < size && heap[l] > heap[largest])
   largest = l;
 if (r < size && heap[r] > heap[largest])
   largest = r;
 
 // If index is not equal to largest, perform swap
 if (largest != i){
   swap(heap[i], heap[largest]);
   heapify(heap, largest);
 }
}
 
//function to insert elements in the heap
void insert(vector<int> &heap, int newNum){
 int size = heap.size();
 
 //checking if it is the first element
 if (size == 0)
   heap.push_back(newNum);
 else
   heap.push_back(newNum);
   for (int i = size / 2 - 1; i >= 0; i--)
     //heapifying the tree
     heapify(heap, i);
}
 
//function to delete from heap
void deleteNode(vector<int> &heap, int num){
 int size = heap.size();
 int i;
 
 //search if element is present in the heap
 for (i = 0; i < size; i++)
   if (num == heap[i])
     break;
  //swapping the last element with the root element
 swap(heap[i], heap[size - 1]);
 //removing the element
 heap.pop_back();
 for (int i = size / 2 - 1; i >= 0; i--)
   //heapifying the tree once again
   heapify(heap, i);
}

3. Python

# Max-Heap data structure in Python
 
def heapify(arr, n, i):
   largest = i
 
   #finding left and right child
   l = 2 * i + 1
   r = 2 * i + 2
  
   #finding largest out of root, left child and right child
   if l < n and arr[i] < arr[l]:
       largest = l
  
   if r < n and arr[largest] < arr[r]:
       largest = r
  
   # If index is not equal to largest, perform swap
   if largest != i:
       arr[i],arr[largest] = arr[largest],arr[i]
       heapify(arr, n, largest)
 
#function to insert a new number
def insert(array, newNum):
   size = len(array)
   if size == 0:
       array.append(newNum)
   else:
       array.append(newNum);
       #heapifying the tree once again
       for i in range((size//2)-1, -1, -1):
           heapify(array, size, i)
 
def deleteNode(array, num):
   size = len(array)
   i = 0
 
   #searching for the number to be deleted
   for i in range(0, size):
       if num == array[i]:
           break
 
   # swapping the last element with the root element 
   array[i], array[size-1] = array[size-1], array[i]
 
   # removing the element
   array.remove(num)
  
   #heapifying the tree once again
   for i in range((len(array)//2)-1, -1, -1):
       heapify(array, len(array), i)

Unlock the Power of Efficient Coding! Join Scaler Academy’s DSA Course Today and Transform Your Problem-Solving Abilities.

Conclusion

  • Heap in data structure efficiently organize data in Min-Heaps and Max-Heaps, optimizing access to the highest or lowest elements.
  • Inserting elements into a heap involves comparisons and potential swaps to keep the structure intact, following a “bubbling up” method.
  • Deletion involves swapping the targeted element with the last, removing it, and then re-heapifying to maintain order.
  • The Peek operation grants immediate access to the heap’s top element without disturbing the overall structure, crucial for quick data retrieval.

Author