EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login
Home Data Science Data Science Tutorials Data Structures Tutorial Heap Data Structure
Secondary Sidebar
Data Structures Tutorial
  • Basics
    • Linked List Advantages
    • What is Data Structure
    • Heap Data Structure
    • Types of Trees in Data Structure
    • AVL Tree in Data Structure
    • B Tree in Data Structure
    • B+ Tree in Data Structure
    • DFS Algorithm
    • BFS Algorithm
    • Arrays in Data Structure
    • Graph in Data Structure
    • Graph Representation
    • Breadth First Search
    • Depth Limited Search
    • Hashing in Data Structure
    • Searching in Data Structure
    • Linear Search in Data Structure
    • Linked List in Data Structure
    • Doubly linked list in Data Structure
    • Circular Linked List in Data Structure
    • Pointers in Data Structure
    • Types of Graph in Data Structure
    • Bubble Sort in Data Structure
    • Quick Sort in Data Structure
    • Bitonic Sort
    • Merge Sort in Data Structure
    • Selection Sort in Data Structure
    • Insertion Sort in Data Structure
    • Radix Sort in Data Structure
    • Stack in Data Structure
    • Queue in Data Structure
    • Priority Queue in Data Structure
    • Asymptotic Analysis
    • Tree Traversal in Data Structure
    • Tree Traversal Techniques
    • Trie Data Structure
    • Splay Tree in Data Structure
    • Spanning Tree Algorithm
    • Sparse Matrix in Data Structure
    • Radix Sort Algorithm
    • Counting Sort Algorithm
    • Skip List Data Structure
    • Linked List Algorithm
    • Linked List Types
    • Inorder Traversal of Binary Tree
    • Kruskals Algorithm
    • Prims Algorithm
    • BFS VS DFS
    • BCNF
    • Skip List
    • Hash Table?in Data Structure
    • Data Structure Interview Questions
    • Data Structures & Algorithms Interview
    • AVL Tree Deletion
    • B+ Tree Deletion
    • Decision Tree Advantages and Disadvantages
    • Data Architect Skills
    • Data Architecture Principles
    • Data Engineer Jobs
    • Data Engineer Roadmap
    • Fundamentals of Data Structure
    • Circular queue in Data Structure
    • Spanning Tree in Data Structure
    • Tree traversal types
    • Deque in Data structure
    • Shell Sort in Data Structure
    • Heap sort in data structure
    • Heap data structure C++
    • Heap data structure in Java
    • Binary Search Tree Types
    • Binary Tree in Data Structure
    • Binary Tree Types
    • Binary search tree in data structure
    • Binary Search Tree Advantages
    • Binary Search Tree Properties
    • Binary Search in Data Structure
    • Binary Tree Deletion
    • Sparse Matrix Multiplication
    • Preorder Traversal of Binary Tree
    • Postorder traversal
    • Decision Tree Hyperparameters
    • PostOrder Traversal without Recursion
    • AVL Tree Rotation
    • Avro File Format
    • Decision Tree Types
    • Binomial heap
    • Confluence Jira Integration
    • Timm Sort
    • Depth First Search
    • Stock Span Problem

Heap Data Structure

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.

Heap Data Structure Types

Types of Heap Data Structure are:

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

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
Popular Course in this category
Data Scientist Training (85 Courses, 67+ Projects)
  85 Online Courses |  67 Hands-on Projects |  660+ Hours |  Verifiable Certificate of Completion
4.8
Price

View Course

Related Courses

All in One Data Science Bundle (360+ Courses, 50+ projects)4.9
Oracle DBA Database Management System Training (2 Courses)4.8
SQL Training Program (10 Courses, 8+ Projects)4.7
Primary Sidebar
Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

ISO 10004:2018 & ISO 9001:2015 Certified

© 2023 - 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

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA

*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?

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more