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 and a special sorting algorithm, heapsort. 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:

• 6.9 Priority Queues with Binary Heaps
• 6.10 Binary Heap Operations
• 6.11 Binary Heap 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.