Scribd
Upload
7 views33 pages

Lecture - Heap ADT and Algorithms

Chapter 9 discusses heap data structures, which are binary trees where each parent node has a value greater than its children, forming a max-heap. It covers the implementation of heaps using arrays, maintenance operations like insertion and deletion, and algorithms such as Reheap Up and Reheap Down. The chapter also introduces the heap Abstract Data Type (ADT) and provides C code for key heap functions.

Uploaded by

ashrafrajpoot3260
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
7 views33 pages

Lecture - Heap ADT and Algorithms

Chapter 9 discusses heap data structures, which are binary trees where each parent node has a value greater than its children, forming a max-heap. It covers the implementation of heaps using arrays, maintenance operations like insertion and deletion, and algorithms such as Reheap Up and Reheap Down. The chapter also introduces the heap Abstract Data Type (ADT) and provides C code for key heap functions.

Uploaded by

ashrafrajpoot3260
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
You are on page 1/ 33

Chapter 9

Heap

Objectives

• Define and implement heap structures


• Understand the operation and use of the heap ADT

Data Structures: A Pseudocode Approach with C, Second Edition 1


9-1 Basic Concepts

•A heap is a binary tree whose left and right subtrees have values less than
their parents. The root of a heap is guaranteed to hold the largest node in
the tree.

•Both the left and the right branches of the tree have the same properties.

•Heaps are often implemented in an array rather than a linked list. When
arrays are used, we are able to calculate the location of the left and the
right subtrees. Conversely, we can calculate the address of it’s parent.

•The tree is complete or nearly complete. The key value of each node is
greater than or equal to the key value in each of its descendents. This
structure is also called max- heap.

Data Structures: A Pseudocode Approach with C, Second Edition 2


Data Structures: A Pseudocode Approach with C, Second Edition 3
Data Structures: A Pseudocode Approach with C, Second Edition 4
Maintenance Operations
Two basic maintenance operations are performed on
a heap.
• Insert a heap
• Delete a heap
•Two basic algorithms are – Reheap Up and Reheap
Down

Data Structures: A Pseudocode Approach with C, Second Edition 5


•The reheap up operation repairs the structure so that it is
a heap by floating the last element up the tree until that
element is in its correct location.
•Insertion takes place at a leaf at the first empty position.
This may create a situation where the new node’s key is
larger than that of its parent. If it is, the node is floated up
the tree by exchanging the child and parent keys and data.

Data Structures: A Pseudocode Approach with C, Second Edition 6


Data Structures: A Pseudocode Approach with C, Second Edition 7
When we have a nearly complete binary tree that
satisfies heap order property except in the root
position. Reheap down operation reorders a
broken heap by pushing the root down the tree
until it is in correct position at the heap.
Data Structures: A Pseudocode Approach with C, Second Edition 8
Data Structures: A Pseudocode Approach with C, Second Edition 9
9-2 Heap Implementation

Heaps are usually implemented in an array structure. In this


section we discuss and develop five heap algorithms.

• Reheap Up
• Reheap Down
• Build a Heap
• Insert a Node into a Heap
• Delete a Node from a Heap

Data Structures: A Pseudocode Approach with C, Second Edition 10


Data Structures: A Pseudocode Approach with C, Second Edition 11
Data Structures: A Pseudocode Approach with C, Second Edition 12
Data Structures: A Pseudocode Approach with C, Second Edition 13
(continued)

Data Structures: A Pseudocode Approach with C, Second Edition 14


Data Structures: A Pseudocode Approach with C, Second Edition 15
Data Structures: A Pseudocode Approach with C, Second Edition 16
Data Structures: A Pseudocode Approach with C, Second Edition 17
Data Structures: A Pseudocode Approach with C, Second Edition 18
Data Structures: A Pseudocode Approach with C, Second Edition 19
Data Structures: A Pseudocode Approach with C, Second Edition 20
9-3 Heap ADT

We begin with a discussion of the heap ADT design and then


develop the C code for the five major functions developed in
Section 9.2.

• Heap Structure
• Heap Algorithms

Data Structures: A Pseudocode Approach with C, Second Edition 21


Data Structures: A Pseudocode Approach with C, Second Edition 22
Data Structures: A Pseudocode Approach with C, Second Edition 23
Data Structures: A Pseudocode Approach with C, Second Edition 24
Data Structures: A Pseudocode Approach with C, Second Edition 25
Data Structures: A Pseudocode Approach with C, Second Edition 26
Data Structures: A Pseudocode Approach with C, Second Edition 27
Data Structures: A Pseudocode Approach with C, Second Edition 28
(continued)

Data Structures: A Pseudocode Approach with C, Second Edition 29


Data Structures: A Pseudocode Approach with C, Second Edition 30
Data Structures: A Pseudocode Approach with C, Second Edition 31
Data Structures: A Pseudocode Approach with C, Second Edition 32
Data Structures: A Pseudocode Approach with C, Second Edition 33

You might also like