SUNY Geneseo Department of Computer Science

Problem Set 13 -- Heaps

CSci 240, Spring 2007

Prof. Doug Baldwin

Due Monday, April 23

Purpose

The goal of this exercise is to increase your understanding of heaps.

Background

Heaps are a tree data structure that makes it easy to find the minimum or maximum element in a data set, with minimal constraints on how the data are ordered within the tree. For more information about heaps, see section 14.4 of our textbook, and the lecture of April 20.

Exercise

Solve the following problems.

Problem 1

Draw a min-heap containing the numbers 5, 2, 3, 1, 9, 8, 10, and 12, ordered in conventional numeric order.

Problem 2

Draw a max-heap containing the strings "apple," "pear," "banana," "canteloupe," and "nectarine," ordered by alphabetical order.

Problem 3

Draw a max-heap containing the numbers 1, 4, 2, 1, 3, and 7, ordered in conventional numeric order.

Problem 4

Here is a min-heap of numbers, ordered in conventional numeric order:

[A Heap of Numbers]

Part A.

Show two distinct heaps that could result from inserting 20 into this heap.

Part B.

Show two distinct heaps that could result from removing the minimum value from this heap.

Part C.

Show a heap equivalent to the one above (without the insertions or deletions) that is a complete tree.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. Make an appointment to meet with me at some time convenient for you, as long as that time is before the end of the due date above. Meetings only need to be 15 minutes long. You can make an appointment by signing up on the copy of my schedule on the bulletin board outside my office.