Operations on Heaps

Heap is a very useful data structure that every programmer should know well. The heap data structure is used in Heap Sort, Priority Queues. The understanding of heaps helps us to know about memory management. In this blog, we will discuss the various operations of the heap data structure. We have already discussed what are heaps, its structure, types, and its representation in the array in the last blog. So let’s get started with the operations on a heap.

Operations on Heaps

The common operation involved using heaps are:

• Heapify → Process to rearrange the heap in order to maintain heap-property.
• Find-max (or Find-min) → find a maximum item of a max-heap, or a minimum item of a min-heap, respectively.
• Insertion → Add a new item in the heap.
• Deletion → Delete an item from the heap.
• Extract Min-Max → Returning and deleting the maximum or minimum element in max-heap and min-heap respectively.

Heapify

It is a process to rearrange the elements of the heap in order to maintain the heap property. It is done when a certain node causes an imbalance in the heap due to some operation on that node.

The heapify can be done in two methodologies:

• up_heapify() → It follows the bottom-up approach. In this, we check if the nodes are following heap property by going in the direction of rootNode and if nodes are not following the heap property we do certain operations to let the tree follows the heap property.
• down_heapify() → It follows the top-down approach. In this, we check if the nodes are following heap property by going in the direction of the leaf nodes and if nodes are not following the heap property we do certain operations to let the tree follows the heap property.

Pseudo Code

void down_heapify(int heap[], int parent, int size)
{
    largest = parent
    leftChild = 2*parent + 1
    rightChild = 2*parent + 2
    
    if(leftChild < size && heap[leftChild] > heap[largest])
        largest = leftChild
    if(rightChild < size && heap[rightChild] > heap[largest])
        largest = rightChild
    if(parent != largest)
    {
        swap(heap[parent], heap[largest])
        down_heapify(heap,largest,size)
    }
}
void up_heapify(int heap[], int child)
{
    parent = (child-1)/2;
    if(heap[parent] < heap[child]) {
        swap(heap[parent], heap[child])
        up_heapify(heap,parent)
    }  
}

Insertion

The insertion in the heap follows the following steps

• Insert the new element at the end of the heap.
• Since the newly inserted element can distort the properties of the Heap. So, we need to perform up_heapify() operation, in order to keep the properties of the heap in a bottom-up approach.

Initially the heap is as (It follows max-heap property)
    
      9
    /   \
   5     3
  / \
 1   4

New element to be inserted is 12
Step 1: Insert the new element at the end.
      9
    /    \
   5      3
  / \    /
 1   4  12

Step 2: Heapify the new element following bottom-up approach.

Final heap
      12
    /    \
   5      9
  / \    /
 1   4  3

Pseudo Code

void up_heapify(int heap[], int child)
{
    parent = (child-1)/2;
    
    if(heap[parent] < heap[child]) {
        swap(heap[parent], heap[child])
        up_heapify(heap,parent)
    }
    
}
void insert(int heap[],int size,int key)
{
    heap.append(key)
    up_heapify(heap,size+1,size)
}

Deletion

The deletion operations follow the following step:

• Replace the element to be deleted by the last element in the heap.
• Delete the last item from the heap.
• Now, the last element is placed at some position in heap, it may not follow the property of the heap, so we need to perform down_heapify() operation in order to maintain heap structure. The down_heapify() operation does the heapify in the top-bottom approach.

The standard deletion on Heap is to delete the element present at the root node of the heap.

Initially the heap is(It follows max-heap property)
      12
    /    \
   6      3
  / \
 1   4
Element to be deleted is 12

Step 1: Replace the last element with root, and delete it.
      4
    /   \
   6     3
  / 
 1 

Step 2: Heapify root.
Final Heap:
      6
    /   \
   4     3
  / 
 1

Pseudo-Code

void down_heapify(int heap[], int parent, int size)
{
    largest = parent
    leftChild = 2*parent + 1
    rightChild = 2*parent + 2
    
    if(leftChild < size && heap[leftChild] > heap[largest])
        largest = leftChild
    if(rightChild < size && heap[rightChild] > heap[largest])
        largest = rightChild
    if(parent != largest)
    {
        swap(heap[parent], heap[largest])
        down_heapify(heap,largest,size)
    }
}
void deleteRoot(int heap[], int size)
{
    swap(heap[0], heap[size-1]) // swap first and last element
    heap.pop_back(); // delete the last element
    down_heapify(heap,0,size-1)
}

Find-max (or Find-min)

The maximum element and the minimum element in the max-heap and min-heap is found at the root node of the heap.

int findMax(int heap[])
{
    return heap[0]
}

Extract Min-Max

This operation returns and deletes the maximum or minimum element in max-heap and min-heap respectively. The maximum element is found at the root node.

int extractMax(int heap[], int size)
{
    ans = heap[0]
    deleteRoot(heap, size)
    return ans
}

Suggested Problems to solve

• Find kth largest element in an array
• Top k Frequent Elements
• K Pairs with Smallest Sums
• Sliding window maximum
• Merge K sorted list
• Convert a min-heap to max heap

Happy coding! Enjoy Algorithms.