You will not hand in the answers to this work.  There might be problems for which there are plenty of solutions available or no correct solution at all.  You are expected to talk to your peers, brainstorm, and get better in both understanding the problem and in problem-solving. The workshops are based on the policy of “no scientist left behind”.  It is your responsibility not only to make sure that you understand the material yourself but also to look around you and make sure that all the members of your team have a good understanding.

Objectives

In this workshop, we will go over Heaps which are the conceptual basis for a lot of different Data Structures and Algorithims. Though heaps can be represented as trees, we will mostly talk about array representation of heaps.

Binary Heaps

This section presents the heap data structure. A heap is defined by two properties. First, it is a complete binary tree, so heaps are nearly always implemented using the array representation for complete binary trees. Second, the values stored in a heap are partially ordered. This means that there is a relationship between the value stored at any node and the values of its children. There are two variants of the heap, depending on the definition of this relationship.

A max heap has the property that every node stores a value that is greater than or equal to the value of either of its children. Because the root has a value greater than or equal to its children, which in turn have values greater than or equal to their children, the root stores the maximum of all values in the tree.

A min heap has the property that every node stores a value that is less than or equal to that of its children. Because the root has a value less than or equal to its children, which in turn have values less than or equal to their children, the root stores the minimum of all values in the tree.

All the exercises in the rest of this section will use max heaps.

1.  On the white board sketch and reveiw the psedocode for the bubbleup method on a heap.

2.  Given the bubbleup method. Sketch and reveiw the psedocode for the insert method on a heap (priority queue).

3.  On the white board sketch and reveiw the psedocode for the bubbldown method on a heap.

4.  Given the bubbledown method. Sketch and reveiw the psedocode for the next method on a heap (priority queue).

5.  One way to build a heap is to insert the elements one at a time.  Use this technique to build a max heap from an array containing the following elements:

5, 18, 3, 25, 27, 45, 97, 88, 26, 16, 49, 67

6.  Now perform two next calls on the heap you built in the last section.

7.  Now add 35, 78, 15 (in order) to your heap.

8.  Now perform two next calls on the heap you built in the last section.

9.  Another way to build a heap is following the heapify algorithm described in class. The heapify algorithm is an in-place algorithm, i.e., you do not need any extra space to perform this.Sketch the heapify method on the whitboard. Perform Heapify algorithm to the earlier array.

10.  Now performthe Heapsort algorithm on this resultant array by combining heapify with sequential nest calls (containing 15 elements)

11.  Bonus Question It’s easy to build a max heap or a min heap .  How would you design a Heap with a functional or functor interface such that the user can specify the comparison operation used by the heap?