# 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.

## 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).

## 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
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