Page 204 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Anil Sharma, Lovely Professional University
Unit 10: Heaps

Unit 10: Heaps Notes

CONTENTS

Objectives
Introduction
10.1 Heaps
10.2 Binary Heaps
10.2.1 Complete Trees
10.2.2 Implementation
10.2.3 Putting items into a Binary Heap
10.2.4 Removing items from a Binary Heap
10.3 Applications of Heaps
10.3.1 Discrete Event Simulation
10.3.2 Implementation

10.4 d-Heaps
10.5 Summary
10.6 Keywords
10.7 Self Assessment
10.8 Review Questions
10.9 Further Readings

Objectives

After studying this unit, you will be able to:

Describe heaps
State the concept of binary heaps
Discuss applications of heaps
Defi ne d-heaps

Introduction

A heap is a specialized tree-based data structure that satisfies the heap property: if B is a child

node of A, then key(A) ≥ key(B). This implies that an element with the greatest key is always in the
root node, and so such a heap is sometimes called a max-heap. (Alternatively, if the comparison
is reversed, the smallest element is always in the root node, which results in a min-heap.) The

heap is one maximally-efficient implementation of an abstract data type called a priority queue.

Heaps are crucial in several efficient graph algorithms.
10.1 Heaps

A heap is a storage pool in which regions of memory are dynamically allocated. For example,
in C++ the space for a variable is allocated essentially in one of three possible places: Global

LOVELY PROFESSIONAL UNIVERSITY 199