THINK FIRST·CODE LATER

← All labs

Building a heap: bottom-up versus one by one

Problem

Write BuildHeap for a min-heap stored in an array (children of i at 2i + 1 and 2i + 2). Read n and n integers and:

  1. say whether the input already is a min-heap;
  2. build a heap bottom-up (Floyd): siftDown every internal node from index n/2 − 1 down to 0 — print the array and the number of swaps;
  3. build a heap from the same input by inserting one by one (siftUp for i = 1 … n − 1) — print the array and the swaps;
  4. heap-sort the first heap in place (swap the root with the last element, shrink, sift down), which leaves the array in descending order.

For the input

7
9 4 7 1 2 6 3

the program prints

Input is a min-heap: false
Bottom-up heapify: [1, 2, 3, 4, 9, 6, 7] swaps 4
Insert one by one: [1, 2, 3, 9, 4, 7, 6] swaps 6
Both are min-heaps: true
Heap sort (descending): [9, 7, 6, 4, 3, 2, 1]

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

d11-3-data-1.txt

7
9 4 7 1 2 6 3
What your program must print for d11-3-data-1.txt
Input is a min-heap: false
Bottom-up heapify: [1, 2, 3, 4, 9, 6, 7] swaps 4
Insert one by one: [1, 2, 3, 9, 4, 7, 6] swaps 6
Both are min-heaps: true
Heap sort (descending): [9, 7, 6, 4, 3, 2, 1]

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < d11-3-data-1.txt

Windows PowerShell does not understand <:

Get-Content d11-3-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.