Lab 7: Testing minimal heap

Goals for this lab

By the time you have completed this lab, you should

  • know what minimal heap is
  • learn about minimal heap array form
  • be able to decide if given array input is a minheap.

Lab preparation

After logging in, create the directory for this lab:

mkdir -p cs24/lab7

Change into the lab2 directory and copy the files you will need for this lab:

cd cs24/lab7
cp ~bboe/public_html/cs24_m13/code/lab7/* .

Open up README.txt with your favorite text editor and be sure to add your and your partner's name so that you both receive credit.

Minimal Heap

Definition

Heap is a tree like data structure that satisfies the min-heap properties: it is a complete binary tree : all levels of the tree (except for the last one) are fully filled each node is smaler or equal to its children

This way the minimal element of the heap is its root element.

Array form

In the heap property it is said that all the levels of heap are completely filled. This means that we can use this information to store the heap compactly in the array. For example look at this heap:

     1
   /   \
  5     3
 /\    /
7  9  8

We can store it an array like this: 1 5 3 7 9 8.

For example we are looking at element i in the array.

Where would its children be?

In the array with indexing starting from 0 the first child of element i would be on 2i + 1 positsion and the second child would be on the 2i + 2 position.

Where would its parent be? It parent would be on floor((i - 1)/ 2) position.

In our array:

element   1 5 3 7 9 8
position  0 1 2 3 4 5

Element 5, pos = 1 has its childre on 21 + 1 = 3, and 21 + 2 = 4 positions, which correspond to 7 and 9.

Implementing a program to test for the heap-property

In this lab you will have to implement a program (test_heap.cpp) that takes command line arguments and checks if the arguments, as integers, satisfies the heap property.

Your program should only produce one of two outputs, either True\n or False\n which indicates whether or not the arguments when converted to integers represents a minumim heap. Here are some examples:

> ./a.out 1
True
> ./a.out 1 10 2
True
> ./a.out 2 1
False
> ./a.out 1 2 3 4 5 6 7 8 9 10
True
> ./a.out 1 2 3 4 5 6 7 8 9 1
False

Submitting the project

Only one person in a group need submit the project. If both members of a group submit we will only score the last submission made between the two group members. Please review the submission instructions as needed. On the submission site you will find the command you need to use to submit the project. Note that you may resubmit this project as many times as necessary up until the deadline.

 
 

Template design by Andreas Viklund