Data structures trees and graphs - Heap Tree.pptx

Data Structures
(Heap Tree )
Dr.N.S.Nithya
ASP/CSE

12/17/2023 2
Introduction
 Heaps are largely about priority
queues.
 They are an alternative data structure
to implementing priority queues (we
had arrays, linked lists…)
 Recall the advantages and
disadvantages of queues implemented
as arrays
◦ Insertions / deletions? O(n) … O(1)!
 Priority queues are critical to many
real-world applications.

12/17/2023 3
Uses of Heaps
 Use of heap trees can be used to obtain improved
running times for several network optimization
algorithms.
 Can be used to assist in dynamically-allocating
memory partitions.
 Lots of variants of heaps (see Google)
 A heapsort is considered to be one of the best
sorting methods being in-place with no quadratic
worst-case scenarios.
 Finding the min, max, both the min and max,
median, or even the k-th largest element can be
done in linear time using heaps.
 And more….

Heap Data Structures
 Heap data structure is a specialized
binary tree-based data structure. Heap
is a binary tree with special
characteristics. In a heap data
structure, nodes are arranged based
on their values. A heap data structure
some times also called as Binary
Heap.

Properties of Heap data
Structure
 Every heap data structure has the
following properties...
 Property #1 (Structural): All levels in
a heap must be full except the last
level and all nodes must be filled from
left to right strictly.
 Property #2 (Ordering): Nodes must
be arranged in an order according to
their values based on Max heap or
Min heap.

Heaps
A heap is a certain kind
of complete binary tree.

Heaps
A heap is a
certain kind
of complete
binary tree.
When a complete
binary tree is built,
its first node must be
the root.
Root

Heaps
Complete
binary tree.
Left child
of the
root
The second node is
always the left child
of the root.

Heaps
Complete
binary tree.
Right child
of the
root
The third node is
always the right child
of the root.

Heaps
Complete
binary tree.
The next nodes
always fill the next
level from left-to-
right.

Heaps
A heap is a
certain kind
of complete
binary tree.
Each node in a heap
contains a key that
can be compared to
other nodes' keys.
19
4
22
21
27
23
45
35

Heaps
A heap is a
certain kind
of complete
binary tree.
The "heap property"
requires that each
node's key is >= the
keys of its children
19
4
22
21
27
23
45
35

Max Heap
 Max-Heap: In this type of heap, the
value of parent node will always be
greater than or equal to the value of child
node across the tree and the node with
highest value will be the root node of the
tree.

Min Heap
 Min-Heap: In this type of heap, the
value of parent node will always be less
than or equal to the value of child node
across the tree and the node with
lowest value will be the root node of
tree.

Heapify
 Heapify is the process of creating a heap
data structure from a binary tree. It is used
to create a Min-Heap or a Max-Heap.
 Let the input array be
Create a complete binary
tree from the array

Adding a Node to a Max-Heap
 Put the new node (42)
in the next available
spot.
 Push the new node
upward, swapping with
its parent until the new
node satisfy the heap
order property.
19
4
22
21
27
23
45
35
42

Adding a Node to a Max-Heap
 Put the new node in
the next available
spot.
node reaches an
acceptable location.
19
4
22
21
42
23
45
35
27

Adding a Node to a Heap
the next available
spot.
node reaches an
19
4
22
21
35
23
45
42
27

Adding a Node to a Max -Heap
 The node move
upwards until it satisfy
the condition
 The parent has a key
that is >= new node
 The process of
pushing the new node
upward is called
reheapification
upward.
19
4
22
21
35
23
45
42
27

Deleting a Max element from Max-
Heap
 To remove the
biggest entry,
move the last
node onto the root,
and perform a
reheapification
downward.
19
4
22
21
35
23
45
42
27

Heap
 Move the last node
onto the root.
19
4
22
21
35
23
27
42

Heap
onto the root.
 Push the out-of-place
node downward,
swapping with its
larger child until the
new node reaches an
19
4
22
21
35
23
27
42

Heap
onto the root.
node downward,
swapping with its
new node reaches an
19
4
22
21
35
23
42
27

Heap
onto the root.
node downward,
swapping with its
new node reaches an
19
4
22
21
27
23
42
35

Heap
 The children all have
keys <= the out-of-
place node, or
 The node reaches the
leaf.
 The process of
downward is called
reheapification
downward.
19
4
22
21
27
23
42
35

Adding a Node to a Min-Heap
 Put the new node (5)
in the next available
spot.
node satisfy the heap
order property.
19
24
20
10
14
18
10
12
5

the next available
spot.
node reaches an
19
24
20
15
5
18
10
12
14

the next available
spot.
node reaches an
19
24
20
15
12
18
10
5
14

the next available
spot.
node reaches an
19
24
20
15
12
18
10
14
5

Adding a Node to a Min -Heap
 The node move
upwards until it satisfy
the condition
 The parent has a key
that is <= new node
 The process of
upward is called
reheapification
upward.
19
24
20
15
12
18
5
10
14

Deleting a Min element from
Min- Heap
 To remove the
biggest entry,
move the last
node onto the root,
and perform a
reheapification
downward.
19
24
20
15
12
18
4
10
14

Min- Heap
onto the root.
19
24
20
15
12
18
14
10

Deleting a Min element from Min-
Heap
onto the root.
node downward,
swapping with its
new node reaches an
19
24
20
15
12
18
14
10

Min- Heap
onto the root.
node downward,
swapping with its
new node reaches an
19
24
20
15
12
18
10
14

Min- Heap
onto the root.
node downward,
swapping with its
new node reaches an
19
24
20
15
14
18
10
12

Min- Heap
 The children all have
keys <= the out-of-
place node, or
 The node reaches the
leaf.
 The process of
downward is called
reheapification
downward.
19
24
20
15
14
18
10
12

Decrease-Key
 To decrease the value of a certain
key, we’ll use the map to locate its
index. After we locate its index, we’ll
change its value, and start moving it
up the tree if needed. The reason we’re
moving the key up the tree is that its
value got reduced. Therefore, it’ll either
stay in its place or move up.

42
Heap-Priority Queues
 Supports the following operations.
◦ Insert element x.
◦ Return min element.
◦ Return and delete minimum element.
◦ Decrease key of element x to k.
 Applications.
◦ Dijkstra's shortest path algorithm.
◦ Prim's MST algorithm.
◦ Event-driven simulation.
◦ Huffman encoding.
◦ Heapsort.
◦ . . .

Data structures trees and graphs - Heap Tree.pptx

Recommended

More Related Content

Similar to Data structures trees and graphs - Heap Tree.pptx (20)

More from MalligaarjunanN (20)

Recently uploaded (20)

Data structures trees and graphs - Heap Tree.pptx