ES242. Data Structures and Algorithms I. Week 14 Lab
ES242. Data Structures and Algorithms I.
Lab 14
Heaps
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
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