Heap Data Structures
Data Structure Data Structure Notes

Heap Data Structures

What is Heap Data Structures ?

  • Heap Data Structures is a Tree Data Structure in which tree is a Complete Binary Tree.
  • Explanation of Complete Binary Tree with example is explained in next section of this tutorial.
  • Questions based on Heap are generally asked in GATE(CS/IT) and UGC NET exam. Students are also suggested to prepare the the questions based on Heap Tree.
  • In this Heap Data Structures tutorial we will discuss various properties of Heap and explained various operations performed on Heap Data Structures.

Properties of Heap Data Structures

A Binary Tree is said to be a Heap if that Binary Tree must follow two properties.

These two Heap Properties are explained here in this section.

1. Structural Property

  • A Heap data structure tree is a Complete Binary Tree.
  • In a complete binary tree, all the levels except possibly the last are completely filled and all nodes are as left as possible it means tree build from left to right.
  • A complete binary tree is shown below-

2.Ordering Property

  • A Heap Tree must follow either max heap properties or min heap properties.
  • These are order properties of heap.
  • These are explained as types of heap in this tutorial in next section.

Types of Heap Data Structures

Heap Data Structure is of two types. These types are as follow –

1. Max Heap ( Root Maximum)

  • A max heap is a tree where if we consider any node, all the successors of the node is either lesser than or equal to the node.
  • An example of Max Heap is shown below-

  • In the above tree, if we take any node say 78, all the successors of the node are lesser than or equal to the node 78.
  • Here at each node, parent must be greater than its children.

2. Min Heap (Root is Minimum)

  • A min heap is a tree where if we consider any node, all the successors of the node is either greater than or equal to that node. i.e. the root of the tree is lesser than any other node of the tree.
  • An example Of Min Heap is shown below-

  • If we consider a node, say the root node 8, is lesser than any other node of the tree.
  • Here at each node parent must be smaller than the child.

Heap Tree Formation

Let’s use Heapify method for constructing a heap from a given array.

Heapify Method of Heap Formation

Note – The process of rearranging the heap by comparing each parent with its children recursively is known as heapify method.

If the heap size=N, then the range of leaves=[N/2] to (N-1). Hence, range of internal nodes= 0 to [N/2]-1

  • If parent node is at index j, both left and right child will be at 2j+1 index.
  • If left or right child is at index j, then parent will be at [j/2]-1.

Let’s construct a max heap using the given array indexed from 0 to 6. Now according to the formula, the leaf nodes will be [7/2]=4 to (7-1)=6th node.

  1. The constructed tree must be a complete binary tree.
  2. The value of parent must be greater than the child.
  • The insertion will take place at the leaf node.

After constructing the complete binary tree, we’ll then take a look whether the parents are greater than the child or not. If not, then we’ll swap the keys to its correct position.

The left sub tree is already a max heap.

Let’s focus on the right sub tree.

Deletion from a Heap Tree

Let’s discuss deletion operation on a heap tree using an example. heap data structure

  1. The node to be deleted will be deleted permanently.
  2. The last node will be deleted temporarily and the node that is permanently deleted will be replaced by the last node.
  3. Finally reheaping will be done to obtain a complete binary tree.

Let’s consider in the above heap we are going to delete the root node (95). The root node will get deleted permanently. The last node (55) will get deleted temporarily. The tree will look like- heap data structure The root node will be replaced by the last node. heap data structure Now, let’s heapify it to obtain a max heap. The resultant max heap will be- heap data structure

Conclusion and Summary

In this Heap Data Structures Tutorial we have discussed some important aspects of Heap Data Structure including it’s properties and various operations to be performed on Heap with suitable examples.

I hope this tutorial will be beneficial for computer science students and for GATE exam aspirants.

Previous Tutorial – AVL Tree in Data Structure

Next Tutorial – Minimum Spanning Tree

Leave a Reply

Your email address will not be published. Required fields are marked *