EDUCBA Logo

EDUCBA

MENUMENU
  • Explore
    • EDUCBA Pro
    • PRO Bundles
    • Featured Skills
    • New & Trending
    • Fresh Entries
    • Finance
    • Data Science
    • Programming and Dev
    • Excel
    • Marketing
    • HR
    • PDP
    • VFX and Design
    • Project Management
    • Exam Prep
    • All Courses
  • Blog
  • Enterprise
  • Free Courses
  • Log in
  • Sign Up
Home Data Science Data Science Tutorials Data Structures Tutorial Heap Data Structure
 

Heap Data Structure

Updated March 4, 2023

Heap Data Structure

 

 

Definition of Heap Data Structure

A heap is a special type of tree that satisfies certain conditions such as it is a complete binary tree and the value in the parent node in a heap is always either greater than or equal to the value in its child nodes in case of max heap or value in parent node is smaller than the value stored in its child node. This type of data structure has been constructed to implement scenarios such as priority queues where one needs to pick the element with least or highest priority. Also the tree in a heap is always balanced.

Watch our Demo Courses and Videos

Valuation, Hadoop, Excel, Mobile Apps, Web Development & many more.

Heap Data Structure Types

Types of Heap Data Structure are:

1. Max Heap

This is a type of heap where the value in the root element is greater or equal to the elements present in its child node.

Heap Data Structure-1.1

Algorithm
  • Step 1: First create a new node N at the end of the heap.
  • Step 2: The new element to be added will be assigned to this node N
  • Step 3: Repeat Step 3 and 4 until node reaches its correct position.
  • Step 3:Values of this node N is compared to parent of N.
  • Step 4:If value of parent[N] < any of its child then swap them
Working

Max heap is a complete binary tree that stores the elements in its node following one cireteriai.e Parent[N] is greater than or equal to its child node. The elements of max heap are mapped into an array my_arr following below criteria –

  1. Root of the heap is stored at first location of array my_arr.
  2. In case an element is stored at m location in the array then its left child is stored at 2*m+1 location.
  3. And right child of the node is stored at 2*m +2 location.
  4. Also root of the element is greater or equal to its child node.

This way a max- heap can be mapped to an array in the memory and can be retrieved easily using these guidelines. Various operations such as insertion, deletion, accessing can be performed on max heap .

It helps in the applications where one needs to sort the elements in decreasing order as the highest element in the heap is present at the root and can be removed one by one and build heap on remaining elements in the heap again. It is also efficient and enhances the performance of the program and memory.

Example

Lets explore one example for the above-given max- heap where we add a new element with value =80 to the heap.

Step 1: First we add a new node with value =80 to the last of the heap that is right child of the node 40. In case node 24 was not there we will insert node 80 as the left child of the heap.

Heap Data Structure-1.2

Step 2: Now we will compare new node 80 with its parent node i.e 40. Since 80> 40 then we will swap the nodes. Now 80 becomes parent of 40.

Heap Data Structure-1.3

Step 3: Now we will compare node 70 and 80 and Since 80 > 70 thus we will swap those nodes. And now we will see 80 is in its correct position thus max heap has been built successfully.

Output-1.4

2. Min Heap

This is a type of heap where the value of elements stored in the root node is lesser or equal to the value of elements stored in its child node.

Output-1.5

Algorithm
  • Step 1: First create a new node N at the end of the heap.
  • Step 2: The new element to be added will be assigned to this node N
  • Step 3: Repeat Step 3 and 4 until node reaches its correct position.
  • Step 3: Values of this node N is compared to parent of N.
  • Step 4: If value of parent[N] > any of its child then swap them.
Working

Min heap is a complete binary tree that stores the elements in its node following one cireteriai.e Parent[N] is lesser than or equal to its child node. The elements of max heap are mapped into an array my_arr following below criteria –

  1. Root of the heap is stored at first location of array my_arr.
  2. In case an element is stored at m location in the array then its left child is stored at 2*m+1 location.
  3. And right child of the node is stored at 2*m +2 location.
  4. Also root of the element is lesser than or equal to its child node.

This way a max- heap can be mapped to an array in the memory and can be retrieved easily using these guidelines. Various operations such as insertion ,deletion, accessing can be performed on min heap .

It helps in the applications where one needs to sort the elements in increasingorder such as priority queues as the smallest element in the heap is present at the root and can be removed one by one and build heap on remaining elements in the heap again. It is also efficient and enhances the performance of the program and memory.

Example

In this example we will build a min heap when a new node with value 5 is inserted in the above given heap.

Step 1: First we will insert the new node with value 4 at the end of the heap . And see if it is its correct position. As we can see parent of new node is 20 and 4> 20 thus we need to swap the two node acccoding to step 4 in the algorithm.

Output-1.6

Step 2: Now node 4 has been swapped to new position. Now we will compare node 4 and its parent node 5 and we see that 5 > 4 and thus needs to be swapped again.

Heap Data Structure-1.7

Step 3: Now new node 4 is at the root of the min heap . Now we observe node 4 is at its right position thus new node 4 has been inserted successfully and new min heap has been built.

 Heap Data Structure-1.8

3. Binary Heap

This is a type of binary heap is a binary tree that satisfies all the properties of complete binary tree. Further binary heap can be represented using above 2

Conclusion

Heap data structure is a special type of balanced complete binary tree that exist either as max –heap where value of the parent node is always greater than or equal to value in the child node or as min-heap where value of the parent node is smaller or equal to the values in its child node.

Recommended Articles

This is a guide to Heap Data Structure. Here we also discuss the definition and types of heap data structure along with an explanation. You may also have a look at the following articles to learn more –

  1. B+ Tree in Data Structure
  2. Merge Sort in Data Structure
  3. Searching in Data Structure
  4. Stack in Data Structure

Primary Sidebar

Footer

Follow us!
  • EDUCBA FacebookEDUCBA TwitterEDUCBA LinkedINEDUCBA Instagram
  • EDUCBA YoutubeEDUCBA CourseraEDUCBA Udemy
APPS
EDUCBA Android AppEDUCBA iOS App
Blog
  • Blog
  • Free Tutorials
  • About us
  • Contact us
  • Log in
Courses
  • Enterprise Solutions
  • Free Courses
  • Explore Programs
  • All Courses
  • All in One Bundles
  • Sign up
Email
  • [email protected]

ISO 10004:2018 & ISO 9001:2015 Certified

© 2025 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

By continuing above step, you agree to our Terms of Use and Privacy Policy.
*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

EDUCBA Login

Forgot Password?

🚀 Limited Time Offer! - 🎁 ENROLL NOW