ES242. Data Structures and Algorithms I. Week 14 Lab

ES242. Data Structures and Algorithms I.

Lab 14

Back to course page

Heaps

Problem 1. Build Heap by Insertions

You are given an array arr of length n. The array is represented in the form of a complete binary tree. A representation of an array as a binary tree is said to be heap compatible if it follows the following features:

The first element is made the root of the tree. Every subsequent element is made the left-child. If left pointer is non-empty, it is made the right-child. If both children exist, then the same procedure is followed for the left-child and then right child.

Consider the array below:

arr[] = {5,6,89,9,45,7,1}

The heap compatible representation of arr[] is as follows:

      5
      /\
     6  89
    /\  /\
   9 45 7 1

Task

You are given an array representation of a heap compatible binary tree. You have to construct a max-heap data structure using the given array. Return the BFS traversal of the data. Build the heap using iterated insertions.

Note: You may want to use the given “queue.h” file to return the BFS traversal

Input Format

The first line contains an integer n.
The next line contains n space-separated integers representing a heap compatible array.

Output Format

Return n space-separated integers that represent the max-heap.

---

Sample I/O

Sample Input 1

5
4 10 3 2 1

Sample Output 1

10 4 3 2 1

Problem 2. Heapify

You are given an array arr of length n. The array is represented in the form of a complete binary tree. A representation of an array as a binary tree is said to be heap compatible if it follows the following features:
The first element is made the root of the tree. Every subsequent element is made the left-child. If left pointer is non-empty, it is made the right-child. If both children exist, then the same procedure is followed for the left-child and then right child.
In a way, it is a greedy level-wise filling

Consider the array below:

arr[] = {5,6,89,9,45,7,1}

The heap compatible representation of arr[] is as follows:

      5
      /\
     6  89
    /\  /\
   9 45 7 1

Task:

You are given an array representation of a heap compatible binary tree. You have to construct a max-heap data structure using the given array. Return the BFS traversal of the data. Build the heap using the heapify method discussed in class.

Note: You may want to use the given “queue.h” file to return the BFS traversal

Input Format

The first line contains an integer n.
The next line contains n space-separated integers representing a heap compatible array.

Output Format

Return n space-separated integers that represent the max-heap.

---

Sample I/O

Sample Input 1

5
4 10 3 5 1

Sample Output 1

10 5 3 4 1

Sample Input 2

11
1 3 5 4 6 13 10 9 8 15 17

Sample Output 2

17 15 13 9 6 5 10 4 8 3 1