Page 256 - DCAP407_DATA_STRUCTURE

Pooja Gupta, Lovely Professional University Unit 14: Heaps

Unit 14: Heaps

CONTENTS
Objectives
Introduction
14.1 Fundamentals of Heaps
14.2 Inserting into Heaps

14.3 Deleting the Root of a Heap
14.4 Heap Sort
14.5 Priority Queue Using Heaps
14.6 Summary
14.7 Keywords
14.8 Self Assessment
14.9 Review Questions

14.10 Further Readings
Objectives

After studying this unit, you will be able to:
• Provide an introduction to heaps
• Explain insertion operation on heap
• Explain deletion of root of a heap
• Discuss heap sort

• Understand priority queue using heaps
Introduction
The heap data structure is a complete binary tree where each node of the tree has an orderly
relationship with its successors. Binary search trees are totally ordered, but the heap data structure is
only partially ordered. It is suitable for inserting and deleting minimum value operations.
Heap is an array object that is considered as a complete binary tree. Each node of the tree corresponds
to an element of the array that stores the value in the node. The tree is completely filled at all levels
except possibly the lowest, which is filled from the left upwards to a point. Heap data structures are
suitable for implementing priority queues.

The heap serves as a foundation of a theoretically important sorting algorithm called heapsort, which
we will discuss after defining the heap.
14.1 Fundamentals of Heaps

A heap can be defined as binary trees with keys assigned to its nodes (one key per node). The two types
of heaps are:
1. Max heaps
2. Min heaps

LOVELY PROFESSIONAL UNIVERSITY 249