Scribd
Upload
5 views27 pages

Understanding Heaps in Data Structures

The document provides an overview of heaps in data structures, detailing their properties as complete binary trees and their memory representation using arrays. It discusses the two main types of heaps, min heaps and max heaps, along with their construction, insertion, and deletion operations. Additionally, it highlights the applications of heaps, such as sorting and implementing priority queues.

Uploaded by

razakidwai90
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views27 pages

Understanding Heaps in Data Structures

The document provides an overview of heaps in data structures, detailing their properties as complete binary trees and their memory representation using arrays. It discusses the two main types of heaps, min heaps and max heaps, along with their construction, insertion, and deletion operations. Additionally, it highlights the applications of heaps, such as sorting and implementing priority queues.

Uploaded by

razakidwai90
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

HEAP In DATA

STRUCTURES

Instructor:
[Link]-e-Shawar Agha
ROAD MAP
 Introduction to Heap

 Types of Heap

 Operations in Heap
Heap
It is a binary tree with the following properties:

Property 1: It is a complete binary tree

Property 2: The value stored at a node is greater or equal to the


values stored at the children
Memory Representation of Heap using
Array
A heap is a complete binary tree, so it is easy to be
implemented using an array representation.
Applications of Heap
• Used for sorting purpose

• Used to implement a priority queue.


Types / Ordering of Heap
• There are two types of Heap

1. Min Heap
The value of each node is greater than or equal to the value of
its parent with the minimum value element at the root.

1. Max Heap

The value of each node is less than or equal to the value of its
parent with the maximum value element at the root.
Construction of Max Heap
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
Construction of Max Heap
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.
Construction of Max Heap

Step-03:

• Node 5 contains greater element in its right child node.


• So, we swap node 5 and node 12.
• The resulting tree is
Construction of Max Heap

Step-04:

•Node 1 contains greater element in its right child node.


•So, we swap node 1 and node 16.
Construction of Max Heap
Step-05:

Node 1 contains greater element in its left child node.


So, we swap node 1 and node 14.

The resulting tree is


Insertion in Max Heap

Insert element 60 in the following Heap


• We insert the new element 60 as a next leaf node from left to right.
• The resulting tree is
• 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.
• Node 30 contains greater element in its left child node.
• So, we swap node 30 and node 60.
• Node 50 contains greater element in its left child node.
• So, we swap node 50 and node 60
Deletion in Max Heap

• In heap deletion of node always occurs from root.


• Move last element of last level to root
• Maintain the ordering of heap
Construction of Min Heap

Construct the Min heap for the following


3, 1 , 6, 5, 2 and 4
Insertion in Min Heap
SUMMARY
 Introduction to Heap

 Types of Heap

 Operations on Heap

You might also like