Heaps Preparation

Overview

Another unique kind of tree, called a heap, can be used for implementing solutions to several different problems, including the priority queue ADT. Today we’ll focus on this data structure and some of what it is used for.

Basic Learning Objectives

Before class, you should be able to:

• Define what the priority queue ADT is
• Define what complete means for binary trees
• Explain how a heap maintains its nodes

Advanced Learning Objectives

After class, you should be able to:

• Implement a heap
• Analyze the time complexity of heap and priority queue operations

Reading

You should read the following:

• 9.2 Priority Queues with Binary Heaps
• 9.3 Priority Queue Operations and Usage
• 9.4 Priority Queue Implementation

Checks

Submit your answers to the following on Moodle. Given this min-heap:

1. Draw out the heap after inserting 11.
2. Given the min-heap after Q1, draw out the heap after inserting 2.
3. Given the min-heap after Q2, draw out the heap after calling delete 14.
4. Given the min-heap after Q3, draw out the heap after calling delete 4.