Heap Operations | Max Heap Operations | Examples

Heap Data Structure-

 

Before you go through this article, make sure that you have gone through the previous article on Heap Data Structure.

 

We have discussed-

  • Heap is a specialized data structure with special properties.
  • A binary heap is a binary tree that has ordering and structural properties.
  • A heap may be a max heap or a min heap.

 

In this article, we will discuss about heap operations.

 

Heap Operations-

 

The most basic and commonly performed operations on a heap are-

 

 

  1. Search Operation
  2. Insertion Operation
  3. Deletion Operation

 

Here, we will discuss how these operations are performed on a max heap.

 

Max Heap-

 

  • In max heap, every node contains greater or equal value element than its child nodes.
  • Thus, root node contains the largest value element.

 

Example-

 

The following heap is an example of a max heap-

 

 

Max Heap Operations-

 

We will discuss the construction of a max heap and how following operations are performed on a max heap-

  • Finding Maximum Operation
  • Insertion Operation
  • Deletion Operation

 

Max Heap Construction-

 

Given an array of elements, the steps involved in constructing a max heap are-

 

Step-01:

 

Convert the given array of elements into an almost complete binary tree.

 

Step-02:

 

Ensure that the tree is a max heap.

  • Check that every non-leaf node contains a greater or equal value element than its child nodes.
  • If there exists any node that does not satisfies the ordering property of max heap, swap the elements.
  • Start checking from a non-leaf node with the highest index (bottom to top and right to left).

 

Finding Maximum Operation-

 

  • In max heap, the root node always contains the maximum value element.
  • So, we directly display the root node value as maximum value in max heap.

 

Insertion Operation-

 

Insertion Operation is performed to insert an element in the heap tree.

 

The steps involved in inserting an element are-

 

Step-01:

 

Insert the new element as a next leaf node from left to right.

 

Step-02:

 

Ensure that the tree remains a max heap.

  • Check that every non-leaf node contains a greater or equal value element than its child nodes.
  • If there exists any node that does not satisfies the ordering property of max heap, swap the elements.
  • Start checking from a non-leaf node with the highest index (bottom to top and right to left).

 

Deletion Operation-

 

Deletion Operation is performed to delete a particular element from the heap tree.

 

When it comes to deleting a node from the heap tree, following two cases are possible-

 

Case-01: Deletion Of Last Node-

 

  • This case is pretty simple.
  • Just remove / disconnect the last leaf node from the heap tree.

 

Case-02: Deletion Of Some Other Node-

 

  • This case is little bit difficult.
  • Deleting a node other than the last node disturbs the heap properties.

 

The steps involved in deleting such a node are-

 

Step-01:

 

  • Delete the desired element from the heap tree.
  • Pluck the last node and put in place of the deleted node.

 

Step-02:

 

Ensure that the tree remains a max heap.

  • Check that every non-leaf node contains a greater or equal value element than its child nodes.
  • If there exists any node that does not satisfies the ordering property of max heap, swap the elements.
  • Start checking from a non-leaf node with the highest index (bottom to top and right to left).

 

PRACTICE PROBLEMS BASED ON MAX HEAP OPERATIONS-

 

Problem-01:

 

Construct a max heap for the given array of elements-

1, 5, 6, 8, 12, 14, 16

 

Solution-

 

Step-01:

 

We convert the given array of elements into an almost complete binary tree-

 

 

Step-02:

 

  • We ensure that the tree is a max heap.
  • Node 6 contains greater element in its right child node.
  • So, we swap node 6 and node 16.

 

The resulting tree is-

 

 

Step-03:

 

  • Node 5 contains greater element in its right child node.
  • So, we swap node 5 and node 12.

 

The resulting tree is-

 

 

Step-04:

 

  • Node 1 contains greater element in its right child node.
  • So, we swap node 1 and node 16.

 

The resulting tree is-

 

 

Step-05:

 

  • Node 1 contains greater element in its left child node.
  • So, we swap node 1 and node 14.

 

The resulting tree is-

 

 

This is the required max heap for the given array of elements.

 

Problem-02:

 

Consider the following max heap-

50, 30, 20, 15, 10, 8, 16

Insert a new node with value 60.

 

Solution-

 

Step-01:

 

We convert the given array of elements into a heap tree-

 

 

Step-02:

 

We insert the new element 60 as a next leaf node from left to right.

The resulting tree is-

 

 

Step-03:

 

  • We ensure that the tree is a max heap.
  • Node 15 contains greater element in its left child node.
  • So, we swap node 15 and node 60.

 

The resulting tree is-

 

 

Step-04:

 

  • Node 30 contains greater element in its left child node.
  • So, we swap node 30 and node 60.

 

The resulting tree is-

 

 

Step-05:

 

  • Node 50 contains greater element in its left child node.
  • So, we swap node 50 and node 60.

 

The resulting tree is-

 

 

This is the required max heap after inserting the node with value 60.

 

Problem-03:

 

Consider the following max heap-

50, 30, 20, 15, 10, 8, 16

Delete a node with value 50.

 

Solution-

 

Step-01:

 

We convert the given array of elements into a heap tree-

 

 

Step-02:

 

  • We delete the element 50 which is present at root node.
  • We pluck the last node 16 and put in place of the deleted node.

 

The resulting tree is-

 

 

Step-03:

 

  • We ensure that the tree is a max heap.
  • Node 16 contains greater element in its left child node.
  • So, we swap node 16 and node 30.

 

The resulting tree is-

 

 

This is the required max heap after deleting the node with value 50.

 

To gain better understanding about Heap Data Structure,

Watch this Video Lecture

 

Next Article- Introduction to Hashing

 

Get more notes and other study material of Data Structures.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Heap Operations | Max Heap Operations | Examples
Article Name
Heap Operations | Max Heap Operations | Examples
Description
Heap Operations- The most commonly performed operations a heap data structure are- Search, Insert, Delete. Max Heap Operations with their Time Complexities are discussed.
Author
Publisher Name
Gate Vidyalay
Publisher Logo